Choose a random number between 00 and 11 and record its value. Keep doing it until the sum of the numbers exceeds 11. How many tries do we need?

Choose a random number between 0 and 1 and record its value. Do this again and add the second number to the first number. Keep doing this until the sum of the numbers exceeds 1. What’s the expected value of the number of random numbers needed to accomplish this?

Answer

Here is a (perhaps) more elementary method. Let X be the amount of numbers you need to add until the sum exceeds 1. Then (by linearity of expectation):

E[X]=1+k1Pr[X>k]

Now X>k if the sum of the first k numbers x1,,xk is smaller than 1. This is exactly equal to the volume of the k-dimensional set:

{(x1,,xk):ki=1xi1,x1,,xk0}

This is known as the k-dimensional simplex. When k=1, we get a line segment of length 1. When k=2, we get a right isosceles triangle with sides of length 1, so the area is 1/2. When k=3, we get a triangular pyramid (tetrahedron) with unit sides, so the volume is 1/6. In general, the volume is 1/k!, and so

E[X]=1+k11k!=e.

Attribution
Source : Link , Question Author : user25329 , Answer Author : Gus

Leave a Comment