Uniform sampling of points on a simplex

Solution 1:

Mathematically, you are trying to uniformly sample points on a simplex, which in turn is also equivalent to sampling points from a Dirichlet distribution and then normalizing.

Here's how to see all this: take the unit interval and pick uniformly at random and independently $N-1$ points. These points partition the unit line into segments, so take your $x_i$ to equal the lengths of the segments. Basically, to implement this, you draw the $N-1$ points at random and then you sort them in increasing order, which gives you a kind of Beta distribution.

If you need to program this, here's one efficient way of doing it without sorting:

1) Generate $N$ independent points $E_i$ from a an exponential distribution by drawing $U_i$ from a uniform distribution on $[0,1]$ and then compute the negative logorithm: $E_i:=-\log(U_i)$.

2) Sum all samples to get $S:=\sum_{i=1}^{N}E_i$.

3) The vector $x:=(x_1,\ldots,x_{N})$, where $x_i=E_i/S$ is uniformly distributed in your space.