4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Uniformly random. Made an edit to the question mentioning that. $\endgroup$
    – web_ninja
    Commented Sep 12, 2013 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
    Commented Sep 13, 2013 at 1:05
  • 2
    $\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
    Commented Sep 13, 2013 at 2:54
  • $\begingroup$ Answered at stats.stackexchange.com/questions/194352/… $\endgroup$
    – kjetil b halvorsen
    Commented Feb 5 at 14:57

2 Answers 2

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
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
    Commented Mar 31, 2019 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
    Commented Apr 1, 2019 at 10:46
  • 1
    $\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
    Commented Apr 2, 2019 at 0:43
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .