This is the full version with appendix of the conference paper with the same
name presented at SOCG 2018. M arxiv version ETH Zürich
<EMAIL_ADDRESS>Malte Milatz lemma[theorem]Lemma
corollary[theorem]Corollary

# Random Walks on Polytopes of Constant Corank

Malte Milatz

###### Abstract.

We show that the pivoting process associated with one line and $n$ points in
$r$-dimensional space may need $\Omega(\log^{r}n)$ steps in expectation as
$n\to\infty$. The only cases for which the bound was known previously were for
$r\leq 3$. Our lower bound is also valid for the expected number of pivoting
steps in the following applications: (1) The Random-Edge simplex algorithm on
linear programs with $n$ constraints in $d=n-r$ variables; and (2) the
directed random walk on a grid polytope of corank $r$ with $n$ facets.

###### Key words and phrases:

polytope, unique sink orientation, grid, random walk

###### 1991 Mathematics Subject Classification:

[500]Theory of computation Randomness, geometry and discrete structures,
[300]Theory of computation Linear programming

(a)

(b)

Figure 1. (a) An instance of “one line and $n$ points”. (b) A possible path
that the directed random walk might take on the corresponding polytope.

##  1\. Introduction

In 2001 Gärtner et al. [GaertnerSTVW'03] introduced a random process involving
a vertical line and $n$ points in the plane (see Figure 1(a)) which they
called “the fast process” or just “one line and $n$ points”. The starting
position of this process is a pair $\\{a,b\\}$ of points that lie on opposite
sides of the vertical line. In each step the process picks a point $p$ (a
pivot) uniformly at random from the points that lie below the non-vertical
line $ab$. The subsequent position is then the unique pair $\\{p,q\\}$ with
$q\in\\{a,b\\}$ such that $p$ and $q$ lie again on opposite sides of the
vertical line. For example, in Figure 1(a) the next position would be
$\\{p,b\\}$. The authors of [GaertnerSTVW'03] gave matching upper and lower
bounds of order $\log^{2}(n)$ for the expected duration of this process in the
plane.

The process generalizes naturally to higher dimensions. However, understanding
its behavior in any dimension other than $2$ has remained a wide open problem,
with the notable exception of an $\Omega(\log^{3}n)$ lower bound in three
dimensions [Tschirschnitz'03]. As the dimension grows, the situation indeed
becomes increasingly complicated, and the question has seen no further
improvements for the subsequent fifteen years.

The relevance of the generalized process lies in its intimate connection with
the Random-Edge simplex algorithm for linear programming, which has already
been widely considered before; for example cf. [BroderDFRU'95, FelsnerGT'05,
GaertnerHZ'98, Hoke'88, MatousekSz'06]. Random-Edge is naturally formulated in
terms of a random walk on the vertex-edge graph of the feasible region (see
Figure 1(b)). To be precise it is a _directed_ random walk, because every edge
may be used in one prescribed direction only: the direction along which the
objective function improves. In each step the directed random walk moves from
the current vertex to a vertex chosen uniformly at random from all neighbors
with smaller objective value. By means of the so-called _extended Gale
transform_ , the directed random walk on a $d$-polytope with $n$ facets
translates precisely into the process of “one line and $n$ points” in
$\mathbb{R}^{r}$, where $r\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=n-d$
denotes the _corank_ of the polytope. For lack of space we refer the
interested reader to the appendix of [GaertnerSTVW'03] for a complete
exposition of the extended Gale transform.

The interpretation in terms of polytopes also explains the difficulties that
arise when analyzing the process for $r\geq 3$. Namely, it is known that every
simple polytope of corank $r=1$ is a simplex, and every simple polytope of
corank $r=2$ is a product of two simplices; these situations are thus well-
understood, classified, and not too complicated. Already for $r=3$, however,
the classification is considerably more involved (cf. chapter 6.3 in
[Gruenbaum'03]), and for $r\geq 4$ no similar classification exists.

The name “corank” is not entirely standard; it has been used e.g. in
[PfeifleZ'04]. Despite its anonymity it plays a prominent role in polytope
theory: The _Hirsch conjecture_ once stated that the corank might be an upper
bound on the diameter of any polytope. Since the Hirsch conjecture, in its
strict form, has been disproved by Santos [Santos'12], the search for a close
connection between these quantities continues. Indeed we believe it fruitful
to analyze algorithms for linear programming in a setting where the corank is
assumed to be small, i.e., a constant or a slowly growing function of $n$. A
positive result of this type is for example Kalai’s Random-Facet algorithm:
His upper bound in [Kalai'92] for the expected number of arithmetic operations
becomes polynomial if the corank is taken to be of order $r=O(\log n)$. In
contrast, Random-Edge has proved to be notoriously hard to analyze, and tight
bounds are rare when we want to understand the behavior of a given simplex
algorithm on a complete class of instances. The analysis in [KaibelMSZ'05] for
$d=3$ suggests that Random-Edge can be a good choice in low dimension; the
present paper takes the dual viewpoint, fixing the corank rather than the
dimension. Note that the mildly exponential lower bound obtained by Friedmann
et al. [FriedmannHZ'11] does not pose any restrictions on the corank.

A polytope with $n$ facets and constant corank $r$ has $O(n^{r})$ vertices,
and this bound is tight; this follows for example from McMullen’s theorem
[McMullen'71]. Thus, $O(n^{r})$ is a trivial bound for the number of Random-
Edge pivoting steps. The known bounds for $r=2$ suggest that the process
outperforms the trivial bound considerably; however, it is not at all clear
what can be expected in general. It is conceivable that a bound of
$O(\log^{r}n)$ holds, although we are currently missing the mathematical
techniques and insights to prove this. In this paper, we prove that one can at
least not do better.

The history of lower-bound constructions for specific LP-solving algorithms
shows that it is often considerably easier to prove bounds in an abstract
model; this is how _unique sink orientations_ (USOs) enter the picture. The
same principle applies to the present paper: We first present a construction
in the USO model in Section 2 and strengthen the result to the geometric
setting in the rest of the paper. Somewhat atypically, the main ideas
underlying the geometric construction are not _entirely_ different from the
ideas underlying the USO construction.

### Our results.

We prove that the random process of “one line and $n$ points” in
$\mathbb{R}^{r}$ may take $\Omega(\log^{r}n)$ steps in expectation. This
generalizes previous constructions for the cases $r=2,3$ [GaertnerSTVW'03,
Tschirschnitz'03]. The exact bound that we obtain is specified in Theorem 5.1.
Using the extended Gale transform, our result can be rephrased in different
settings, as in the following theorems. Theorem 1.1 rephrases our result in
the language of linear programs. Theorem 1.2 uses instead the language of
polytopes. The combinatorial type of the polytopes that we construct in this
way is rather special: they are _grid polytopes_ , i.e., Cartesian products of
simplices.

######  Theorem 1.1.

Let $r\in\mathbb{N}_{0}$ be a fixed parameter. There are linear programs in
$d$ variables with $n=d+r$ constraints on which the Random-Edge algorithm
needs $\Omega(\log^{r}n)$ pivoting steps in expectation as $n\to\infty$.

######  Theorem 1.2.

Let $r\in\mathbb{N}_{0}$. There are grid $d$-polytopes with $n=d+r$ facets on
which the directed random walk (with the direction specified by a linear
function) needs $\Omega(\log^{r}n)$ steps in expectation as $n\to\infty$.

##  2\. Prelude: Walks on grids

In this section we prove a lower bound of order $\log^{r}(n)$ for the expected
duration of a random walk on a certain class of directed graphs, namely
_unique sink orientations of grids_. The construction does not involve any
geometry and should be simpler to understand than the point-set construction
in Section 4.

Given a directed (multi-)graph $G$ and a vertex $v_{0}$ of $G$, the _directed
random walk_ is the random process $v_{0},v_{1},v_{2},\dots$ described as
follows: If the current position is $v_{i}$, choose one of the outgoing edges
at $v_{i}$ uniformly at random, and let $v_{i+1}$ be the other endpoint of
that edge. The process terminates when (and if) it reaches a sink. The random
variable

$\displaystyle T(G,v_{0})=\min\\{t\,\mathrel{\mathop{\mathchar
58\relax}}\,v_{t}\text{ is a sink}\\}$

will denote the duration of the directed random walk on $G$ starting in
$v_{0}$. We will abbreviate $T(G)\mathrel{\mathop{\mathchar
58\relax}}=T(G,v_{0})$ for a starting position $v_{0}$ chosen uniformly at
random from the set of vertices.

Following the terminology in [GaertnerMR'08], a _grid_ is a Cartesian product
of a (finite) number of (finite) complete graphs $G_{1},\dots,G_{r}$.
Explicitly, the vertex set of this graph is $V(G_{1})\times\dots\times
V(G_{r})$, and two vertices $(u_{1},\dots,u_{r})$ and $(v_{1},\dots,v_{r})$
are joined by an edge if and only if they differ in exactly one coordinate. We
could have defined grids equivalently as the vertex-edge graphs of grid
polytopes. The number $r$ is usually called the _dimension_ of the grid (this
is _not_ the dimension of the underlying grid polytope!); and its _size_ is
the number $|V(G_{1})|+\dots+|V(G_{r})|$.

A _subgrid_ of a grid is an induced subgraph on a set of the form
$U_{1}\times\dots\times U_{r}$ with $U_{i}\subseteq V(G_{i})$. Finally, a
_unique sink orientation_ of a grid is an orientation of the edges of the grid
with the property that every subgrid possesses a unique sink. An example is
shown in Figure 2(a).

######  Theorem 2.1.

Let $r\in\mathbb{N}_{0}$ and $m\in\mathbb{N}$. There is an $r$-dimensional
grid $G$ of size $n\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=rm$,
endowed with an acyclic unique sink orientation, such that a directed random
walk on the grid, starting at a random position, takes at least

$\operatorname{E}\bigl{[}T(G)\bigr{]}\geq\frac{1}{r!}\ln^{r}\mathinner{\left(m+1\right)}-1$
(1)

steps in expectation.

We remark that the theorem is meaningful primarily for a fixed dimension $r$
and with the grid size tending to infinity. In this setting it says that the
number of pivoting steps can be of order $\Omega(\log^{r}n)$.

(a)

(b)

(c)

Figure 2.
(a) A grid $G$ of dimension $r=2$ and size $n=5$.
(b) The augmented (multi-)graph $G^{\Delta}$, here for $\Delta=1$.
(c) A schematic depiction of the grid constructed in the proof of Theorem 2.1.

######  Proof 2.2.

We can choose the grid to be $G=G_{1}\times\dots\times G_{r}$ with
$G_{1}=\dots=G_{r}=K_{m}.$ We construct a unique sink orientation on $G$ by
induction on $r$. For $r=0$, the graph consists of a single vertex, so we need
not orient any edges.

For $r\geq 1$, we first choose a permutation of $V(G_{r})$ uniformly at random
from the set of all permutations, and we label the vertices according to the
chosen permutation, as in $V(G_{r})=\\{1,\dots,m\\}$. Now we partition the
grid into “hyperplanes”

$H_{i}=G_{1}\times\dots\times
G_{r-1}\times\\{i\\}\quad\textstyle(i=1,\dots,m).$

Each hyperplane $H_{i}$ is a subgrid of dimension $r-1$, so we can inductively
assign an orientation to it. We do this for each hyperplane independently
(i.e., all random permutations used throughout the construction are chosen
independently). The only edges that we still need to orient are those between
vertices from two distinct hyperplanes. We orient those according to our
chosen permutation of $V(G_{r})$. Explicitly, the edge from a vertex
$(u_{1},\dots,u_{r-1},i)$ to $(u_{1},\dots,u_{r-1},j)$ is directed forwards if
and only if $i>j$. See Figure 2(c) for an illustration.

It is easy to verify that this defines an acyclic unique sink orientation of
the grid. We will now analyze the duration of the random walk from a random
starting position. Concerning the starting position, here is a key
observation: Due to the random permutations involved in the construction of
the grid orientation, it amounts to the same random process whether we start
the walk in a random position of the grid, or whether we start in any fixed
given position. Consequently, if the random walk visits one of the hyperplanes
$H_{i}$, we can relate the behavior within $H_{i}$ to the $(r-1)$-dimensional
construction, for which we have a lower bound by induction. However, there
_is_ a difference between $H_{i}$ and the $(r-1)$-dimensional construction:
namely, every vertex of $H_{i}$ has $i-1$ additional outgoing edges by which
the walk may leave $H_{i}$ at any moment. To account for these, we make use of
the following “augmented” multigraph; see Figure 2(b) for an example.

######  Definition 2.3.

Given any (multi-)graph $\Gamma$ and a parameter $\Delta\in\mathbb{N}_{0}$, we
define an _augmented multigraph_ $\Gamma^{\Delta}$ as follows. We add a new,
special, vertex $v_{\infty}$ to the vertex set of $\Gamma$. Furthermore we add
$\Delta$ many edges $\overrightarrow{vv_{\infty}}$ for every $v\in V(\Gamma)$.
If $\Delta=0$ then we add one additional edge $\overrightarrow{sv_{\infty}}$
for every sink $s$ of $\Gamma$; this way we ensure that $v_{\infty}$ is the
only sink of $\Gamma^{\Delta}$.

######  Lemma 2.4.

Let $\Delta\in\mathbb{N}_{0}$. Then the expected duration of the directed
random walk on the augmented construction $G^{\Delta}$, starting from a random
position (and ending in $v_{\infty}$), satisfies the bound

$\operatorname{E}\bigl{[}T(G^{\Delta})\bigr{]}\geq\frac{1}{r!}\mathinner{\left(\ln\mathinner{\left(m+\Delta+1\right)}-\ln(\Delta+1)\right)}^{r}.$

Proof of the lemma. We proceed by induction on $r\geq 0$. If $r=0$ then $G$
consists of a single vertex and there is nothing to prove; so let $r\geq 1$.
For $i\in\\{1,\dots,m\\}$, let $T_{i}$ denote the number of positions that the
walk visits on $H_{i}$, so that the total duration of the walk is given by

$\displaystyle T(G^{\Delta})=T_{1}+\dots+T_{m}.$ (2)

Furthermore, let $\mathcal{E}_{i}$ denote the event that the random walk
visits at least one vertex in $H_{i}$ ($i=1,\dots,m$). We claim

$\displaystyle\Pr\bigl{[}\mathcal{E}_{i}\bigr{]}\geq\frac{1}{\Delta+i}.$ (3)

To this end we consider the hitting time

$\tau_{i}\mathrel{\mathop{\mathchar
58\relax}}=\min\mathinner{\left\\{t\leavevmode\nobreak\
\mathrel{\mathop{\mathchar 58\relax}}\leavevmode\nobreak\
v_{t}\in\\{v_{\infty}\\}\cup H_{1}\cup\dots\cup H_{i}\right\\}}$

where, as before, $v_{t}\in V(G^{\Delta})$ denotes the position that the
random walk visits at time $t$ ($t=0,1,2,\dots$). Note that the hyperplanes
$H_{i}$ are visited in decreasing order; so either the walk visits $H_{i}$ at
time $\tau_{i}$, or not at all. Hence, $\mathcal{E}_{i}$ equals the event
$\\{v_{\tau_{i}}\in H_{i}\\}$. We now calculate the probability of this event
by conditioning on $\tau_{i}\geq 1$.

Case 1: $\tau_{i}\geq 1$. Since $v_{\tau_{i}-1}$ has $\Delta$ outgoing edges
to $v_{\infty}$ and one outgoing edge to each of the hyperplanes
$H_{1},\dots,H_{i}$, and since the random walk is equally likely to move along
any of these $\Delta+i$ edges, we obtain

$\displaystyle\Pr\bigl{[}\mathcal{E}_{i}\,\big{|}\,\tau_{i}\geq
1\bigr{]}=\Pr\bigl{[}v_{\tau_{i}}\in H_{i}\,\big{|}\,\tau_{i}\geq
1\bigr{]}=\frac{1}{\Delta+i}.$ (4)

Case 2: $\tau_{i}=0$. Here we need to look at $v_{0}$, which (conditioned on
$\tau_{i}=0$) is a vertex taken uniformly at random from the set
$H_{1}\cup\dots\cup H_{i}$. Since the hyperplanes $H_{1},\dots,H_{i}$ are all
of equal cardinality, we obtain

$\displaystyle\Pr\bigl{[}\mathcal{E}_{i}\,\big{|}\,\tau_{i}=0\bigr{]}=\Pr\bigl{[}v_{0}\in
H_{i}\,\big{|}\,\tau_{i}=0\bigr{]}=\frac{1}{i}\geq\frac{1}{\Delta+i}.$ (5)

The claim (3) follows by combining (4) and (5). Now, it is easy to see that
$T_{i}|\mathcal{E}_{i}$ has the same distribution as
$T((H_{i})^{\Delta+i-1})$, so that we obtain

$\displaystyle\operatorname{E}\bigl{[}T_{i}\bigr{]}$
$\displaystyle=\Pr\bigl{[}\mathcal{E}_{i}\bigr{]}\cdot\operatorname{E}\bigl{[}T_{i}\,\big{|}\,\mathcal{E}_{i}\bigr{]}$
$\displaystyle\geq\frac{1}{\Delta+i}\cdot\operatorname{E}\bigl{[}T((H_{i})^{\Delta+i-1})\bigr{]}$
$\displaystyle\geq\frac{1}{\Delta+i}\cdot\frac{1}{(r-1)!}\mathinner{\left(\ln\mathinner{\left(m+\Delta+i\right)}-\ln(\Delta+i)\right)}^{r-1}$

where the last step was using the induction hypothesis. With (2) we obtain

$\displaystyle\operatorname{E}\bigl{[}T\bigr{]}$
$\displaystyle=\sum_{i=1}^{m}\operatorname{E}\bigl{[}T_{i}\bigr{]}$
$\displaystyle\geq\sum_{i=1}^{m}\frac{1}{\Delta+i}\cdot\frac{1}{(r-1)!}\mathinner{\left(\ln\mathinner{\left(m+\Delta+i\right)}-\ln(\Delta+i)\right)}^{r-1}$
$\displaystyle\geq\sum_{i=1}^{m}\frac{1}{\Delta+i}\cdot\frac{1}{(r-1)!}\mathinner{\left(\ln\mathinner{\left(m+\Delta+1\right)}-\ln(\Delta+i)\right)}^{r-1}$
$\displaystyle\geq\int_{1}^{m+1}\frac{1}{\Delta+x}\cdot\frac{1}{(r-1)!}\mathinner{\left(\ln\mathinner{\left(m+\Delta+1\right)}-\ln(\Delta+x)\right)}^{r-1}\operatorname{d\\!}x$
$\displaystyle=\Bigl{[}\leavevmode\nobreak\
-\frac{1}{r!}\mathinner{\left(\ln(m+\Delta+1)-\ln(\Delta+x)\right)}^{r}\leavevmode\nobreak\
\Bigr{]}_{x=1}^{m+1}$
$\displaystyle=\frac{1}{r!}\mathinner{\left(\ln(m+\Delta+1)-\ln(\Delta+1)\right)}^{r}$

which concludes the proof of the lemma. In order to deduce the theorem, we
choose $\Delta=0$ to obtain a random orientation (i.e., a probability
distribution of orientations) of $G^{0}$ such that

$\operatorname{E}\bigl{[}T(G^{0})\bigr{]}\geq\frac{1}{r!}\ln^{r}(m+1).$ (6)

A directed random walk on $G$ corresponds to a random walk on $G^{0}$, except
that the latter does one additional step in the end (from the sink of $G$ to
the extra vertex $v_{\infty}$). Thus we need to subtract $1$ from the bound
(6) to obtain the desired bound (1). We are left only to observe that there
must then also exist at least one concrete (not random) choice of orientation
$G$ that satisfies this bound. This concludes the proof of Theorem 2.1.

In Theorem 2.1 we chose $n$ to be a multiple of $r$. For other values of $n$
we can still deduce essentially the same bound, as in the following corollary.

For all $r,n\in\mathbb{N}$ with $n>r$ there is an $r$-dimensional acyclic
unique sink orientation of a grid $\hat{G}$ of size $n$ such that
$\operatorname{E}\bigl{[}T(\hat{G})\bigr{]}>\frac{1}{r!}\ln^{r}\mathinner{\left(\frac{n}{r}\right)}-1.$

######  Proof 2.5.

If $n$ is divisible by $r$, then the corollary is an immediate consequence of
Theorem 2.1. Assume that $n$ is not divisble by $r$, and let
$m=\lfloor\frac{n}{r}\rfloor$. We take our construction $G$ from the proof of
Theorem 2.1 for the size $n^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=rm$
and embed it into a grid $\hat{G}$ of size $n$. We can do this in such a
fashion that all the edges between $G$ and $\hat{G}\setminus G$ point into
$G$. In this way we obtain an acyclic unique sink orientation on $\hat{G}$
with
$\operatorname{E}\bigl{[}T(\hat{G})\bigr{]}\geq\operatorname{E}\bigl{[}T(G)\bigr{]}$,
which yields the corollary using (1) with $m>\frac{n}{r}-1$.

##  3\. One line and $n$ points

Here we describe the geometric setting in which we prove our main theorem. We
will assume that we are given a set of $n$ points $A\subseteq\mathbb{R}^{r}$
and a non-zero vector $u\in\mathbb{R}^{r}$. Its linear span $\mathbb{R}u$ is a
line: the “one line” or _requirement line_ featured in the heading of this
section.

### Pierced simplices and general position.

We call a set $S\subseteq A$ _pierced_ or, more exactly, _$u$ -pierced_ if the
convex hull $\operatorname{conv}(S)$ intersects the requirement line
$\mathbb{R}u$. If in addition $|S|=r$, then $S$ is a _pierced simplex_. Some
readers might find it more natural to reserve the term “simplex” for the set
$\operatorname{conv}(S)$ instead of $S$; we will always take care to
distinguish between the two whenever the distinction is important. A pierced
simplex $S$ is _non-degenerate_ if (i) $S$ is affinely independent, (ii) no
proper subset of $S$ is a pierced set, and (iii) the affine hyperplane spanned
by $S$ and the requirement line are not parallel. — Within this paper, when we
say that $(A,u)$ is _in general position_ , we merely mean that every
$u$-pierced simplex $S\subseteq A$ is non-degenerate.

### Below and above.

Consider the affine span of a non-degenerate pierced simplex $S\subseteq A$:
it is a hyperplane in $\mathbb{R}^{r}$ that is not parallel to the vector $u$.
The direction of $u$ thus determines an orientation (a positive and negative
side) of this hyperplane. For any point $x\in A$, we will say that $x$ lies
_(strictly) below $S$_ if it lies on the (strictly) negative side of the
hyperplane. The word “above” is understood similarly.

Figure 3. A tetrahedron in $\mathbb{R}^{3}$. Its two front facets, the green
and orange triangles, are both a pierced simplex. If $S$ denotes the green
triangle at the top, then the _simplex obtained by pivoting at $S$ with $p$_
is the orange triangle at the bottom.

### Pivoting steps.

Given $(A,u)$ in general position, a pierced simplex $S\subseteq A$ and a
point $p\in A$ strictly below $S$, we define a new pierced simplex
$S^{\prime}\subseteq A$ which we call the _simplex obtained by pivoting at $S$
with $p$_. To this end consider the set $S\cup\\{p\\}$: It is an
$r$-dimensional simplex, and the boundary of
$\operatorname{conv}(S\cup\\{p\\})$ is pierced by the line $\mathbb{R}u$
exactly twice: once in the facet $S$, and once in another facet which we take
to be $S^{\prime}$. See Figure 3 for an example. We note that

  * •

$S^{\prime}$ is by general position uniquely determined,

  * •

$S^{\prime}$ is a subset of $S\cup\\{p\\}\subseteq A$, and

  * •

$S^{\prime}$ is a pierced simplex.

### The random process.

Given a finite set $A\subseteq\mathbb{R}^{r}$ of $n$ points, a non-zero vector
$u\in\mathbb{R}^{r}$, and a $u$-pierced simplex $S_{0}\subseteq A$, we define
the following random process, denoted $\mathcal{R}(A,u,S_{0})$. We will keep
on assuming that $(A,u)$ is in general position.

The states (or positions) of the process are pierced simplices, and $S_{0}$ is
the starting position. The consecutive positions $S_{1},S_{2},\dots$ are
obtained as follows. If the current position is $S_{i}$, let $p_{i}$ be a
point (the $i$th “pivot”) chosen uniformly at random from the set of points
from $A$ that lie strictly below $S_{i}$. (If there are no such points, then
the random process terminates at this stage.) Now define $S_{i+1}$ to be the
simplex obtained by pivoting at $S_{i}$ with $p_{i}$. — Our main theorem in
Section 5 states that the expected number of steps until the process
terminates can be of order $\log^{r}(n)$.

##  4\. Construction

Here we construct the point set that underlies the proof of our main theorem
(Theorem 5.1 in Section 5). For the proofs of the technical lemmas in this
section we refer the reader to the appendix.

### Points, colors, layers, and phases.

For all $r,m\in\mathbb{N}$ we define our point set
$A(r,m)\subseteq\mathbb{R}^{r}$ as follows; a sketch is shown in Figure 4. We
use the notation $\mathbf{0}_{r}=(0,\dots,0)$ for the all-zeros vector in
$\mathbb{R}^{r}$. We let

$A(r,m)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{\,a_{i,j,k}\,\mathrel{\mathop{\mathchar
58\relax}}\,i,j\in[r],\leavevmode\nobreak\ i\leq j,\leavevmode\nobreak\
k\in[m]\,\\}$

where

$a_{i,j,k}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\begin{pmatrix}\mathbf{0}_{i-1}\\\
\mathinner{\left(m^{3}+m^{5}+\dots+m^{2r-2j+1}\right)}+(r-j)m+k\\\
\mathbf{0}_{j-i}\\\ -m^{2r-2j+1}\\\ -m^{2r-2j-1}\\\ \vdots\\\ -m^{5}\\\
-m^{3}\end{pmatrix}.$

In particular, for $j=r$, we have $a_{i,r,k}=k\mathbf{e}_{i}$, where
$\mathbf{e}_{i}$ denotes the $i$th standard unit vector in $\mathbb{R}^{r}$.
We call the indices $i,j,k$ the _color_ , the _layer_ , and the _phase_ of a
point, respectively. Sometimes we will need a notational shorthand for colors
and layers, so we define $\mathcal{C}_{i}\subseteq A(r,m)$ to denote the set
of points of color $i$, and $\mathcal{L}_{j}\subseteq A(r,m)$ to denote the
set of points from layer $j$. So defined, $\mathcal{L}_{j}$ consists of $jm$
points, and our point set consists of $n=\binom{r+1}{2}\cdot m$ points
overall.

We will fix $u$ to denote the all-ones vector, $u=\mathbf{1}_{r}$, so that a
set $S\subseteq A(r,m)$ is pierced if and only if its convex hull intersects
the diagonal line $\mathbb{R}\mathbf{1}_{r}$. The rest of this section is
devoted to a number of lemmas concerning the relevant structure of our
construction. We begin by identifying the pierced subsets. While the lemmas in
this section could also be proved in an intuitive geometric/visual way, such
an exposition would be likely to take longer than our straight-forward proofs
based on calculations.

Let $S\subseteq A(r,m)$ be a pierced subset. Then $S$ contains a point of
color $i$, for all $i\in[r]$.

This follows essentially from the fact that every point from our set $A(r,m)$
has a unique positive (and large) entry that determines its color class. The
formal proof goes as follows. Since $S$ is pierced, there is a convex
combination of the form

$\displaystyle\mu\mathbf{1}_{r}=\sum_{x\in S}\lambda_{x}x$ (7)

with $\mu\in\mathbb{R}$, $\lambda_{x}\geq 0$ for all $x\in S$, and $\sum_{x\in
S}\lambda_{x}=1$. We will use the following sign properties that hold for
every point $x\in A(r,m)$:

We have $\mathbf{1}_{r}^{\mathrm{T}}x>0$.

Let $i$ denote the color of the point $x$. Then $x_{i}>0$, and $x_{j}\leq 0$
for all $j\neq i$. Taking the sum of the coordinates in (7) and using property
(i), we obtain

$\displaystyle\mu\hskip 1.0ptr=\sum_{x\in
S}\lambda_{x}\mathbf{1}_{r}^{\mathrm{T}}x=\mathbf{1}_{r}^{T}x>0$

and hence $\mu>0$. Comparing the signs of the left-hand and right-hand side in
(7) we find that for every $i$ there must be some $x^{(i)}\in S$ with
$x^{(i)}_{i}>0$. By property (ii), $x^{(i)}$ has color $i$, which proves the
lemma.

Figure 4. The constructed point set for $r=3$, $m=4$. The sketch is not true
to scale. All off-axis points lie in the plane $x_{3}=-64$.

The next lemma shows the converse of Lemma 4, implying that the set of pierced
simplices can be identified with the set
$\mathcal{C}_{1}\times\dots\times\mathcal{C}_{r}$. More to the point, this
implies that the extended Gale transform of our point set defines a grid
polytope.

Let $S\subseteq A(r,m)$ and assume that $S$ contains a point from each color
class $\mathcal{C}_{1},\dots,\mathcal{C}_{r}$. Then $S$ is a pierced subset.
Furthermore, for each $i\in[r]$, $\operatorname{conv}(S)$ intersects the $i$th
coordinate axis in some point $t\mathbf{e}_{i}$ with $t>0$.

It suffices to show the second statement of the lemma; so let $i\in[r]$.
Consider the system

$\displaystyle B\lambda=t\mathbf{e}_{i}$ (8)

in the variables $(\lambda_{1},\dots,\lambda_{r},t)\in\mathbb{R}^{r+1}$, where
$B\in\mathbb{R}^{r\times r}$ is a matrix whose $j$th column is an arbitrarily
chosen element of $S\cap\mathcal{C}_{j}$ ($j=1,\dots,r$). We need to show that
(8) has a solution with $t>0$, $\sum_{i}\lambda_{i}=1$ and $\lambda_{i}\geq 0$
for all $i$. To this end we note that, by construction of our point set,

  * •

all non-diagonal entries of $B$ are non-positive, and

  * •

$B^{\mathrm{T}}$ is strictly diagonally dominant, i.e., $B_{ii}>\sum_{j\neq
i}\mathinner{\\!\left\lvert B_{ji}\right\rvert}$.

These conditions imply that $B^{\mathrm{T}}$ and hence $B$ is what is known as
a non-singular M-matrix, which in turn implies that $B^{-1}$ exists and is
non-negative (cf. conditions $\text{N}_{39}$ and $\text{F}_{15}$ in
[Plemmons'77]). Hence the $i$th column of $B^{-1}$ is a non-negative solution
$\hat{\lambda}$ to the equation $B\hat{\lambda}=\mathbf{e}_{i}$. We can scale
the vector $\hat{\lambda}$ by the factor

$\textstyle t\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\mathinner{\left(\sum_{i}\hat{\lambda}_{i}\right)}^{-1}>0$

so as to achieve that the entries of the vector $\lambda\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=t\hat{\lambda}$
sum up to $1$, which gives the desired solution to the system (8).

$(A,\mathbf{1}_{r})$ is in general position; that is, every pierced simplex
$S\subseteq A(r,m)$ is non-degenerate.

First we need to prove that $S$ is affinely independent. To this end, let
$\mathrm{aff}(S)$ denote the affine span of $S$: we want to prove that
$\mathrm{aff}(S)$ is $(r-1)$-dimensional (a hyperplane). Assume that
$\mathrm{aff}(S)$ was at most $(r-2)$-dimensional, and let $z$ denote the
intersection of $\operatorname{conv}(S)\subseteq\mathrm{aff}(S)$ with the
requirement line. Then, by Carathéodory’s theorem applied within the space
$\mathrm{aff}(S)$, some subset $S^{\prime}\subseteq S$ with $|S^{\prime}|\leq
r-1$ would still contain $z$ in its convex hull. It follows that $S^{\prime}$
is a pierced subset with at most $r-1$ elements; a contradiction to Lemma 4.

Second we need to check that no proper subset of $S$ is a pierced subset.
Assuming the contrary would again lead to an immediate contradiction with
Lemma 4.

Third we need to prove that $\mathrm{aff}(S)$ and the requirement line are not
parallel. Assume they were parallel. Then, since they intersect, the
requirement line would lie within the hyperplane $\mathrm{aff}(S)$, wherein it
intersects the convex set $\operatorname{conv}(S)$. But if it intersects
$\operatorname{conv}(S)$, then it also intersects some facet
$\operatorname{conv}(S^{\prime})$ with $S^{\prime}\subseteq S$ and
$|S^{\prime}|\leq\dim(\mathrm{aff}(S))=r-1$. Again we would have that
$S^{\prime}$ is a pierced subset with at most $r-1$ elements, in contradiction
with Lemma 4.

Lemma 4 above assures that the random process associated with our construction
is well-defined. The next lemma states that, as our random process evolves,
the intersection value $t$ of the current position with the $i$th coordinate
axis ($i=1,\dots,r)$ is monotonically decreasing with time and, thus, can
serve as a measure of progress. This is of course by no means true for an
arbitrary point set, but it holds in the case of our construction. Next, Lemma
4 states a simple condition from which to tell whether the points from the
layer $\mathcal{L}_{r-1}$ lie above or below the current position; this
condition is immediately relevant for the analysis of the random process.

######  Lemma 4.1.

Let $i\in[r]$. Let $S\subseteq A(r,m)$ be a pierced simplex, let $p\in A$ be a
point strictly below $S$, and let $S^{\prime}$ denote the pierced simplex
obtained by pivoting at $S$ with $p$. Let $t_{i}\mathbf{e}_{i}$ and
$t^{\prime}_{i}\mathbf{e}_{i}$ denote the intersection of
$\operatorname{conv}(S)$ (respectively, $\operatorname{conv}(S^{\prime})$)
with the $i$th coordinate axis, as in Lemma 4. Then we have
$t^{\prime}_{i}\leq t_{i}$ for all $i$.

We omit the proof of Lemma 4.1; the reader may want to make it visually
plausible with the help of Lemma 4. The latter is essentially saying that all
points of $A(r,m)$ lie on the outside of the cone spanned by the coordinate
axes.

Let $r\geq 2$, $m\geq 2$, let $S\subseteq A(r,m)$ be a pierced simplex, and
let $t_{i}\mathbf{e}_{i}$ denote the intersections of $\operatorname{conv}(S)$
with the $i$th coordinate axis as in Lemma 4 ($i=1,\dots,r$).

If, for some $i$, $t_{i}\leq t_{r}$, then all points from
$\mathcal{C}_{i}\cap\mathcal{L}_{r-1}$ lie strictly _above_ $S$.

If, for some $i$, $t_{i}\geq t_{r}+1$, then all points from
$\mathcal{C}_{i}\cap\mathcal{L}_{r-1}$ lie strictly _below_ $S$.

If $i$ is such that $t_{i}=\min\\{t_{1},\dots,t_{r}\\}$, then all points from
$\mathcal{C}_{i}\setminus\mathcal{L}_{r}$ lie strictly _above_ $S$. In
particular we then have $t_{i}\mathbf{e}_{i}\in S$.

First we recall that $S$ contains one point from each color class, and we
remark that the color class $\mathcal{C}_{r}$ consists solely of the points
$\mathbf{e}_{r},2\mathbf{e}_{r},\dots,m\mathbf{e}_{r}$. This implies $1\leq
t_{r}\leq m$, which will be used in the calculation below. Second we recall
that a generic point from $\mathcal{C}_{i}\cap\mathcal{L}_{r-1}$ is, by
definition, of the form

$\displaystyle\begin{pmatrix}\mathbf{0}_{i-1}\\\ m^{3}+m+k\\\
\mathbf{0}_{r-1-i}\\\ -m^{3}\end{pmatrix}$ (9)

with $k\in[m]$.

_Ad (a)._ The affine hyperplane spanned by $S$ has the equation

$\displaystyle\frac{x_{1}}{t_{1}}+\dots+\frac{x_{r}}{t_{r}}-1=0;$ (10)

and a point lies strictly above $S$ if and only if the left hand side in (10)
is positive. We can easily verify the statement by plugging (9) into (10),
which gives indeed

$\displaystyle\frac{m^{3}+m+k}{t_{i}}+\frac{-m^{3}}{t_{r}}-1$
$\displaystyle\geq\frac{m^{3}+m+1}{t_{r}}+\frac{-m^{3}}{t_{r}}-1$
$\displaystyle=\frac{m+1}{t_{r}}-1\geq\frac{m+1}{m}-1>0.$

_Ad (b)._ This time we need to show that the left-hand side in (10) is
negative. We calculate similarly:

$\displaystyle\frac{m^{3}+m+k}{t_{i}}+\frac{-m^{3}}{t_{r}}-1$
$\displaystyle\leq\frac{m^{3}+2m}{1+t_{r}}+\frac{-m^{3}}{t_{r}}-1$
$\displaystyle=\frac{-m^{3}+2mt_{r}}{(1+t_{r})t_{r}}-1$
$\displaystyle\leq\frac{-m^{3}+2m^{2}}{2}-1$ since $1\leq t_{r}\leq m$
$\displaystyle<0.$

_Ad (c)._ Let $x\in\mathcal{C}_{i}\setminus\mathcal{L}_{r}$. We use the
convenient fact that, for all such points $x$, we have
$\mathbf{1}^{\mathrm{T}}x\geq m+1$. Plugging $x$ into (10) gives

$\displaystyle\frac{x_{1}}{t_{1}}+\dots+\frac{x_{r}}{t_{r}}-1$
$\displaystyle=\underbrace{\frac{x_{i}}{t_{i}}}_{>0}+\sum_{j\neq
i}\underbrace{\frac{x_{j}}{t_{j}}}_{<0}-1\geq\frac{x_{i}+\sum_{j\neq
i}x_{j}}{t_{i}}-1$
$\displaystyle=\frac{\mathbf{1}^{\mathrm{T}}x}{t_{i}}-1\geq\frac{m+1}{m}-1>0.$

In order to deduce the additional statement $t_{i}\mathbf{e}_{i}\in S$, recall
that by Lemma 4, $S$ must contain some point from the color class
$\mathcal{C}_{i}$, and by the above, this point must be an element of
$\mathcal{L}_{r}$. But all the points from
$\mathcal{L}_{r}\cap\mathcal{C}_{i}$ lie on the $i$th axis, so
$t_{i}\mathbf{e}_{i}$ is the only possible choice.

The last lemma in this section states that taking the point set $A(r+1,m)$ and
removing the outermost layer $\mathcal{L}_{r+1}$ yields a point set that is
equivalent, for our purposes, to the set $A(r,m)$. This observation is key to
the inductive approach followed in section 5. Actually, the statement is a bit
more general: The lemma starts from the set $A(R,m)$ for any $R>r$ and then
removes all higher layers $\mathcal{L}_{r+1},\dots,\mathcal{L}_{R}$.

Assume $m\geq 3$. For $R>r$, let

$B\mathrel{\mathop{\mathchar
58\relax}}=\\{(x_{1},\,\cdots,\,x_{r})\,\mathrel{\mathop{\mathchar
58\relax}}\,x\in A(R,m),\leavevmode\nobreak\
x\in\mathcal{L}_{1}\cup\dots\cup\mathcal{L}_{r}\\}.$

Then Lemmas 4 to 4 are also valid for the point set $B$ in place of $A(r,m)$.

Lemmas 4 to 4.1 are based on sign properties that still hold for the set $B$;
so their validity follows with the original proof. We will now verify
statements (a,b,c) from Lemma 4 for the set $B$ by showing that their original
proof can be adapted, where we abbreviate

$\alpha\mathrel{\mathop{\mathchar
58\relax}}=m^{3}+m^{5}+\dots+m^{2R-2r+1}+(R-r)m.$

The hyperplane spanned by $S$ can again be written as in (10), but this time
instead of $1\leq t_{r}\leq m$ we have $\alpha+1\leq t_{r}\leq\alpha+m$, and
this time a generic point from $\mathcal{L}_{r-1}\cap\mathcal{C}_{i}$ is of
the form

$\displaystyle\begin{pmatrix}\mathbf{0}_{i-1}\\\ \alpha+m^{2R-2r+3}+m+k\\\
\mathbf{0}_{r-1-i}\\\ -m^{2R-2r+3}\end{pmatrix}.$ (11)

_Ad (a)._ We assume $t_{i}\leq t_{r}$. In order to show that all points from
$\mathcal{C}_{i}\cap\mathcal{L}_{r-1}$ lie below the hyperplane given by (10),
we plug (11) into (10) to obtain

$\displaystyle\frac{\alpha+m^{2R-2r+3}+m+k}{t_{i}}+\frac{-m^{2R-2r+3}}{t_{r}}-1$
$\displaystyle\geq\frac{\alpha+m^{2R-2r+3}+m+1}{t_{r}}+\frac{-m^{2R-2r+3}}{t_{r}}-1$
$\displaystyle\geq\frac{\alpha+m+1}{\alpha+m}-1=\frac{1}{\alpha+m}>0,$

as desired.

_Ad (b)._ We first note that the expression $\alpha+m+2$, which will occur in
the calculation below, can be upper bounded e.g. by $\frac{89}{72}m^{2R-2r+1}$
(assuming $m\geq 3$ and $R-r\geq 1$), which implies the coarse, but useful,
bound

$\displaystyle(\alpha+m+2)(\alpha+m+1)<2m^{4R-4r+2}.$ (12)

This time we assume $t_{i}\geq 1+t_{r}$ and we want to show that all points
from $\mathcal{C}_{i}\cap\mathcal{L}_{r-1}$ lie below the hyperplane spanned
by $S$; so we plug a generic such point into (10) to obtain

$\displaystyle\frac{\alpha+m^{2R-2r+3}+m+k}{t_{i}}+\frac{-m^{2R-2r+3}}{t_{r}}-1$
$\displaystyle\leq\frac{\alpha+m^{2R-2r+3}+2m}{1+t_{r}}-\frac{m^{2R-2r+3}}{t_{r}}-1$
$\displaystyle=\frac{\alpha+2m}{1+t_{r}}-\frac{m^{2R-2r+3}}{(1+t_{r})t_{r}}-1$
$\displaystyle\leq\frac{\alpha+2m}{\alpha+2}-\frac{m^{2R-2r+3}}{(\alpha+m+2)(\alpha+m+1)}-1$
$\displaystyle=\frac{2m-2}{\alpha+2}-\frac{m^{2R-2r+3}}{(\alpha+m+2)(\alpha+m+1)}$
$\displaystyle<\frac{2m-2}{m^{2R-2r+1}}-\frac{m^{2R-2r+3}}{2m^{4R-4r+2}}$ by
(12)
$\displaystyle=\frac{-1}{2m^{2R-2r+1}}\mathinner{\left(m-2\right)}^{2}\leq 0.$

_Ad (c)._ The proof from Lemma 4 adapts immediately, this time using the
relation $\mathbf{1}^{\mathrm{T}}x\geq\alpha+m+1$.

##  5\. Analysis

The goal of this section is to prove the main theorem of this paper, concerned
with the random process $\mathcal{R}_{r,m}=\mathcal{R}(A,u,S_{0})$ associated
with the point set $A\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=A(r,m)$,
the all-ones vector $u\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\mathbf{1}_{r}$,
and the starting position $S_{0}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{m\mathbf{e}_{1},\dots,m\mathbf{e}_{r}\\}$:

######  Theorem 5.1.

The expected number of steps performed by the random process
$\mathcal{R}_{r,m}$ is at least

$\displaystyle\frac{1}{r!^{3}}\mathinner{\left(\ln\mathinner{\bigl{(}m+{\textstyle\binom{r}{2}}+\Delta\bigr{)}}-\ln\mathinner{\bigl{(}1+{\textstyle\binom{r}{2}}+\Delta\bigr{)}}\right)}^{r}=\Omega(\log^{r}m).$

In terms of the number of points, $n$, the bound can be written in the form
$\Omega(\log^{r}n)$.

### The augmented process $\mathcal{R}^{\Delta}_{r,m}$.

In order to make an inductive proof possible, we will make use of an
“augmented” pivoting process, in analogy to the “augmented graph” that we used
in the proof of Theorem 2.1. Given a number $\Delta\geq 0$, the _augmented
process_ $\mathcal{R}^{\Delta}_{r,m}$ is defined as follows.

  * •

The starting position is chosen by an adversary, in the following way. The
adversary chooses one new point $\alpha_{i}\mathbf{e}_{i}$ on each axis,
subject to the constraint $\alpha_{i}\geq m$. These points are added to the
point set $A=A(r,m)$ to obtain an augmented point set

$A^{\prime}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=A\cup\\{\alpha_{i}\mathbf{e}_{i}\,\mathrel{\mathop{\mathchar
58\relax}}\,i\in[r]\\},$

and the starting position is now chosen as $S_{0}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{\alpha_{1}\mathbf{e}_{1},\dots,\alpha_{r}\mathbf{e}_{r}\\}.$
We fit the new points into our terminology of colors, layers and phases by
saying that $\alpha_{i}\mathbf{e}_{i}$ has color $i$, layer $r$ and phase
$m+1$; and we remark that the lemmas in Section 3 still hold for the augmented
point set.

  * •

The positions $S_{0},S_{1},\dots$ of the augmented process are pierced
simplices of $A^{\prime}$, except that we also introduce a new, special,
position $S_{\infty}$. ($S_{\infty}$ is just a formal symbol; it is not
represented by any simplex.) This will be the terminal position.

  * •

If we are currently at position $S_{t}$, then the next position $S_{t+1}$ is
obtained as follows: Let $\text{below}(S_{t})\subseteq A^{\prime}$ denote the
set of points that lie strictly below $S_{t}$. We draw a pivot element
$p_{t+1}$ from the set $\text{below}(S_{t})\cup\\{\infty\\}$ according to the
distribution

$\displaystyle\Pr\bigl{[}p_{t+1}=x\bigr{]}=\begin{cases}\frac{1}{\mathinner{\\!\left\lvert\text{below}(S_{t})\right\rvert}+\Delta}&\text{
for }x\in\text{below}(S_{t}),\\\\[8.61108pt]
\frac{\Delta}{\mathinner{\\!\left\lvert\text{below}(S_{t})\right\rvert}+\Delta}&\text{
for }x=\infty.\end{cases}$

If $p_{t+1}=\infty$, then $S_{t+1}=S_{\infty}$, and the process terminates.
Otherwise we perform a standard pivoting step at $S_{t}$ with $p_{t+1}$. (Edge
case: If $\Delta=0$ and $\text{below}(S_{t})=\emptyset$, then we always pick
$p_{t+1}=\infty$.)

Note that, despite its name, the “augmented” process typically terminates
earlier than the non-augmented process: the larger the parameter $\Delta$ is,
the sooner! For $\Delta=0$ the augmented process behaves like the original,
non-augmented process — except for the modified starting position and one
additional final pivoting step towards the terminal position $S_{\infty}$.

### The phase of a pierced simplex.

We define the _phase_ of a pierced simplex $S\subseteq A^{\prime}$ as

$\mathrm{phase}(S)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\min\\{\mathrm{phase}(p)\,\mathrel{\mathop{\mathchar
58\relax}}\,p\in S\text{ with }\mathrm{layer}(p)=r\\}.$

The minimum is well-defined because $S$ contains at least one point from the
layer $\mathcal{L}_{r}$: Indeed Lemma 4 tells us that $S$ contains a point
from $\mathcal{C}_{r}$, which is a subset of $\mathcal{L}_{r}$. For
consistency we also define $\text{phase}(S_{\infty})\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=0$.
— Note that we are overloading the term “phase”, because we have defined the
phase of a point earlier.

We remark that the phase of a pierced simplex can be equivalently written as
$\mathrm{phase}(S)=\min\\{t_{1},\dots,t_{r}\\}$, where $t_{i}\mathbf{e}_{i}$
denotes the intersection of $\operatorname{conv}(S)$ with the $i$th coordinate
axis; this follows from Lemma 4(c). Using this observation, the possible
choices for pivots at the time of a phase change are easily identified, and
from this information we may read off the probability that a particular phase
is visited. The following lemma summarizes the result of this observation.

######  Lemma 5.2 (— The phases visited by the augmented process).

Let $\sigma_{1}<\sigma_{2}<\dots<\sigma_{N}$ denote the times at which a phase
change occurs in the augmented random process, and let $(\phi_{i})_{0\leq
i\leq N}$ denote the phases that are visited, i.e., $\phi_{0}=m+1,$ and
$\phi_{i}=\mathrm{phase}(S_{\sigma_{i}})$ ($1\leq i\leq N$). Then we have, for
$i\geq 1$:

The distribution of $\phi_{i}$ is given by

$\displaystyle\Pr\bigl{[}\phi_{i}=x\,\big{|}\,\phi_{i-1}\bigr{]}=\begin{cases}\frac{r}{r(\phi_{i-1}-1)+\Delta}&\text{
for }x\in[\phi_{i-1}-1],\\\\[8.61108pt]
\frac{\Delta}{r(\phi_{i-1}-1)+\Delta}&\text{ for }x=0.\end{cases}$

If $\phi_{i}>0$, then the color of the pivot at time $\sigma_{i}$ is a u.a.r.
element of $[r]$.

Consider one of the phases $\phi_{i}$ that are visited by the augmented random
process. We want to bound the _duration_ of the phase $\phi_{i}$, i.e. the
number $\sigma_{i+1}-\sigma_{i}$, from below. In general this duration could
be very short, so we introduce a suitable notion of a _good phase_. The
definition will guarantee that, when entering a good phase, all points of the
layer $\mathcal{L}_{r-1}$ will lie strictly below the current position; and
this property will in turn make it possible to derive a lower bound on the
duration of a good phase inductively.

######  Definition 5.3 ((good phases)).

Let $k\in[m]$. We say that $k$ is a _good phase_ of the augmented process if,
using the notation from Lemma 5.2,

$k$ is visited, so that $k=\phi_{j}$ for some $j$,

the pivot at time $\sigma_{j}$ has color $r$, and

the position $S_{\sigma_{j}}$ does not contain any point from the layer
$\mathcal{L}_{r-1}$.

Let the reader be warned that the above definition is weaker than one might
think at first: The only points that we take directly into account are those
from the two outermost layers $\mathcal{L}_{r}$ and $\mathcal{L}_{r-1}$. In
particular we allow $S_{\sigma_{j}}$ to contain points from other layers. When
reading on, it is useful to keep in mind one consequence of Lemma 4(c): The
phase of the current position can change only when pivoting a point from the
layer $\mathcal{L}_{r}$, i.e., a point that lies on one of the coordinate
axes. Consequently, pivots in lower layers can largely be ignored in our
analysis.

######  Lemma 5.4.

Let $1\leq k\leq m-1$. Then phase $k$ is a good phase with probability at
least $\frac{1}{r(\Delta+kr)}.$

######  Proof 5.5.

Let $j$ be the (random) largest index such that $\phi_{j-1}>k$. Then the
probability of (i) equals $\Pr\bigl{[}\phi_{j}=k\bigr{]}$, and using Lemma
5.2(a) we compute this probability to be $\frac{r}{rk+\Delta}$. Given (i),
Lemma 5.2(b) tells us that the probability of (ii) equals $1/r$.

Assume that (i) and (ii) hold. It remains to show that, in this case, (iii)
holds with probability at least $1/r$. We consider the position
$S_{\sigma_{j}-1}$ one time step before entering phase $k$. Using the same
notation as in Lemma 4, let $t_{i}\mathbf{e}_{i}$ denote the intersections of
$\mathrm{conv}(S_{\sigma_{j}-1})$ with the $i$th coordinate axis
($i=1,\dots,r$). Note that $t_{i}>k$ for all $i$, because phase $k$ has not
been entered yet at this time.

By Lemma 4 it is sufficient to give a bound for the event

$\displaystyle t_{i}\leq t_{r}\text{ for all }i=1,\dots,r-1.$ (13)

To this end, let $\tau$ denote the time that the point $t_{r}\mathbf{e}_{r}$
is pivoted, so that $S_{\tau}$ is the first position to include the point
$t_{r}\mathbf{e}_{r}$. Note that $t_{r}$ does not change in between time
$\tau$ and time $\sigma_{j}$; thus, if property (13) already holds at time
$\tau$, then by monotonicity (Lemma 4.1) it will still hold at time
$S_{\sigma_{j}-1}$. So assume that at time $\tau$ property (13) does not yet
hold, so that there are some “bad” indices $i$ with $t_{i}>t_{r}$. Let
$I\subseteq[r-1]$ denote the set of such bad indices, and let $\tau_{1}>\tau$
be the first time that another point of layer $r$ with phase $\leq t_{r}$ and
color contained in $I\cup\\{r\\}$ is pivoted. With probability at least
$\frac{|I|}{|I|+1}$, the color of this pivot is contained in $I$, in which
case the number of bad indices is reduced by $1$. Iterating this argument, the
number of bad indices will be reduced down to zero with probability at least

$\displaystyle\frac{|I|}{|I|+1}\cdot\frac{|I|-1}{|I|}\cdots\frac{1}{2}=\frac{1}{|I|+1}\geq\frac{1}{r},$

as desired.

When the augmented process enters a good phase $k$, then all the points of the
layer $\mathcal{L}_{r-1}$ lie strictly below the current position. We restrict
our attention to the hyperplane $x_{r}=-m^{3}$ that contains all the points
from $A(r,m)\setminus\mathcal{L}_{r}$: Due to Lemma 4, the augmented process
within this hyperplane behaves like the augmented process on the lower-
dimensional construction $A(r-1,m)$. However, the process might at any point
pivot one of the points $\\{p\in\mathcal{L}_{r}\,\mathrel{\mathop{\mathchar
58\relax}}\,\text{phase}(p)<k\\}$, and as soon as this happens, the good phase
$k$ already ends. We can account for this by adjusting the parameter $\Delta$
and we obtain the following lemma.

######  Lemma 5.6.

For every $1\leq k\leq m-1$, if phase $k$ is visited and if it is a good
phase, then its expected duration is bounded from below by the best-case111The
term “best-case” here, as well as in Theorem 5.7, refers to the action of the
adversary who chooses the starting position of the augmented process. The
intended meaning is for the lower bound in Theorem 5.7 to hold for any choice
of starting position. expected duration of the process
$\mathcal{R}^{\Delta+(k-1)r}_{r-1,m}$.

######  Theorem 5.7.

Let $t^{\Delta}_{r,m}$ denote the best-case expected duration of the augmented
process $\mathcal{R}^{\Delta}_{r,m}$. Then we have

$\displaystyle
t^{\Delta}_{r,m}\geq\frac{1}{r!^{3}}\cdot\mathinner{\left(\ln(m+{\textstyle\binom{r}{2}}+\Delta)-\ln(1+{\textstyle\binom{r}{2}}+\Delta)\right)}^{r}.$

######  Proof 5.8.

By induction on $r$. For $r=1$ the statement is easy to verify; let now $r\geq
2$. Combining Lemmas 5.4 and 5.6 we obtain

$\displaystyle t^{\Delta}_{r,m}$
$\displaystyle\geq\sum_{k=1}^{m-1}\frac{1}{r(kr+\Delta)}\cdot
t^{\Delta+kr-1}_{r-1,m}.$ (14)

The induction hypothesis gives, for $1\leq k\leq m-1$,

$\displaystyle t^{\Delta+kr-1}_{r-1,m}$
$\displaystyle\geq\frac{1}{(r-1)!^{3}}\cdot\mathinner{\left(\ln(m+{\textstyle\binom{r-1}{2}}+\Delta+kr-1)-\ln({\textstyle\binom{r-1}{2}}+\Delta+kr)\right)}^{r-1}.$
$\displaystyle=\frac{1}{(r-1)!^{3}}\cdot\mathinner{\Bigl{(}\ln(m+{\textstyle\binom{r}{2}}+\Delta+kr-r)-\ln(\underbrace{1+{\textstyle\binom{r}{2}}+\Delta+kr-r}_{=\mathrel{\mathop{\mathchar
58\relax}}f(k)})\Bigr{)}}^{r-1},$ (15)

where we have used Pascal’s rule to handle the binomial coefficients. Plugging
(15) into (14) and furthermore using the simple inequality $kr+\Delta\leq
f(k)$, we thus obtain

$\displaystyle t_{r,m}^{\Delta}$
$\displaystyle\geq\frac{1}{(r-1)!^{3}}\sum_{k=1}^{m-1}\frac{1}{rf(k)}t^{\Delta+kr-1}_{r-1,m}$
$\displaystyle\geq\frac{1}{(r-1)!^{3}}\int_{x=1}^{m}\frac{1}{rf(x)}{\mathinner{\left(\ln(m+{\textstyle\binom{r}{2}}+\Delta+rx-r)-\ln
f(x)\right)}^{r-1}}\operatorname{d\\!}{x}$ (16)
$\displaystyle\geq\frac{1}{(r-1)!^{3}}\int_{x=1}^{1+(m-1)/r}\frac{1}{rf(x)}{\mathinner{\left(\ln(m+{\textstyle\binom{r}{2}}+\Delta)-\ln
f(x)\right)}^{r-1}}\operatorname{d\\!}{x}$ (17)
$\displaystyle=\frac{1}{r!^{3}}\cdot\Bigl{[}\,-\mathinner{\left(\ln(m+{\textstyle\binom{r}{2}}+\Delta)-\ln
f(x)\right)}^{r}\leavevmode\nobreak\ \Bigr{]}_{x=1}^{1+(m-1)/r}$
$\displaystyle=\frac{1}{r!^{3}}\cdot\mathinner{\left(\ln(m+{\textstyle\binom{r}{2}}+\Delta)-\ln(1+{\textstyle\binom{r}{2}}+\Delta)\right)}^{r},$

which proves the theorem. Note that the integrand in (16) is positive
everywhere, so we were justified to restrict the range of the integral in
(17), effectively dropping negligible terms.

Theorem 5.1 now follows from Theorem 5.7 by setting $\Delta=0$.

##  6\. Conclusion

### Outlook.

It remains an open question whether one can obtain good upper bounds for the
expected number of steps performed by Random-Edge when the corank is bounded.
The only non-trivial result at this point remains the $O(\log^{2}n)$ bound for
the case $r=2$, which was settled in [GaertnerSTVW'03] and which the author
has studied further in a more abstract setting in [Milatz'17]. It might well
be that there is a threshold behavior in the sense that Random-Edge performs
well for slowly growing $r$, and badly for quickly growing $r$. Finally, the
same questions can be asked for other simplex pivoting rules that might be
easier to analyze.

### Remark on the dependence on $r$.

The leading factor $1/r!^{3}$ in Theorem 5.7 is rather small. Due to the
results by Friedmann et al. [FriedmannHZ'11], this factor cannot in general be
tight. Unfortunately, an improvement seems to be beyond the scope of our
method. For the interpretation of Theorem 1.2 some readers may find it
interesting to pick a value of $r$ that depends on the number of facets $n$.
Not every such choice of $r$ leads to a meaningful bound; but it is possible
to choose $r=r(n)=\ln^{1/s}\mathinner{\left(1+4n/r^{4}\right)}$ with any
$s>3$, which leads to a lower bound of the form $(\ln
n)^{\displaystyle\Omega(\ln^{1/s}n)}$ for the directed random walk on a grid
polytope with $n$ facets and corank $r(n)$.

### Acknowledgements.

I would like to thank Bernd Gärtner, Ahad N. Zehmakan, Jerri Nummenpalo and
Alexander Pilz for many useful suggestions and discussions.

## References

  * [1] Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, and Eli Upfal.  The worst-case running time of the random simplex algorithm is exponential in the height.  Inf. Process. Lett., 56(2):79–81, 1995.
  * [2] Stefan Felsner, Bernd Gärtner, and Falk Tschirschnitz.  Grid orientations, $(d,d+2)$-polytopes, and arrangements of pseudolines.  Discrete & Computational Geometry, 34(3):411–437, 2005.
  * [3] Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick.  Subexponential lower bounds for randomized pivoting rules for the simplex algorithm.  In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 283–292, 2011.
  * [4] Bernd Gärtner, Martin Henk, and Günter M. Ziegler.  Randomized simplex algorithms on klee-minty cubes.  Combinatorica, 18(3):349–372, 1998.
  * [5] Bernd Gärtner, Walter D. Morris, Jr., and Leo Rüst.  Unique sink orientations of grids.  Algorithmica, 51:200–235, 2008.
  * [6] Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Pavel Valtr, and Emo Welzl.  One line and $n$ points.  Random Structures & Algorithms, 23(4):453–471, 2003 (preliminary version at STOC 2001).
  * [7] Branko Grünbaum.  Convex polytopes.  Springer, New York, 1967/2003.
  * [8] Kathy Williamson Hoke.  Completely unimodal numberings of a simple polytope.  Discrete Applied Mathematics, 20(1):69–81, 1988.
  * [9] Volker Kaibel, Rafael Mechtel, Micha Sharir, and Günter M. Ziegler.  The simplex algorithm in dimension three.  SIAM Journal on Computing, 34(2):475–497, 2005.
  * [10] Gil Kalai.  A subexponential randomized simplex algorithm.  In Proc. 24th ACM Symposium on Theory of Computing, pages 475–482, 1992.
  * [11] Jiří Matoušek and Tibor Szabó.  Random edge can be exponential on abstract cubes.  Advances in Mathematics, 204(1):262–277, 2006.
  * [12] Peter McMullen.  On the upper-bound conjecture for convex polytopes.  Journal of Combinatorial Theory, Series B, 10(3):187–200, 1971\.
  * [13] Malte Milatz.  Directed random walks on polytopes with few facets.  Electronic Notes in Discrete Mathematics, 61:869–875, 2017.  The European Conference on Combinatorics, Graph Theory and Applications (Eurocomb ’17).
  * [14] Julian Pfeifle and Günter M. Ziegler.  On the monotone upper bound problem.  Experimental Mathematics, 13(1):1–12, 2004.
  * [15] Robert J. Plemmons.  M-matrix characterizations. I—Nonsingular M-matrices.  Linear Algebra and its Applications, 18(2):175–188, 1977.
  * [16] Francisco Santos.  A counterexample to the Hirsch Conjecture.  Annals of Mathematics, 176:383–412, 2012.
  * [17] Falk Tschirschnitz.  LP-related properties of polytopes with few facets.  PhD thesis, ETH Zürich, 2003.