algorithm to select Uniformly from S(N)

Algorithm to select f∈S(N)

Use the computer's RANDOM function to select N-1 points in ]0,1[. These partition [0,1] into N subintervals. Take the lengths of those subintervals as the f(i).

Explanation

Although the visualisation of S(N) as a simplex is geometrically appealing, it's easier to put it to the back of the mind and to think, instead, in terms of the above diagram.

Firstly ask the question "What is meant by 'uniformly select from...' "?

Superficially, this means that all distributions should have the same probability of selection: except that that doesn't make sense other than in the trivial sense that each has a probability of selection equal to zero because a single distribution defines a set of measure zero.

What the question must surely be asking for is the probability of selecting from a neighborhood of a distribution, not the probability of selecting the distribution itself. In terms of the above diagram, a neighbourhood of a distribution would be formed by a selection of (N-1) non-intersecting intervals, placed around the points representing that distribution. The requirement for uniformity would then be asking that the selection by the RANDOM function of one point in each interval should depend upon the lengths of those intervals but not on their positions.

But that's precisely what we have. Because the RANDOM function is the uniform distribution, we could slide the intervals to the left and to the right, as we wished, without affecting the probabilities in any way.

All we have to do is make the intervals so small that we can move them as close to 0 and 1, or to each other, as we wish. To do this, we quantify 'as close as we wish' by ε and set the total length of the intervals to be less than that by giving each interval a length less than ε/(N-1).

And that's all there is to it.