Probability & Statistics

Sum of Uniforms Below One

Add up n independent uniform draws from the interval from 0 to 1. How likely is the total to land below 1?

solvedmedium2 min

Let X1,X2,,XnX_1, X_2, \dots, X_n be independent, each uniform on [0,1][0,1]. What is the probability that their sum is less than 11?

Reveal solutionHide solution

#A volume inside the cube

The vector (X1,,Xn)(X_1, \dots, X_n) is uniform on the unit cube [0,1]n[0,1]^n, so every probability is just a volume. The event {X1++Xn<1}\{X_1 + \cdots + X_n < 1\} is the corner simplex {xi0, ixi<1}\{x_i \ge 0,\ \sum_i x_i < 1\}, which sits entirely inside the cube, so the probability equals that simplex's volume.

#Partial sums straighten the simplex

Send each point to its running totals, yk=x1+x2++xky_k = x_1 + x_2 + \cdots + x_k. This map is linear with a triangular matrix whose diagonal is all ones, so its determinant is 11 and it preserves volume. It carries the simplex {xi>0, ixi<1}\{x_i > 0,\ \sum_i x_i < 1\} exactly onto the sorted region {0<y1<y2<<yn<1}\{0 < y_1 < y_2 < \cdots < y_n < 1\}.

#Count the orderings

The cube breaks into n!n! congruent pieces, one for each ordering of the coordinates, all of equal volume by symmetry. The sorted region is a single one of them, so it has volume 1n!\tfrac{1}{n!}, and therefore

P(X1++Xn<1)=1n!.(1)\PP(X_1 + \cdots + X_n < 1) = \frac{1}{n!}. \tag{1}
n = 2
n = 3
The event is the corner simplex cut from the unit cube by the plane that sums to one. Its volume is one half in two dimensions and one sixth in three, the pattern 1/n! continuing in every dimension.

For n=2n = 2 the chance is 12\tfrac{1}{2} and for n=3n = 3 it is 16\tfrac{1}{6}, the factorial shrinking the corner simplex away to nothing as the dimension grows.

#The general statement by induction

The same answer drops out of a sharper claim, that P(Snt)=tnn!\PP(S_n \le t) = \tfrac{t^{n}}{n!} for every 0t10 \le t \le 1, where Sn=X1++XnS_n = X_1 + \cdots + X_n. The base case n=1n = 1 is just P(X1t)=t\PP(X_1 \le t) = t. Assuming the claim at nn, condition on the final draw Xn+1X_{n+1}, whose density is 11 on [0,1][0,1],

P(Sn+1t)=01P(Sntx)dx=0t(tx)nn!dx=tn+1(n+1)!,(2)\PP(S_{n+1} \le t) = \int_0^1 \PP(S_n \le t - x)\,dx = \int_0^t \frac{(t-x)^{n}}{n!}\,dx = \frac{t^{n+1}}{(n+1)!}, \tag{2}

where the integrand drops to zero once x>tx > t because then SnS_n cannot be negative. Setting t=1t = 1 recovers 1n!\tfrac{1}{n!}, now as the value of a polynomial that also gives the law of the partial sum at every cutoff below 11.