There is a surprising number of posts asking about the uniform sampling of convex polytopes (e.g. 1, 2, 3), and an equally surprising number of non-answers (e.g. a, b).
From what I have read, this seems to be a difficult problem; and known solutions consist in partitioning the polytope into a collection of simplices, select one randomly, and sample a uniformly random point from it. That is assuming that we know the vertices of the polytope in the first place (otherwise the problem is apparently NP-hard?).
From what I know, sampling uniformly random points from a d-dimensional simplex with d+1 known vertices is done in two steps:
- Sample d+1 weights from a Dirichlet distribution with parameters $(\alpha_k = 1)_{k=0..d}$
- Compute the corresponding weighted sum of vertices
Assuming this is correct, my question is: why can we not apply the same method to sample any convex polytope uniformly randomly? I.e. by computing a weighted sum of its vertices, with weights sampled from a Dirichlet distribution.
Is it because it has not been proven that this would result in a uniform distribution, or because there are known cases where it does not?
Well, it seems the short answer is: "because it doesn't work".
It is still unclear to me why that is; and I should probably first try to understand why it works in the case of a simplex. But trying the same method on regular polygons yields a sampling density that is not uniform: