How many random numbers to push the sum past one?

Question

Draw numbers one at a time, each independent and uniform on [0, 1], and keep a running total. Stop as soon as the total exceeds 1. On average, how many numbers do you draw?

Accepted Answer

Let N be the number of draws needed for the sum to first exceed 1. The elegant fact is E[N] = e \approx 2.718. Here is why. Use the tail-sum formula E[N] = \sum{k \ge 0} P(N k). Now N k means the first k draws still sum to at most 1 (you haven't crossed yet). The probability that k independent uniforms sum to less than 1 is the volume of the corner simplex in k dimensions: P(X1 + \dots + Xk \le 1) = \frac{1}{k!}. (For k = 0 this is 1; for k = 1 it's 1; for k = 2 it's 	frac12; and so on.) Therefore E[N] = \sum{k=0}^{\infty} P(N k) = \sum{k=0}^{\infty} \frac{1}{k!} = 1 + 1 + \frac{1}{2} + \fra…

How many random numbers to push the sum past one?

Your answer

More Probability questions