# Sampling from a Convex Body with Many Extremal Points

Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an efficienct' way. In my setting, I have $n$ moderate (e.g. $n \approx 500$) but $N$ very large (e.g. $N \approx 2^{n^{2}}$).

I am aware that there is a great deal of work by Lovasz et. al. on using hit-and-run algorithms for doing this type of sampling. Unfortunately, to my knowledge that algorithm is impractical in my setting: when $N$ is very large compared to $n$, the cost of running the algorithm is dominated by the (large) cost of finding the boundaries of the convex body along a slice. In particular, this work suggests that around $n^{3}$ steps of a Markov chain are required to get a single good sample, but each step still seems to require at least $N$ operations.

I do have one advantage in this setting: I can sample a random element of $p_{1}, \ldots, p_{N}$ quite quickly (e.g. in time $O(\log(N))$. I thought that perhaps a "nonreversible" hit-and-run sampler might be possible, but so far don't have anything particularly general in that direction.

Thanks for any help!

EDIT: In response to Douglas Zare's comment below, I'll also add:

1. It is certainly too much to ask for a sampling algorithm that is always' good in the above setting. I think I'll settle for a somewhat general algorithm that is`sometimes' good. As a baseline check on generality, it probably shouldn't fail miserably on e.g. the simplex. As a baseline check on goodness, I probably want something that is at least plausibly subexponential in $n$ and $\log(N)$.
2. The examples that I care most about are moderately nice - e.g. there are $k$-transitive actions on the vertices for $k$ pretty big. So I feel at least moderately optimistic that algorithms that sometimes work given this data will probably work in my setting.
-
I think you need more assumptions to hope to be able to sample uniformly. You can define a distribution so that with probability about $1/2$ the convex hull is large, and with probability $1/2$ the convex hull is small, and you won't be able to rule out a large convex hull without checking almost all points. – Douglas Zare Mar 24 '14 at 6:23
Thank you! Some changes to the question above. – qtrs Mar 24 '14 at 11:51
Not nearly as fast as you ask for, but you can approximate the convex hull by the hull of a smaller, possibly random subset of the points. $e^{cn}$ should suffice for a good approximation. – Omer Mar 25 '14 at 16:29
Dear Omer, thanks for the comment. We tried doing a few things that seem to be in this spirit, like choosing $k > n$ points and sampling from the associated convex body. The result is biased, though in a way that is easier to understand than the nonreversible version: a point has density proportional to the number of size-$k$ convex bodies containing it. If the body has a lot of symmetry, maybe there is no bias. Otherwise, it wasn't obvious to me how to get around the bias. Is the claim that, for $k>e^{cn}$, most convex hulls of $k$-sets of extreme points cover most of the target? – qtrs Mar 25 '14 at 17:10
(Sorry for the rushed ending - ran out of characters.) In any case, it would be really exciting to me if something like that were often true. As mentioned by Douglas, it can't be true in general since adding $2^{n}$ points can completely change the full body, but maybe it is true for nice enough targets. – qtrs Mar 25 '14 at 17:10