News for hackers. Stuff that matters.
Re:How many draws of a random number [0,1] are needed to sum... by ivan_ah on Sunday February 24, 2013 @05:17PM (#5276167)
The calculation given by the OP does not solve the stated problem, as remarked by xyzzyz.

Sniffnoy already gave the correct solution in elementary terms, but since I spent the last two hour learning about the convolution formula, I want to give my solution here.

Define: U[0,1] to the the uniform distr. on [0,1] and S_n to be the sum of n copies of the uniform distribution. We can compute the probability density function f_{S_n}(x) using the convolution formula:

    f_{S_n}(x) = 1/(n-1)! * \sum_{0≤j≤x} (-1)^j (n choose j) (x - j)^{n-1}.
see http://www.dartmouth.edu/~chance/teaching_aids/books_article...

In particular we are interested in the event that the sum goes over 1:

    Pr{ S_n < 1 } = \int_0^1 f_{S_n}(x) dx.
In the range [0,1] the function pdf f_{S_n}(x) takes on the simple form 1/(n-1)!x^{n-1} because j=0 is the only term we keep in the summation, so we can evaluate the above integral:

    Pr{ S_n < 1 } = 1/n!.
OK, now for the problem statement ;)

Let N be the random variable which describes the number of draws from U[0,1] we will make to reach a sum of 1. We need to find the probability density of N (call it p(n)) and then calculate its expected value

    E{N} = \sum_n=0^\infty n*p(n)
As pointed out by Sniffnoy, the formula for p(n), the probability that it will take //exactly// n draws to go over 1 is given by:

  p(1) = 0,
  p(2) =  1                  - Pr{ S_{2} < 1 },
  p(3) = [1 - p(2)]          - Pr{ S_{3} < 1 }  = Pr{ S_{2}<1 } - Pr{ S_{3}<1 },
  p(4) = [1 - p(2) - p(3)]   - Pr{ S_{4} < 1 }  = Pr{ S_{3}<1 } - Pr{ S_{4}<1 },
  p(n) = [1-p(n-1)-..- p(2)] - Pr{ S_{n} < 1 }  (telescopic sum in [ ])
       = Pr{ S_{n-1} < 1 }   - Pr{ S_{n} < 1 }   
       = 1/(n-1)! - 1/n!
Note that [1 - p(n-1) - p(n-2) - ... - p(2)] is the prob of not going over 1 in the first n-1 trials, from which we subtract 1/n! -- the probability of not going over in the n'th trial.

The final steps are:

     E{N} = \sum_n=2^\infty n*p(n) 
          = \sum_n=2^\infty n*[1/(n-1)! - 1/n! ] 
          = \sum_n=2^\infty [n/(n-1)! - n/n! ] 
          = \sum_n=2^\infty [n/(n-1)! - 1/(n-1)! ] 
          = \sum_n=2^\infty [(n-1)/(n-1)!] 
          = \sum_n=2^\infty 1/(n-2)!
          = \sum_m=0^\infty 1/m!        (change of var m = n-2) 
          = e
Very nice problem.

There are no comments on this comment yet.