How many uniforms to exceed one half?

Question

Draw U1, U2, \dots independently from U(0,1) and let Nt be the smallest n with U1 + \cdots + Un t, for a threshold 0 < t \le 1. Find E[Nt] in general, and evaluate it at t = 	frac12.

Accepted Answer

Step 1: the tail probability. Nt n means the first n draws still sum to at most t. That region is a simplex scaled by t inside the cube: P(Nt n) = \operatorname{vol}\{u \in [0,1]^n : u1 + \cdots + un \le t\} = \frac{t^n}{n!}, \qquad 0 < t \le 1. (The full simplex \{u1 + \cdots + un \le 1\} has volume 	frac{1}{n!}; scaling every coordinate by t multiplies n-dimensional volume by t^n.) Step 2: sum the tail. For a nonnegative integer variable, E[Nt] = \sum{n=0}^{\infty} P(Nt n) = \sum{n=0}^{\infty} \frac{t^n}{n!} = e^{t}. At t = 	frac12: E[N{1/2}] = e^{1/2} = \sqrt{e} \approx 1.6487. This nest…

How many uniforms to exceed one half?

Your answer

More Probability questions