random point in a convex polyhedral region

Question

How does one effectively generate a uniformly distributed random point in some bounded convex polyhedral region R in a Euclidean space? If codimension is zero I could surround the region with a rectangular region and generate point in the rectangular region rejecting it, if it is not in R. This is not very efficient and does not work, if codimension is positive.

Typical example would be: generate uniformly distributed random (p_1,...,p_n) in a simplex, that is p_i>=0, for all i and p_1+...+p_n=1.

Answer 1

If you have a subspace of codimension k, that means your convex polytope is defined by some number of inequalities and k independent equalities. So you can still use modified rejection sampling:

1. Find n-k independent variables p_1 through p_{n-k}.
2. Compute the possible ranges for those variables
3. Sample each variable.
4. Compute p_{n-k+1} through p_n
5. Accept if it's within your simplex, else reject and repeat.

I'm fairly sure this is still uniform because the dependent variables are related linearly to the independent ones and so mumble Jacobian mumble linearity, but I can't quite prove it.