Puzzle – How to Efficiently Generate Five Numbers that Add to One

puzzlerandom

I have access to a random number generator that generates numbers from 0 to 1. Using this, I want to find five random numbers that add up to 1.

How can I do this using the smallest number of steps possible?

Edit: I do want the numbers to be uniformly distributed.

Best Answer

The following method results in a uniform distribution on all sequences with sum one. Generate four random numbers and sort them in ascending order to get $x_1 \leq x_2 \leq x_3 \leq x_4$ then take $$x_1, x_2-x_1, x_3-x_2, x_4-x_3, 1-x_4$$ as your final sequence of numbers that add to one.

In contrast, the method suggested in another answer (rescaling) results in sequences that are biased towards the centroid of the set of all sequences of sum one (i.e. the summands are biased towards $\frac{1}{5}$).

Here are some results of a simple experiment to demonstrate the bias. I implemented both methods (called "sort" and "scale") and generated ten sequences with each. I determined the standard deviation of all these sequences and sorted them in descending order. Here's one result set (all numbers rounded to three decimal places):

 #  method  sd     sequence
 -  ------  --     --------
 1:  sort   0.302  (0.802, 0.081, 0.065, 0.026, 0.027)
 2:  sort   0.182  (0.344, 0.001, 0.139, 0.475, 0.040)
 3:  sort   0.180  (0.290, 0.499, 0.040, 0.165, 0.005)
 4:  sort   0.179  (0.369, 0.445, 0.009, 0.017, 0.160)
 5:  sort   0.172  (0.011, 0.198, 0.308, 0.023, 0.461)
 6: scale   0.171  (0.325, 0.452, 0.031, 0.191, 0.001)
 7:  sort   0.159  (0.413, 0.129, 0.064, 0.028, 0.366)
 8: scale   0.138  (0.003, 0.090, 0.392, 0.256, 0.259)
 9: scale   0.136  (0.335, 0.346, 0.082, 0.233, 0.004)
10:  sort   0.133  (0.375, 0.086, 0.349, 0.093, 0.096)
11: scale   0.128  (0.082, 0.021, 0.328, 0.232, 0.337)
12: scale   0.118  (0.256, 0.038, 0.342, 0.083, 0.281)
13:  sort   0.103  (0.205, 0.229, 0.028, 0.348, 0.191)
14: scale   0.096  (0.121, 0.361, 0.117, 0.142, 0.260)
15:  sort   0.091  (0.246, 0.284, 0.181, 0.258, 0.031)
16: scale   0.080  (0.157, 0.281, 0.192, 0.294, 0.077)
17:  sort   0.074  (0.146, 0.179, 0.328, 0.228, 0.119)
18: scale   0.065  (0.264, 0.259, 0.202, 0.083, 0.193)
19: scale   0.027  (0.219, 0.215, 0.213, 0.147, 0.206)
20: scale   0.020  (0.235, 0.201, 0.200, 0.185, 0.179)

So the "scale" methods tends to produce sequences with smaller standard deviation.

Related Question