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?
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):
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:
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