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.

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

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

Answer 4

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

Expanding on Kobi's answer, here's a Java function that does exactly that.

public static double[] getRandDistArray(int n)  {
    double randArray[] = new double[n];
    double sum = 0;

    // Generate n random numbers
    for (int i = 0; i < randArray.length; i++) {
        randArray[i] = Math.random();
        sum += randArray[i];
    }

    // Normalize sum to 1
    for (int i = 0; i < randArray.length; i++) {
        randArray[i] /= sum;
    }
    return randArray;
}

In a test run, getRandDistArray(5) returned the following

[0.1796505603694718, 0.31518724882558813, 0.15226147256596428, 0.30954417535503603, 0.043356542883939767]

Answer 5

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

Answer 6

public static double[] array(int n){

    double[] a = new double[n];
    double flag = 0;

    for(int i=0;i<n;i++){
        a[i] = Math.random();
        flag += a[i];
    }

    for(int i=0;i<n;i++) a[i] /= flag;

    return a;
}

Here, at first a stores random numbers. And the flag will keep the sum all the numbers generated so that at the next for loop the numbers generated will be divided by the flag, which at the end the array will have random numbers in probability distribution.