# A proof of the Glivenko-Cantelli theorem

I would like to have the following proof of the Glivenko-Cantelli theorem checked, which states that if $${X_1,X_2,\dots}$$ are iid copies of a real random variable $${X}$$, then almost surely, one has

$$\displaystyle \frac{1}{n} | \{ 1 \leq i \leq n: X_i \leq t \}| \rightarrow {\bf P}( X \leq t )$$

uniformly in $${t}$$ as $${n \rightarrow \infty}$$.

Hint: For any natural number $${m}$$, let $${f_m(x)}$$ denote the largest integer multiple of $${1/m}$$ less than $${x}$$. Show first that $${f_m( \frac{1}{n} | \{ 1 \leq i \leq n: X_i \leq t \}| )}$$ is within $${O(1/m)}$$ of $${f_m( {\bf P}( X \leq t ) )}$$ for all $${t}$$ when $${n}$$ is sufficiently large. Once one has uniformity in $$t$$ for the $$f_m$$-approximate version of the problem, the usual analysis arguments (splitting an epsilon into say three smaller epsilons, etc.) will then give uniformity in $$t$$ for the original problem.

Proof: Let $$F_n(t) := \frac{1}{n}|\{ 1 \leq i \leq n: X_i \leq t \}|$$ denote the empirical distribution function and $$F(t) := {\bf P}(X \leq t)$$ the CDF. For any natural number $${m}$$, let $${f_m(x)}$$ denote the largest integer multiple of $${1/m}$$ less than $${x}$$.

By construction, $$f_m$$ is a piecewise constant function on the unit interval, divided at $$0, 1/m, 2/m, \dots, 1$$ (we let $$f_m(0) := 0$$). Subsequently $${\bf R}$$ is partitioned into $$m$$ intervals, divided at $$t_0 := F^{-1}(0), t_1 := F^{-1}(1/m), \dots, t_m := F^{-1}(1)$$, here we let $$t_0 = F^{-1}(0) := -\infty$$ and $$t_m = F^{-1}(1) := \infty$$.

For any $$t \in {\bf R}$$, $$t \in [t_{j-1}, t_j]$$ for some $$j$$, and correspondingly $$F(t) \in [\frac{j-1}{m}, \frac{j}{m}]$$, as all of $$f_m, F, F_n$$ are non-decreasing, we have \begin{align*} f_m(F_n(t)) - f_m(F(t)) &\leq f_m(F_n(t_j)) - f_m(F(t_{j-1})) \\ &= f_m(F_n(t_j)) - f_m(F(t_j)) + 1/m. \end{align*} Therefore, \begin{align*} \|f_m(F_n) - f_m(F)\|_\infty &= \sup_{t \in \bf R} |f_m(F_n(t)) - f_m(F(t))| \\ &\leq \max_{j \in \{1, \dots, m\}} |f_m(F_n(t_j)) - f_m(F(t_j))| + 1/m. \end{align*} By the strong law of large numbers (and the definition of $$f_m$$), we see that $$\forall t \in {\bf R}, |f_m(F_n(t)) - f_m(F(t))| = O(1/m)$$ almost surely for sufficiently large $$n$$. By the triangle inequality, we thus have \begin{align*} |F_n(t) - F(t)| &\leq |F_n(t) - f_m(F_n(t))| + |F(t) - f_m(F(t))| + |f_m(F_n(t)) - f_m(F(t))| \\ &= O(1/m) \end{align*} almost surely for sufficiently large $$n$$, as $$1/m$$ can be arbitrarily small, this proves the claim.