Glivenko-Cantelli theorem

For independent and identically distributed real observations $X_i$ with cumulative distribution function $F$, the empirical distribution functionsatisfies the Glivenko-Cantelli theoremThe population law may have atoms; continuity of $F$ is not required. The conclusion is uniform over every threshold, strengthening the separate strong laws for fixed thresholds.^[ref]

Here is a proof using inverse transform sampling. First take iid uniforms and their empirical CDF $G_n$. At the finitely many grid points $j/m$, the strong law of large numbers gives $G_n(j/m)\to j/m$ simultaneously. Monotonicity bounds the discrepancy between grid points by the largest grid discrepancy plus $1/m$. Taking countably many $m\to \infty$ proves uniform convergence on $[0,1]$.

For general $F$, construct $X_i=F^{-1}(U_i)$ using the quantile function. Then $X_i\le x$ exactly when $U_i\le F(x)$, so $F_n(x)=G_n(F(x))$ and the general supremum is bounded by the uniform one. This also handles jumps of $F$. The theorem does not apply merely because an empirical CDF was formed: for repeated copies of the same nondegenerate random observation, the empirical CDF does not approach its population law in this way.

For a cumulative distribution function $G$, let $Q(u)=\inf \{x:G(x)\ge u\}$, $0<u<1$. Right continuity gives $Q(u)\le x$ exactly when $u\le G(x)$, including at atoms. Thus applying $Q$ to independent uniform variables $U_i$ constructs an independent sample with distribution function $G$. Its empirical distribution function is $G_n(x)=F_n(G(x))$, where $F_n$ is the uniform-sample empirical distribution function. Consequently ${\sup }_x|G_n(x)-G(x)|\le {\sup }_{t\in [0,1]}|F_n(t)-t|$. For the uniform sample, monotonicity and a grid of mesh $1/m$ bound the last supremum by the largest error at grid points plus $1/m$. The strong law of large numbers on the countable union of all such grids proves the almost-sure limit. This construction proves the theorem for distributions with atoms as well as continuous distributions.