How to sample points from a bounded polytope?

38 Views Asked by At

I have a bounded polytope $C \subset \mathbb{R}^n$ characterized by the following restraints: $$ x \in C \Leftrightarrow \sum_{i=1}^n x_i = 1 \text{ and } Ax \leq b$$ for some matrix $A \in \mathbb{R}^{n \times n}$ and vector $b \in \mathbb{R}^n$.

Is it possible to sample a uniform distribution of points of the set $C$ somehow?

My only idea so far is to get a starting point $x_0 \in C$, then perturb it $x_{i+1} = \frac{x_{i} + \varepsilon}{|x_{i} + \varepsilon|}$ and keep it if $x_{i+1} \in C$, else get another perturbation vector $\varepsilon$. This trajectory would be uniformly distributed if one samples enough points, but the computation of the next $x_{i+1}$ might be very high.