Sampling lattice polytope vertices

[ruescasd]

Hello all,

Ive been looking at polymake (looks great) and have a simple question regarding a specific use case.

I have a lattice polytope and I want to compute some function on its vertices (specifically, I want to calculate probabilities over some properties of the vertices). Because the number of vertices is potentially huge, it is infeasible to use $p->VERTICES to list all the vertices and then compute on them.

So my question is, is there a way to sample randomly from vertices in polymake? If not, is there some way to use existing functionality to do this?

Many thanks,

David

PS. more details:

I want to calculate a weighted sum of the value of one of the dimensions of the polytope over all vertices.
The weight is given by the binomial coefficients of the variables for some fixed values n. For example, lets say a solution (vertex) is

(1, 3, 5, 2, 6)

and I am interested in the first dimension. The value at this point would be something like

1 * (n1 choose 1) * (n2 choose 3) * (n3 choose 5) * (n4 choose 2) * (n5 choose 6)

If there were two points

(1, 3, 5, 2, 6)
(3, 4, 1, 2, 5)

the sum would be

1 * (n1 choose 1) * (n2 choose 3) * (n3 choose 5) * (n4 choose 2) * (n5 choose 6) +
3 * (n1 choose 3) * (n2 choose 4) * (n3 choose 1) * (n4 choose 2) * (n5 choose 5)

and so on. (n1..n6 are given constants)

I have looked at latte and using ehrhart polynomials, but encoding binomial coefficients in the monomials for the weight function seems impossible.

[joswig]

I am not sure if I get it completely. There seem to be at least two questions in your post.

(1) Random vertices. Well, this depends on how your polytope is given. If you have the vertices then the client rand_vert does the trick. If you have an inequality description than random sampling should probably be done by solving a linear program (with respect to a random objective function). The latter is not implemented; but this should not be too hard by combining code from rand_sphere and, say, to_lp_client.

(2) I guess you want to compute like this?

Code: Select all

> @v=(1, 3, 5, 2, 6); > @n=(5, 6, 7, 8, 9); > $x = $v[0]; for (my $i=0; $i<scalar(@v); ++$i) { $x *= binomial($n[$i],$v[$i]) }; print $x; 4939200

[ruescasd]

Hi Josh thanks for your response

Perhaps I was not very clear, my question is about random vertex sampling because the number of vertices that I expect will be in the polytope will be too large to just calculate over all of them, as in your example in 2), or to use rand_vert.

My polytope is given as a set of equalities of the form

a1 + b1 + c1 + ... + = k1
a2 + b2 + c2 + ... + = k2
.
.
a1 + a2 + a3 + .... + = ka
b1 + b2 + b3 + .... + = kb
.
.

where all the variables and constants k are integers. I had thought about using a random objective function, but I am not sure the resulting vertices will be uniformly distributed, which is something I need to estimate probability distributions over the vertices (thats what the calculation is doing)

[joswig]

Of course, picking a random objective function typically will not give you a uniform distribution on the vertices. However, there is no way to get at this without knowing the vertices. If you only have an exterior description it is #P-hard to tell how many vertices there are.

[ruescasd]

Thanks again Josh.

I am currently looking at hit and run as described here http://www-math.ucdenver.edu/~hgreenbe/ ... etal04.pdf, as well as markov chains as described here ftp://ftp.stat.duke.edu/pub/WorkingPapers/04-12.pdf for monte carlo sampling on vertices