Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is the exact question:

You are given black-box which returns a random number between 0 and 1(uniform distribution).You keep generating random numbers X1,X2,X3 and so on and store the sum of all those random numbers. You stop as soon as the sum exceeds 1.What is the expected number of random variables used in the process?

How I went about solving this is to find the probability that N random variables are required and S = event that sum exceeds 1.

For N=1, P(S) = 0.

For N=2, P(S) = 1/2 ( X1 + X2 > 1, when (X1,X2) lies above the line X1 + X2 = 1 where 0 < X1,X2 < 1. Area of triangle fulfilling the criteria is 1/2 )

For N=3, P(S) = 1/2 * 5/6 ( X1 + X2 + X3 > 1. This holds when X1 + X2 > 1 - X3 and integrating over all values of X3 gave the probability to be 5/6 which is multiplied with 1/2 because X1 + X2 < 1)

This seems to be a rather lengthy way to approach this problem. Is there a shorter more intuitive method?

share|improve this question
1  
Uniformly random. Made an edit to the question mentioning that. –  web_ninja Sep 12 '13 at 10:43
    
This question was Problem A3 of the 1958 Putnam Competition (and as such is not research-level mathematics). –  Greg Marks Sep 13 '13 at 1:05
    
@Greg Marks: The problem itself isn't research level. However, web_ninja asked, "Is there a shorter, more intuitive method?" Finding a short, intuitive approach to a problem you can solve in another way seems to fit. In addition, this is not an isolated puzzle as shown by the question I linked. –  Douglas Zare Sep 13 '13 at 2:54

2 Answers 2

up vote 5 down vote accepted

For any random variable $X$ taking values in $\mathbb{N}$, $E[X]= \sum_{n=0}^\infty P(X\gt n)$. In this case, the probability that the sum of the first $n$ numbers is less than $1$ is $1/n!$, the volume of the simplex with vertices at the origin and the standard basis vectors in $n$ dimensions. So, the expected number of draws needed to get a partial sum greater than $1$ is $\sum_{n=0}^\infty 1/n! = e$.

Another approach is to set up a (lag-)differential equation for $f(x)$, the expected number of draws needed for the sum to exceed $x$. For $x \le 0, f(x) = 0$. For $x \gt 0, f(x) = 1+ \int_{x-1}^x f(z) dz$, so $f'(x) = f(x)-f(x-1)$. This has the solution $f(x) = e^x, 0\lt x\le 1$. Another recent question asked about the error from the asymptotic of $f(x) \sim 2x+2/3$.

share|improve this answer

If I copypaste your title into google it shows me that the answer is e. http://mathworld.wolfram.com/UniformSumDistribution.html

share|improve this answer

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.