Generating N numbers that sum to 1

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.

Solution 1

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 distributed value, we take a negative log of uniformly distributed value.

Solution 2

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

Solution 3

This is relatively late, but to show the ammendment to @Kobi's simple and straightforward answer given in this paper pointed to by @dreeves which makes the sampling uniform. The method (if I understand it clearly) is to

1. Generate n-1 distinct values from the range [1, 2, ... , M-1].
2. Sort the resulting vector
3. Add 0 and M as the first and last elements of the resulting vector.
4. Generate a new vector by computing x_i - x_i-1 where i = 1,2, ... n. That is, the new vector is made up of the differences between consecutive elements of the old vector.
5. Divide each element of the new vector by M. You have your uniform distribution!

I am curious to know if generating distinct random values and normalizing them to 1 by dividing by their sum will also produce a uniform distribution.