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?

  • 1
    $\begingroup$ Uniformly random. Made an edit to the question mentioning that. $\endgroup$ – web_ninja Sep 12 '13 at 10:43
  • $\begingroup$ This question was Problem A3 of the 1958 Putnam Competition (and as such is not research-level mathematics). $\endgroup$ – Greg Marks Sep 13 '13 at 1:05
  • 1
    $\begingroup$ @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. $\endgroup$ – Douglas Zare Sep 13 '13 at 2:54

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

  • $\begingroup$ How do you get an expectation $\sum_{n=0}^\infty 1/n!$ from the fact that the probability that the sum of the first $n$ numbers is less than 1 is $1/n!$? Where does the term $1/0!$ come from in the sum? $\endgroup$ – Richard Stanley Mar 31 at 16:38
  • $\begingroup$ @RichardStanley: The $1/0!$ term is the probability that you need to draw the first time, which is $P(X > 0)=1$. The probability that you need to draw the second number is also 1, $P(X > 1)=1/1!$. The probability that you need to draw the third number is $P(X>2)=1/2!$ etc. $\endgroup$ – Douglas Zare Apr 1 at 10:46
  • $\begingroup$ The sum is just the tail-sum formula for the expected value of a random whole number. $\sum i P(X=i) = \sum_i \sum_{j=1}^i P(X=i) = \sum_{j=1}^\infty \sum_{i =j}^\infty P(X=i) = \sum_{j=1}^\infty P(X \ge j)$. $\endgroup$ – Douglas Zare Apr 2 at 0:43

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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