Sampling the simplex

[jalex]

Since choosing a random point from an N-dimensional simplex space
is equivalent to the problem of randomly partitioning
the interval [0,1] into N pieces, we can concentrate on 
the latter problem.

Here's a proof that Russell's algorithm, posted on 9 Oct 1999,
generates an unbiased random partition of [0,1] (taken from _An
Introduction to Probability Theory and Its Applications, vol.2_,
William Feller, 1966, pg. 73).

Let X1,...,Xn be n points chosen independently and at random from
the intervale [0,1].  Let X(1),...,X(n) denote the same points
rearranged in increasing order.  

Now, the sample space of (X1,...,Xn) is the n-dimensional unit cube C.
The sample space of (X(1),...,X(n)) is the subset O of C consisting of
all points x1,...,xn such that 0 < x1 <= ... <= xn < 1.  This latter 
sample space has volume 1/n!.  Notice that C contains n! congruent
replicas of O and in each the ordered n-tuple (X(1),...,X(n))
coincides with a fixed permutation of X1,...,Xn.  The probability that 
Xj=Xk for some pair j != k is zero, and only this event causes overlap 
among the various replicas.  It follows that for any subset A of O,
the probability that (X(1),...,X(n)) lies in A equals the probability
that (X1,...,Xn) lies in one of the n! replicas of A, and this
probability in turn equals n! times the volume of A.  Thus
P{(X(1),...,X(n)) in A} equals the ratio of the volumes of A and of
O, which means that the n-tuple (X(1),...,X(n)) is distributed
uniformly over the set O of points such that 0 < x1 <= ... <= xn < 1.

Cheers,

Jason




                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================