How to uniformly sample a sorted simplex

Question

I am looking for an algorithm to uniformly generate a descending array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should satisfy:

x + y + z = 1
0 <= x <= 1
0 <= y <= 1
0 <= z <= 1
x >= y >= z

My guess is all i have to do is uniformly sample a simplex (Uniform sampling from a simplex), and then sort the elements. But i'm not sure whether the result sampling algorithm is uniform.

Also, rejection sampling is not ideal for me, because i'll use this for high dimension.

Answer 1

Yes, all you have to do is to uniformly sample a simplex, and then sort the elements, under the assumption that the given distribution on the simplex is invariant under the permutation of the coordinates and the probability of a 0-measure set is 0.

That assumption holds often by default. Hopefully it holds in your situation. otherwise, a different sampling method or some preprocessing/postprocessing may be needed.

Here is a simple argument that should convince you that uniformly sampling and then sorting results in uniform sampling, given that assumption. Suppose we get a sample $x<y<z$ in the end. It may come from any one of the six kinds of original sampling, $(x,y,z)$, $(x,z,y)$, $(y,z,x)$, $(y,x,z)$, $(z,x,y)$ and $(z,y,x)$. The original sampling is uniform everywhere, and hence uniform on a neighborhood of these six points. Combining six identical (small) disjoint neighborhoods of them and dividing by 6, we see that sampling and sorting is also uniform on a neighborhood of $(x,y,z)$. Since $(x,y,z)$ can be any given point with distinct coordinates and the set of all points with at least two equal coordinates has measure 0, the sampling and sorting is uniform on the whole sorted simplex.

A rigorous proof along the same line of reasoning can be written if we want to be more formal.