This paper describes an approach to the random sampling of lattice polytopes. The lattice polytopes we are interested in are contained in the hypercube [0; k]d and we refer to them as lattice (d; k)-polytopes. Our approach consists in using a Markov chain whose space of states is the set of all d-dimensional lattice (d; k)-polytopes and whose transitions add or delete vertices following simple, well-de ned rules. We prove that this Markov chain provides a uniform random sampler of lattice (d; k)-polytopes, and give a lower bound on the mixing time. We also present a number of experimental results on a selection of values of k in the 2-dimensional case.
of convex polyominoes from [BDJM13] could be modi ed in order to obtain a Boltzmann sampler for lattice polygons. Also, note that in [DDT14], the authors give a random generator of convex polygons. However their setup is di erent from ours as they deal with polygons contained in a disc, whose vertices are not restricted to a lattice. Another easier case is when k = 1. Indeed, any set of lattice points contained in [0; 1]d is the vertex set of a lattice (d; 1)-polytope. Thus, an ad-hoc algorithm can be designed that samples random sets of points with binary coordinates and rejects the resulting polytopes when they are not d-dimensional.
The random sampler we propose results from a Markov chain, whose space of states is the set of all ddimensional lattice (d; k)-polytopes. Its stationary distribution is uniform for any d 2 and positive k. The transitions in this Markov chain, and the resulting random sampler can be described informally as follows. Given a lattice (d; k)-polytope P with vertex set V, performing a transition will rst consist in randomly choosing a lattice point x in [0; k]d, and then proceeding according to the placement of x with respect to P . If x belongs to V, then P will be replaced by the convex hull of Vnfxg, thus removing x from P . If x does not belong to V and V [ fxg is precisely the vertex set of its convex hull, then P will be replaced by the convex hull of V [ fxg, thus inserting x in P . If none of these two cases occurs, then P will not be a ected. These operations are elementary, yet they raise very interesting geometric questions as, for instance, whether they always allow to transform any d-dimensional lattice (d; k)-polytope into any other.
In order to sample a uniform random lattice (d; k)-polytope, we will run a random walk on our Markov chain until we are close enough to the stationary distribution. The e ciency of the sampler is related to the time needed for the walk to get close enough to the stationary distribution. In order to evaluate it, we need to determine the rate of convergence of the Markov chain to the stationary distribution as a function of the geometry and the size of the state space. Doing so is often a di cult problem (see for instance [CDF11, MDBM01]).
A formal de nition of our Markov chain and of the resulting sampler shall be given in Section 2. In the sequel, we provide both theoretical and experimental results regarding the behaviour of this Markov chain. Our main result is that the random sampler built from the Markov chain for lattice (d; k)-polytopes is uniform. This is shown in Section 3. Section 4 presents a general lower bound on the mixing time of our Markov chain. We conclude by providing experimental results and discussing them in Section 5. 2
We will introduce two variants of our Markov chain. The rst one contains a minimal set of rules, su cient to obtain a uniform stationary distribution. It turns out that the proof of the irreducibility of this variant raises interesting geometric questions. The second one contains an additional rule which simpli es this proof, as we shall see in Section 3. For both chains, the space of states is the set of all d-dimensional lattice (d; k)-polytopes, for xed d and k. Some e ort will be needed in order to enforce the requirement that all the states of our Markov chains are polytopes of dimension exactly d. The transition rules of our Markov chains are de ned as local operations on lattice (d; k)-polytopes. These rules consist in adding a single vertex to such a polytope or to remove a vertex from it. Consider a d-dimensional lattice (d; k)-polytope P and denote by V its vertex set. Consider a lattice point x in [0; k]d which, we assume has been uniformly drawn from all possible lattice points in [0; k]d. The transition from P that corresponds to the chosen lattice point x goes as follows.
If x is contained in P but is not a vertex of it (i.e. x 2 P nV) then the chain will loop on P . In other words, the current state is una ected.
If x is a vertex of P (i.e. x 2 V), then { If the convex hull Q of Vnfxg is d-dimensional, the transition goes from P to Q. Note that if Q were (d 1)-dimensional, then P would be a pyramid (with apex x) over Q. In this case, the transition from P to Q would be impossible because it would exit .
{ Otherwise, we loop on P .
{ If V [ fxg is precisely the vertex set of its convex hull, then the transition goes from P to the convex hull of V [ fxg. { Otherwise we loop on P .
By the above procedure, sampling a random lattice (d; k)-polytope consists in generating a random walk on the Markov chain until we are close enough to the stationary distribution. Thereby, the resulting random sampler for lattice (d; k)-polytopes is given by Algorithm 1.
Input: the dimension d, the size k of the hypercube
Output: a random lattice (d; k)-polytope 1 sample a random lattice (d; k)-simplex P with vertex set V 2 while we are not close enough to the stationary distribution do 3 generate a random lattice point x in [0; k]d 4 if x 2 V then 5 if conv(Vnfxg) is d-dimensional then 6 P conv(Vnfxg)
In the other variant of our Markov chain, we introduce an additional rule when P is a simplex: if the chosen random lattice point x is a vertex of P , we may move that vertex to another lattice point instead of having a loop on P in our Markov chain. More precisely, in this case we generate a new random lattice point y in [0; k]d and compute the convex hull Q of [Vnfxg] [ fyg. If Q is d-dimensional, the transition goes from P to Q, otherwise we loop on P . Note that, since P is a simplex, [Vnfxg] [ fyg is precisely the vertex set of Q when Q is d-dimensional. With this additional transition rule, we obtain Algorithm 2. Algorithm 2: Random sampling of a lattice (d; k)-polytope
Input: the dimension d, the size k of the hypercube
Output: a random lattice (d; k)-polytope 1 sample a random lattice (d; k)-simplex P with vertex set V 2 while we are not close enough to the stationary distribution do 3 generate random a lattice point x in [0; k]d 4 if x 2 V then 5 if jVj = d + 1 then 6 generate a random lattice point y in [0; k]d 7 if conv([Vnfxg] [ fyg) is d-dimensional then 8 P conv([Vnfxg] [ fyg) It is well known that an irreducible, aperiodic, and symmetric Markov chain converges to the uniform distribution [LPW09]. In this section we prove that all these properties are satis ed by our Markov chains (reminders on their de nitions will be given in the proof as well). Thus, we show that the two variants of our d-dimensional lattice (d; k)-polytopes sampler are uniform.
aperiodic and symmetric.
2 and for all positive k, the Markov chain corresponding to Algorithm 1 is irreductible, Proof. Three properties have to be veri ed, thus this proof will be done in three steps. Let P and Q be in and let V be the vertex set of P . i Irreducibility. A Markov chain is irreducible when all of its states can be reached from any other state. In other words the graph (d; k) underlying the Markov chain is connected. The vertex set of (d; k) is and there is an edge in this graph between any two vertices that are related to one another by a single transition. The complete proof for the connectedness of (d; k) is quite involved and due to its length, we omit it here. This proof can be found in [DPR]. An important piece of the proof consists in showing that, given a lattice (d; k)-simplex S, there always is at least one lattice point in [0; k]d that can be inserted as a new vertex in S. It turns out that proving this seemingly simple statement is quite tricky. ii Symmetry. In order to prove the symmetry one needs to show that the probability P(P; Q) to move from P to Q in a single step is equal to the probability P(Q; P ) of performing the opposite step.
By our transition rules, for any P 6= Q we have:
P(P; Q) = P(Q; P ) =
0 otherwise.
( (k+11)d ; if Q is the convex hull of Vnfxg or of V [ fxg, where x 2 [0; k]d, iii Aperiodicity. In order to prove that the chain is aperiodic, one needs to show that each state in has period 1. By de nition, the period of a state P is gcd(T (P )), where T (P ) is the set of the return times in P . Since for an irreductible chain, all the states of have the same period, then we need to nd a state P such that gcd(T (P )) = 1. Now recall that the polytope resulting from a transition in our Markov chain must remain d-dimensional. In particular, if one picks any vertex of a d-dimensional simplex P , this vertex cannot be removed, and we get a loop in our Markov chain. Since there exist d-dimensional lattice (d; k)-simplices for all d 2 and positive k, this shows that, at some state P 2 we have a positive probability to get back to P from P in one step. Hence, 1 2 T (P ) and gcd(T (P )) is equal to 1.
aperiodic and symmetric.
2 and for all positive k, the Markov chain corresponding to Algorithm 2 is irreductible, Proof. We proceed the same way as we did in the proof of Theorem 1.
i Irreducibility. The proof still relies on the fact that one can always nd a transition path between two simplices, yet the \moving a vertex" rule allows us to choose one vertex of the starting simplex and move it directly to a vertex of the desired simplex. Indeed, recall that by de nition, a d-dimensional simplex is the convex hull of a set of d + 1 a nely independent points. Therefore, one can transform any P 2 into a simplex by consecutive deletions of its vertices, until there only remains d + 1 of them. With an analog reasoning, by a succession of addition of vertices, we always have a transition path from a simplex to a lattice (d; k)-polytope. The graph of the Markov chain remains connected, hence the Markov chain is irreducible. ii Symmetry. Here the only di erence from the symmetry proof in Theorem 1 is that now we may have a one step transition between two simplices. It occurs when they only di er by a single vertex. Then, let S and S0 be two simplices in . If they only di er by a single vertex, then all the vertices of S belong to S0 apart from a vertex x, and all the vertices of S0 belong to S apart from a vertex y. The transition goes from S to 1 1 S0 consists in choosing x, with a (k+1)d probability, and then to move it to y with a (k+1)d probability. The same argument allows to treat the transition from S0 to S. Thus,
P(S; S0) = P(S0; S) = 8 1 < (k + 1)2d ; if S and S0 di er by a single vertex, :0 otherwise. iii Aperiodicity. To prove the aperiodicity, it is necessary and su cient to nd a lattice (d; k)-polytope with a positive probability to loop. Let us consider a simplex S with vertex set V and a lattice point x 2 [0; k]d. If x is chosen among the vertices of S, then we have to redraw a point y 2 [0; k]d where we decide to move x. The cases when we have a loop on S are: either y and x are the same point, or conv([Vnfxg] [ fyg) is not a 1 d-simplex. Note that the probability to choose x again is (k+1)d . Therefore,
P(S; S)
d + 1 1 (k + 1)d (k + 1)d > 0:
chain remains aperiodic. has the same period 1. Hence, the
It is an immediate consequence of Theorem 1 and of Theorem 2 that the two variations of our Markov chain have a uniform stationary distribution. Thus, the lattice (d; k)-polytopes obtained from both samplers are picked uniformly from . We have the following theorem.
Theorem 3. The random samplers described in Algorithm 1 and in Algorithm 2 are uniform random samplers for d-dimensional lattice (d; k)-polytopes.
Recall that the total variation distance is a distance measure between probability distributions [LPW09]. The e ectiveness of the sampler is given by the number of steps it takes until one is close enough to the stationary distribution on , meaning that the total variation distance between the current distribution and the stationary one is less than a small positive quantity ". This number of steps is called the mixing time of the Markov chain, denoted tmix("). That is, the quicker the Markov chain mixes, the more e ective the resulting sampler is. Obtaining an accurate estimation of the mixing time is often a di cult problem. In order to obtain a lower bound, one may use the diameter of the graph of the Markov chain. This diameter is the length of the longest geodesic walk on the chain between any two states. In our case, that length is bounded below by the di erence between the largest number of vertices of a d-dimensional lattice (d; k)-polytope and the number of vertices of a d-dimensional simplex.
The largest number of vertices of a lattice polygon contained in a disk or a square has been studied in [Av95, Thi91, BB91]. Deza, Manoussakis and Onn have generalized this result to higher dimensions by describing lattice (d; k)-polytopes whose diameter is large and conjecturally maximal [DMO18]. According to [Av95], the largest number of vertices of a lattice polygon contained in [0; k]2 is (1) 12
We therefore immediately obtain the following lower bound on the mixing time of our sampler in the 2dimensional case from equation (7.3) in [LPW09].
Theorem 4. Assume that d = 2. For any " > 0, there exists c > 0 such that
For the case of higher dimensions, Barany and Larman gave bounds on the number of faces of each dimension of a lattice polytope contained in the the d-dimensional ball of radius r centered at the origin as a function of r and d [BL98]. In particular they provide bounds on its number of vertices. Up to a translation and nding the right constant, Theorem 1 in [BL98] also provide us the following lower bound on the mixing time.
2 and for any " > 0, there exists c > 0 such that
We have carried out a number of experiments in order to get an estimation of the actual mixing time of the sampler corresponding to Algorithm 1 in the 2-dimensional case. These results are presented in Section 5. 5
The empirical estimations we obtained are based on ergodic theory. This theory requires the studied Markov chains to be irreducible and positive recurrent. These properties hold in our case since we have a nite space of states [LPW09]. Ergodic theory states that the average of any real-valued function on the states over a long enough walk is the same as the expectancy at the stationary distribution, see Theorem 4.16 in [LPW09]. Here the function can be any quantity we can measure on lattice (d; k)-polytopes. The process is the following: we run a long walk on the Markov chain, evaluate the quantity on each state we visit, then calculate the average value of this quantity over the whole run. Our results are reported in Figure 2. One can see that the average number of vertices of a polygon seems to stabilize after 100 thousand steps (resp. 1 million and 10 million) when k 20 (resp. k 30 and k 50). We also measured the average area of a polygon after a 10 million steps walk and show it on the right of the same gure. Our measures suggest that
E[n] 6
and E[a] k 2 2=3 3 2
k ; 4 where E[n] and E[a] are respectively the expectancy of the number of vertices and the area of a polygon at the stationary distribution.
The coupling method is another way to estimate the mixing time. The coupling is more general and often used to bound rates of convergence to stationarity as well. It consists in running two walks on the Markov chain. 100 thousands steps 1 milion steps 10 milion steps
Maximal Diameter [Av95] The coupling result on Markov chains tells us that once two coupled walks are at the same state, they will both move following the stationary distribution with high probability. Note that the walk may have been already very close to the stationary distribution much earlier. Our computations allowed us to get an empirical upper bound on the mixing time in the 2-dimensional case for k up to 6, the computation time becoming prohibitive for larger values of k. Table 1 presents execution times for this method and the number of steps needed for the two walks to meet. As one can see, the required number of steps increases quickly. This suggests that the coupling method may not provide sharp estimations of the mixing time for our sampler.
Dragan Acketa, Jovisa Zunic. On the maximal number of edges of convex digital polygons included into an m m-grid. Journal of Combinatorial Theory A, 69:358-368, 1995.
Antal Balog, Imre Barany. On the convex hull of the integer points in a disc. In Proceedings of the Seventh Annual Symposium on Computational Geometry, pages 162-165, 1991.
Ste en Borgwardt, Jesus De Loera, Elisabeth Finhold. The diameters of transportation polytopes satisfy the Hirsch conjecture. Mathematical Programming, to appear.
Olivier Bodini, Ph Duchon, Alice Jacquot, L Mutafchiev. Asymptotic analysis and random sampling of digitally convex polyominoes. In International Conference on Discrete Geometry for Computer Imagery, pages 95-106. Springer, 2013. [BDSEHN14] Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand, Nicolai Hahnle, Martin Niemeier. On sub-determinants and the diameter of polyhedra. Discrete and Computational Geometry, 52:102115, 2014. [DPR] [KK92] [KO92] [KW67] [LPW09] [MDBM01] [Nad89] [San12] [Thi91] [Zie95]