Expected Number of Uniforms to Exceed a Threshold

Worked Solution

How to Think About It: You are drawing uniform random numbers and adding them up until you pass 1. How many draws does that take on average? Each draw contributes about $1/2$ on average, so you'd guess roughly 2 draws -- but that ignores the fact that you often overshoot or undershoot. The real answer is $e \approx 2.718$, which is surprisingly clean. The key insight is that the probability of needing more than $n$ draws is exactly $1/n!$, because the event $\{T > n\}$ is the same as the event $\{S_n \le 1\}$, and the volume of the region where $n$ uniform random variables sum to at most 1 is the volume of the standard $n$-simplex, which is $1/n!$.

Quick Estimate: Each $X_i$ has mean $1/2$, so after 2 draws the expected sum is 1. But you need to *exceed* 1, and sometimes you get unlucky with small draws. A rough guess: somewhere between 2.5 and 3. The exact answer $e \approx 2.718$ fits right in that range. You can also simulate: draw a few thousand trials on a computer and you will see the average converge to $e$.

Approach: Use the tail-sum formula for expectation $E[T] = \sum_{n=0}^{\infty} P(T > n)$ and compute each tail probability as a simplex volume.

Formal Solution:

Define $T = \min\{n : S_n > 1\}$. Note that $\{T > n\}$ is the event $\{S_n \le 1\}$, i.e., the first $n$ draws all contribute to a partial sum that has not yet exceeded 1.

The probability $P(S_n \le 1)$ is the volume of the region

$$\{(x_1, \ldots, x_n) \in [0,1]^n : x_1 + \cdots + x_n \le 1\}.$$

Since each $x_i \in [0,1]$ and the constraint $\sum x_i \le 1$ already forces each $x_i \le 1$, this region is exactly the standard $n$-simplex $\Delta_n$. Its volume is

$$\text{Vol}(\Delta_n) = \frac{1}{n!}.$$

So $P(T > n) = 1/n!$. Applying the tail-sum formula for expectation:

$$E[T] = \sum_{n=0}^{\infty} P(T > n) = \sum_{n=0}^{\infty} \frac{1}{n!} = e.$$

Generalization to threshold $c > 0$:

For $T_c = \min\{n : S_n > c\}$, we need

$$P(T_c > n) = P(S_n \le c) = \text{Vol}\{(x_1, \ldots, x_n) \in [0,1]^n : x_1 + \cdots + x_n \le c\}.$$

For $0 < c \le 1$, this is simply $c^n / n!$ (scaled simplex), so

$$E[T_c] = \sum_{n=0}^{\infty} \frac{c^n}{n!} = e^c.$$

For general $c > 0$ (including $c > 1$), the region is no longer a simplex because the $[0,1]^n$ box constraint binds. By inclusion-exclusion, the volume is the Irwin-Hall CDF:

$$P(S_n \le c) = \frac{1}{n!} \sum_{j=0}^{\lfloor c \rfloor} (-1)^j \binom{n}{j}(c - j)^n.$$

Then

$$E[T_c] = \sum_{n=0}^{\infty} P(S_n \le c).$$

For integer thresholds, closed forms exist. For example: - $c = 1$: $E[T_1] = e \approx 2.718$ - $c = 2$: $E[T_2] = \frac{e^2 + e}{2} \approx 5.053$

In general, for integer $c = k$, $E[T_k]$ can be expressed in terms of powers of $e$ with rational coefficients.

Answer: $E[T] = e$. For threshold $0 < c \le 1$, $E[T_c] = e^c$. For general $c$, $E[T_c] = \sum_{n=0}^{\infty} P(S_n \le c)$ where each term uses the Irwin-Hall inclusion-exclusion formula.