Probability That n Uniforms Sum to at Most 1
Let $X_1, X_2, \ldots, X_n$ be independent random variables, each uniformly distributed on $[0, 1]$. Show that
$$P\!\left(X_1 + X_2 + \cdots + X_n \le 1\right) = \frac{1}{n!}.$$
Hints
- For $n = 2$ the event is the triangle below the line $x + y = 1$ in the unit square, with area $1/2$. For $n = 3$ it is a tetrahedron. What is the general shape?
- Prove the stronger statement $P(X_1 + \cdots + X_n \le x) = x^n / n!$ for $0 \le x \le 1$ by induction on $n$, conditioning on $X_{n+1}$.
- $P(S_{n+1} \le x) = \int_0^x P(S_n \le x - t)\,dt = \int_0^x \frac{(x-t)^n}{n!}\,dt = \frac{x^{n+1}}{(n+1)!}$.
Worked Solution
How to Think About It: The event $\{X_1 + \cdots + X_n \le 1\}$ with all $X_i \in [0, 1]$ is the region $x_i \ge 0$, $\sum x_i \le 1$, a simplex. Its volume is $1/n!$, and the cleanest proof is induction on $n$ with the general threshold $x \in [0, 1]$ carried along, because conditioning on the last variable turns the $(n+1)$-fold problem into an integral of the $n$-fold one.
Quick Estimate: $n = 2$: the triangle under $x + y = 1$ has area $1/2$. $n = 3$: the tetrahedron has volume $1/6$. The pattern $1/n!$ is already visible.
Formal Solution:
*Step 1 -- Strengthen the claim.* Let $S_n = X_1 + \cdots + X_n$ and define $F_n(x) = P(S_n \le x)$. Claim: for $0 \le x \le 1$,
$$F_n(x) = \frac{x^n}{n!}.$$
*Step 2 -- Base case.* $F_1(x) = P(X_1 \le x) = x = x^1/1!$.
*Step 3 -- Inductive step.* Assume $F_n(x) = x^n/n!$ on $[0, 1]$. Since $X_{n+1}$ is independent of $S_n$ and uniform, for $x \in [0, 1]$,
$$F_{n+1}(x) = P(S_n + X_{n+1} \le x) = \int_0^1 P(S_n \le x - t)\,dt = \int_0^x F_n(x - t)\,dt,$$
where the integrand vanishes for $t > x$ because $S_n \ge 0$. Substituting the hypothesis,
$$F_{n+1}(x) = \int_0^x \frac{(x - t)^n}{n!}\,dt = \frac{x^{n+1}}{(n+1)!}.$$
*Step 4 -- Conclude.* Setting $x = 1$ gives $P(S_n \le 1) = 1/n!$.
*Geometric view.* The event is the simplex $\Delta_n = \{x \in [0,1]^n : \sum x_i \le 1\}$. The map $y_k = x_1 + \cdots + x_k$ is volume-preserving (unit-triangular Jacobian) and sends $\Delta_n$ onto $\{0 \le y_1 \le y_2 \le \cdots \le y_n \le 1\}$, which is one of the $n!$ congruent order-regions partitioning the cube. Hence $\text{vol}(\Delta_n) = 1/n!$.
*Corollary.* If $N = \min\{n : S_n > 1\}$ then $P(N > n) = 1/n!$ and $E[N] = \sum_{n \ge 0} 1/n! = e$.
Answer: $P(X_1 + \cdots + X_n \le 1) = \dfrac{1}{n!}$ (for example $1/24$ when $n = 4$).
Intuition
The event is the standard $n$-simplex $\{x_i \ge 0, \sum x_i \le 1\}$ inside the unit cube, and the simplex has volume $1/n!$: the cube can be cut into $n!$ congruent pieces according to the ordering of the coordinates, and the simplex is one of them after a change of variables. The induction just integrates $(x-t)^n/n!$ once more. The same fact gives $E[\min\{n : X_1 + \cdots + X_n > 1\}] = \sum 1/n! = e$, a classic follow-up, and the simplex volume is the reason uniform spacings and Dirichlet distributions carry factorials.