Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
17  
Generate $5$ random numbers, and divide by their sum? –  Zev Chonoles Jun 16 '13 at 17:09
3  
I wonder if this can be done using only four calls rather than five... –  vadim123 Jun 16 '13 at 17:18
add comment

4 Answers

up vote 21 down vote accepted

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.

share|improve this answer
3  
Here is a little intuition. You chop the line at random in four places and get five pieces. If you do this at randome, you expect each piece to be 1/5 long. –  ncmathsadist Jun 16 '13 at 18:23
    
The obervations you get this way are not independent; they're negatively correlated. –  Michael Hardy Jun 18 '13 at 18:25
    
@MichaelHardy Sure, this is most clearly visible if you only take two numbers. :-) –  WimC Jun 18 '13 at 18:37
add comment

To expand on the comment made by Zev Chonoles, it is trivial to show that given $5$ random numbers, $x_{1},\dots,x_{5}\in\mathbb{R}$, you can scale them to add up to one:

$$\frac{x_{1}}{\sum_{i=1}^{5}x_{i}}+\cdots+\frac{x_{5}}{\sum_{i=1}^{5}x_{i}}=1$$

If we multiply both sides of the equation by $\sum_{i=1}^{5}x_{i}=x_{1}+\cdots+x_{5}$, we get:

$$x_{1}+\cdots+x_{5}=\sum_{i=1}^{5}x_{i}$$

Which is true by definition. Q.E.D.

share|improve this answer
4  
Sure they add up to $1$, but you also need to show that the distribution is really uniformly random. –  ShreevatsaR Jun 16 '13 at 17:35
5  
So you proved that $x_1+\cdots+x_5=\sum_{i=1}^5x_i$? ...Good job? –  Rahul Jun 16 '13 at 17:36
1  
@ShreevatsaR The OP didn't mention anything about a uniform distribution. –  Byron Schmuland Jun 16 '13 at 17:46
1  
Seems to have done so now. :-) –  ShreevatsaR Jun 16 '13 at 18:29
3  
This will give a uniform distribution if the $x_i$'s are independent exponential random variables. See en.wikipedia.org/wiki/Dirichlet_distribution#Gamma_distribution –  Byron Schmuland Jun 16 '13 at 18:41
add comment

This can be done with the following strategy.

Generate $X \sim \textrm{Unif}[0,{2 \over 5}].$ Let $Y = {2 \over 5} - X.$ Generate $Z \sim \textrm{Unif}[0,{2 \over 5}].$ Set $W = V = {3 \over 10} - {Z \over 2}.$

With this set up, we know that $X + Y + Z + W + V = 1$ as required. And each random variable has a uniform distribution, although not all have the same uniform distribution.

The accepted solution does not generate uniform random variables. For example, consider the first point $x_1$ of that proposed method. It is the minimum of four Unif$[0,1]$ random variables. The minimum of uniform random variables does not have a uniform distribution.

share|improve this answer
add comment

Here is a way to satisfy the basic requirements of the question and have all of the component random variables identically uniformly distributed. Generate $V$ as uniform$[0,{2 \over 5}].$ Let $$W = \begin{cases} V+{1/10} \ , & \text{if} \ V \le {3/10} \\ V-{3/10} \ , & \text{if} \ V \gt {3/10} \end{cases}$$ Let $$X = \begin{cases} V+{2/10} \ , & \text{if} \ V \le {2/10} \\ V-{2/10} \ , & \text{if} \ V \gt {2/10} \end{cases}$$ Let $$Y = \begin{cases} V+{3/10} \ , & \text{if} \ V \le {1/10} \\ V-{1/10} \ , & \text{if} \ V \gt {1/10} \end{cases}$$ Let $$Z = 1-V-W-X-Y.$$ This may not be the best approach, but it does require only one generation of a uniform random variable since $W, X, Y,$ and $Z$ are all dependent on $V.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.