generating constrained random vectors - a proof ( i think)

[Chris Landauer]

hihi, all -

well, the last message worried me, so i worked through a proof of the process
suggested by several people of incrementally generating the values (i think
the comment about bias towards small values is actually correct, but not a
problem, since if the sum of all the values is to be 1, then there can't be
very many large values anyway)

to start working out a proof, define the generation process gen(n,r,x) as
follows:

it is defined for integer n >= 1, real r >= 0, and an n-vector x

gen(n,r,x) =
        if (n==1)
                x[n] = r;
        else
                x[n] = choose uniform random value in [0,r];
                gen(n-1,r-x[n],x)

the theorem to be proved is that the vector resulting from this process
gen(n,r,x) is uniformly distributed over the set

        { x in real n-space | each x[i] >= 0, sum(i) x[i] = r }

it is easy for the case n=1, since the set contains only one point, and also
for n=2, as in my previous message

now the probability density function of gen(n,r,x) can be factored using
conditional probabilities, and each factor is constant, so the entire function
is, which means that the distribution is uniform (this is really a
plausibility argument, but i think it can be turned into a proof)

more later,
cal

Dr. Christopher Landauer
Aerospace Integration Science Center
The Aerospace Corporation, Mail Stop M6/214
P.O.Box 92957
Los Angeles, California 90009-2957, USA
e-mail: address@hidden
Phone: +1 (310) 336-1361


                  ==================================
   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.
                  ==================================