Generating a probability distribution

Question

Given an array of size n I want to generate random probabilities for each index such that Sigma(a[0]..a[n-1])=1

One possible result might be:

0     1     2     3     4
0.15  0.2   0.18  0.22  0.25

Another perfectly legal result can be:

0     1     2     3     4
0.01  0.01  0.96  0.01  0.01

How can I generate these easily and quickly? Answers in any language are fine, Java preferred.

Answer 1

Get n random numbers, calculate their sum and normalize the sum to 1 by dividing each number with the sum.

Answer 2

The task you are trying to accomplish is tantamount to drawing a random point from the N-dimensional unit simplex.

http://en.wikipedia.org/wiki/Simplex#Random_sampling might help you.

A naive solution might go as following:

public static double[] getArray(int n)
    {
        double a[] = new double[n];
        double s = 0.0d;
        Random random = new Random();
        for (int i = 0; i < n; i++)
        {
           a [i] = 1.0d - random.nextDouble();
           a [i] = -1 * Math.log(a[i]);
           s += a[i];
        }
        for (int i = 0; i < n; i++)
        {
           a [i] /= s;
        }
        return a;
    }

To draw a point uniformly from the N-dimensional unit simplex, we must take a vector of exponentially distributed random variables, then normalize it by the sum of those variables. To get an exponentially distibuted value, we take a log of uniformly distributed value.

Answer 3

If you want to generate values from a normal distribution efficiently, try the Box Muller Transformation.