How many uniforms to exceed one?

Question

Draw U1, U2, \dots independently from U(0,1) and let N be the smallest n such that U1 + \cdots + Un 1. What is E[N]?

Accepted Answer

Step 1: the tail. N n exactly when the first n draws still sum to at most 1: P(N n) = P(U1 + \cdots + Un \le 1) = \mathrm{vol}\{u \in [0,1]^n : u1 + \cdots + un \le 1\} = \frac{1}{n!}. The volume of the simplex is \frac{1}{n!} by a slick bijection: for u in the simplex, the partial sums sk = u1 + \cdots + uk form an increasing sequence in [0,1]; conversely any increasing sequence gives such a u. Increasing sequences are one of the n! equally-sized ordering chambers of the cube, hence volume \frac{1}{n!}. (Induction on n works too.) Step 2: sum the tail. For a nonnegative integer variable, E[N…

How many uniforms to exceed one?

Your answer

More Probability questions