Expected Number of Uniforms to Exceed One
Let $U_1, U_2, U_3, \ldots$ be i.i.d. $\text{Uniform}(0,1)$ random variables. Define the stopping time:
$$N = \min\{n : U_1 + U_2 + \cdots + U_n > 1\}$$
What is $E[N]$?
Hints
- Think about the geometry: $P(U_1 + \cdots + U_n \leq 1)$ is the volume of a region inside the unit $n$-cube. What shape is it?
- The standard $n$-simplex $\{x \geq 0 : \sum x_i \leq 1\}$ has volume $1/n!$. Use this to compute $P(N > n) = 1/n!$.
- Apply the tail-sum formula: $E[N] = \sum_{n=0}^{\infty} P(N > n) = \sum_{n=0}^{\infty} 1/n! = e$.
Worked Solution
How to Think About It: You are adding up random numbers between 0 and 1 until the sum exceeds 1. How many draws does that take on average? Each draw adds about $1/2$ on average, so you might guess $N \approx 2$ or $3$. But the distribution is not symmetric around 2 -- sometimes you get lucky with a single large draw close to 1, and sometimes you need 4 or 5 small draws. The answer turns out to be $e \approx 2.718$, one of the most elegant results in probability.
Quick Estimate: The expected sum after 2 draws is 1, so roughly half the time 2 draws suffice and half the time you need 3 or more. That puts $E[N]$ somewhere between 2 and 3. More precisely: $P(N = 2) = P(U_1 > 1) = 0$... wait, $P(N = 1) = 0$ since $U_1 \in (0,1)$ and we need the sum to strictly exceed 1. Actually $P(N = 2) = P(U_1 + U_2 > 1) = 1/2$ (area of the triangle above the diagonal in the unit square). $P(N = 3) = P(U_1 + U_2 \leq 1, U_1 + U_2 + U_3 > 1)$. We know $P(U_1 + U_2 \leq 1) = 1/2$. So $E[N] \geq 2 + (1/2)(1) = 2.5$. With some more draws needed, $E[N]$ in the range $2.7$-$2.8$ is plausible.
Approach: Use the volume of the standard simplex to compute $P(N > n)$, then sum over $n$.
Formal Solution:
The key identity is: $$P(U_1 + U_2 + \cdots + U_n \leq 1) = \frac{1}{n!}$$
This follows because the event $\{U_1 + \cdots + U_n \leq 1, \; U_i \geq 0\}$ is the standard $n$-simplex embedded in the unit $n$-cube $[0,1]^n$. The volume of the standard $n$-simplex is $1/n!$.
Now, $N > n$ means $U_1 + \cdots + U_n \leq 1$, so: $$P(N > n) = \frac{1}{n!}$$
Using the tail-sum formula for expectation: $$E[N] = \sum_{n=0}^{\infty} P(N > n) = \sum_{n=0}^{\infty} \frac{1}{n!}$$
Verify the first few terms: - $P(N > 0) = 1 = 1/0!$ $\checkmark$ (you always need at least one draw) - $P(N > 1) = P(U_1 \leq 1) = 1 = 1/1!$ $\checkmark$ - $P(N > 2) = P(U_1 + U_2 \leq 1) = 1/2 = 1/2!$ $\checkmark$ - $P(N > 3) = P(U_1 + U_2 + U_3 \leq 1) = 1/6 = 1/3!$ $\checkmark$
Therefore: $$E[N] = \sum_{n=0}^{\infty} \frac{1}{n!} = e$$
Answer: $E[N] = e \approx 2.71828$.
Intuition
This is one of the most beautiful results in elementary probability: the number $e$ appears not from exponential growth or compound interest, but from the volumes of simplices. The $n$-simplex has volume $1/n!$, and summing these volumes over all $n$ gives the Taylor series for $e$. The result can also be understood through the theory of Poisson processes: the uniform draws are equivalent to inter-arrival times of a rate-1 Poisson process (after a transformation), and $N$ counts arrivals until the cumulative time exceeds 1.
This problem is a perennial favorite in quant interviews because it tests geometric intuition (simplex volumes), series recognition ($\sum 1/n! = e$), and the ability to connect a seemingly hard stopping-time problem to a simple formula. The technique of computing $P(N > n)$ via simplex volumes generalizes to many other "how many draws until..." problems.