3 ms·
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 s
by ivan_ah 14y ago
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_articles/probability_book/Chapter7.pdf#page=5 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.