The Empirical Distribution and Glivenko-Cantelli Classes

Intuition Beginner

You have a sample of data and you want to know the distribution it came from — not just its average, but its whole shape: where the values pile up, how spread out they are, where the tails sit. The most honest summary you can build is the empirical distribution: pretend the only possible outcomes are exactly the data points you saw, each equally likely. If you collected $100$ numbers, you treat the world as a lottery with those $100$ tickets. This turns a sample into a full-fledged distribution you can compute anything from.

The empirical distribution function records, for each threshold, the fraction of your data at or below it. As you collect more data, this staircase of fractions should fill in and match the true distribution function. The law of large numbers already promises that at any single fixed threshold the fraction settles to the true probability. The deeper claim is that this happens everywhere at once: the entire empirical curve hugs the true curve, with the worst gap across all thresholds shrinking to zero.

That uniform promise is the Glivenko-Cantelli theorem, sometimes called the fundamental theorem of statistics. It is what lets you treat a sample as a faithful stand-in for the population, and it is the reason plug-in estimates — compute something from the data exactly as you would from the truth — actually work as the sample grows.

The one-sentence takeaway: the empirical distribution built from a sample converges to the true distribution uniformly, so a large sample is a trustworthy picture of the whole population, not just of one feature at a time.

Visual Beginner

Picture the true distribution function as a smooth rising curve from $0$ on the left to $1$ on the right. The empirical version is a staircase: it jumps up by $1/n$ at each data point and is flat in between. Watch the staircase as the sample size grows.

Sample size	What the staircase looks like	Worst gap to the true curve
Small	A few big steps, blocky, only roughly tracking the curve	Large
Medium	Many smaller steps hugging the curve more closely	Smaller
Large	A fine staircase nearly on top of the smooth curve	Tiny
Growing without bound	The staircase merges into the smooth curve everywhere	Shrinks to zero

The single number to watch is the worst gap: the largest vertical distance between the staircase and the smooth curve, taken over every threshold. Glivenko-Cantelli says this worst gap closes to zero as the sample grows, for almost every run of data collection. The same worst gap is what the Kolmogorov-Smirnov test measures to decide whether a sample really came from a proposed distribution.

Worked example Beginner

We build the empirical distribution function from a tiny sample and measure its worst gap to a true distribution. Take five data points drawn from a distribution that is uniform on the interval from $0$ to $1$, whose true distribution function is the straight line $F(t)=t$ on that interval. Suppose the five values are $0.1,0.3,0.5,0.7,0.9$.

Step 1. Build the staircase. With $n=5$ points, each one contributes a jump of $1/5=0.2$. The empirical fraction at or below a threshold $t$ counts how many of the five values are $\le t$, divided by $5$. Below $0.1$ the fraction is $0$; at $0.1$ it jumps to $0.2$; at $0.3$ to $0.4$; at $0.5$ to $0.6$; at $0.7$ to $0.8$; at $0.9$ to $1.0$.

Step 2. Compare to the true line just before each jump. The biggest gaps sit just under each data point, where the staircase has not yet jumped but the true line has risen. Just below $0.1$, the staircase is $0$ and the true value is $0.1$, a gap of $0.1$. Just below $0.3$, the staircase is $0.2$ and the true value is $0.3$, a gap of $0.1$. The same pattern repeats: just below $0.5$, $0.7$, $0.9$, each gap is $0.1$.

Step 3. Compare just after each jump. Just above $0.1$, the staircase is $0.2$ and the true value is $0.1$, a gap of $0.1$. The same $0.1$ gap appears just above each data point.

Step 4. Read off the worst gap. Every gap computed is $0.1$, so the largest vertical distance between staircase and true line is $0.1$.

Step 5. What this tells us. With only five evenly spaced points the worst gap is already just $0.1$. Pack in more data and the steps get finer and the worst gap shrinks. Glivenko-Cantelli is the promise that, for genuinely random samples, this worst gap keeps dropping toward zero as the sample grows, so the staircase becomes a faithful copy of the true distribution.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $X_1,X_2,\dots$ are independent and identically distributed random elements of a measurable space $(\mathcal{X},\mathcal{A})$ with common law $P$. The development follows van der Vaart ^{[van der Vaart 1998]} Ch. 19 and van der Vaart-Wellner ^{[van der Vaart Wellner 1996]} §2.4. The modes of stochastic convergence and the notion of consistency used below are those fixed in 45.04.01, and the strong law of large numbers 37.02.02 is the single probabilistic input.

Definition (empirical measure and empirical process). The empirical measure of the first $n$ observations is the random discrete probability measure

$$P_n=\frac{1}{n}\sum _{k=1}^n{\delta }_{X_k},$$

where ${\delta }_x$ is the unit point mass at $x$. For a measurable $f:\mathcal{X}\to \mathbb{R}$ write $P_{n}f=\int fd{P}_n=n^{-1}{\sum }_{k=1}^{n}f(X_k)$ and $Pf=\int fdP=\mathbb{E}f(X_1)$. The empirical process indexed by $f$ is ${\mathbb{G}}_{n}f=\sqrt{n}(P_{n}f-Pf)$.

Definition (empirical distribution function). When $\mathcal{X}=\mathbb{R}$, the empirical distribution function (EDF) is

$$F_n(t)=P_n(-\infty ,t]=\frac{1}{n}\sum _{k=1}^n{1}_{\{X_k\le t\}},t\in \mathbb{R}.$$

It is the EDF that the elementary statistics curriculum estimates $F$ with; it is a right-continuous step function with jumps of size $1/n$ (or multiples, at ties) at the observations, and it is the special case $P_{n}f$ for $f=1_{(-\infty ,t]}$.

Definition (the supremum norm over a class). For a class $\mathcal{F}$ of measurable functions $f:\mathcal{X}\to \mathbb{R}$ with $P|f|<\infty$ for all $f\in \mathcal{F}$, set

$$\Vert P_n-P{\Vert }_{\mathcal{F}}=\underset{f\in \mathcal{F}}{\sup }|P_{n}f-Pf|.$$

For the EDF the relevant class is $\mathcal{F}=\{1_{(-\infty ,t]}:t\in \mathbb{R}\}$, and then $\Vert P_n-P{\Vert }_{\mathcal{F}}={\sup }_t|F_n(t)-F(t)|$, the Kolmogorov-Smirnov distance.

Definition (Glivenko-Cantelli class). A class $\mathcal{F}$ is $P$-Glivenko-Cantelli (or simply Glivenko-Cantelli, GC) if

$$\Vert P_n-P{\Vert }_{\mathcal{F}}\stackrel{a.s{.}^{\ast }}{\to }0,$$

where $\stackrel{a.s{.}^{\ast }}{\to }$ is outer almost-sure convergence (the supremum may fail to be measurable; the outer expectation ${\mathbb{E}}^{\ast }$ handles this without changing anything for the countable or pointwise-separable classes met in practice). Equivalently $\Vert P_n-P{\Vert }_{\mathcal{F}}\to 0$ in (outer) probability suffices to call $\mathcal{F}$ Glivenko-Cantelli in probability; for the classes below the two notions coincide.

Definition (bracketing number). Given two functions $\ell \le u$, the bracket $[\ell ,u]$ is the set of all $g$ with $\ell \le g\le u$ pointwise; it is an $\epsilon$-bracket in $L^1(P)$ if $P(u-\ell )\le \epsilon$. The bracketing number $N_{[]}(\epsilon ,\mathcal{F},L^1(P))$ is the minimum number of $\epsilon$-brackets needed to cover $\mathcal{F}$ (every $f\in \mathcal{F}$ lies in at least one bracket). Finiteness of $N_{[]}(\epsilon ,\mathcal{F},L^1(P))$ for every $\epsilon >0$ is the bracketing entropy condition.

Definition (Vapnik-Chervonenkis dimension). A collection $\mathcal{C}$ of subsets of $\mathcal{X}$ shatters a finite set $\{x_1,\dots ,x_m\}$ if every one of its $2^m$ subsets is cut out as $\{x_1,\dots ,x_m\}\cap C$ for some $C\in \mathcal{C}$. The VC dimension $V(\mathcal{C})$ is the largest $m$ for which some $m$-point set is shattered (and $\infty$ if arbitrarily large sets are shattered). A class of sets with $V(\mathcal{C})<\infty$ is a VC class; a class of functions is VC if the collection of its subgraphs is a VC class of sets. This is the identical combinatorial notion that governs uniform generalisation bounds in statistical learning theory; the learning-theoretic development is 45.07.03.

Key theorem with proof Intermediate+

Theorem (classical Glivenko-Cantelli). Let $X_1,X_2,\dots$ be i.i.d. real random variables with distribution function $F$, and let $F_n$ be the empirical distribution function. Then

$$\Vert F_n-F{\Vert }_{\infty }=\underset{t\in \mathbb{R}}{\sup }|F_n(t)-F(t)|\stackrel{a.s.}{\to }0.$$

Proof. The argument upgrades the pointwise strong law to uniformity by exploiting monotonicity of $F$ and a finite grid. Fix an integer $m\ge 1$. Using right-continuity and monotonicity of $F$, choose grid points

$$-\infty =t_0<t_1<\cdots <t_m=+\infty$$

such that $F(t_j-)-F(t_{j-1})\le 1/m$ for each $j$; this is possible because $F$ increases from $0$ to $1$ and has at most countably many jumps, so the values $\{i/m:0\le i\le m\}$ can be straddled by grid points, splitting any jump exceeding $1/m$ at its location. By the strong law of large numbers 37.02.02 applied to the bounded indicators $1_{\{X_k\le t_j\}}$ and $1_{\{X_k<t_j\}}$, for each fixed $j$,

$$F_n(t_j)\stackrel{a.s.}{\to }F(t_j),F_n(t_j-)\stackrel{a.s.}{\to }F(t_j-),$$

and since there are only finitely many grid points, all $2m$ of these limits hold simultaneously off a single null set $N_m$.

Fix $\omega \notin N_m$ and any $t\in \mathbb{R}$; say $t\in [t_{j-1},t_j)$. Monotonicity of both $F_n$ and $F$ gives the two-sided sandwich

$$F_n(t)-F(t)\le F_n(t_j-)-F(t_{j-1})=(F_n(t_j-)-F(t_j-))+(F(t_j-)-F(t_{j-1}))\le (F_n(t_j-)-F(t_j-))+\frac{1}{m},$$ $$F_n(t)-F(t)\ge F_n(t_{j-1})-F(t_j-)=(F_n(t_{j-1})-F(t_{j-1}))-(F(t_j-)-F(t_{j-1}))\ge (F_n(t_{j-1})-F(t_{j-1}))-\frac{1}{m}.$$

Taking the supremum over $t$ and then ${\mathrm{limsup}}_n$, every grid-point difference vanishes off $N_m$, leaving

$$\underset{n\to \infty }{\mathrm{limsup}}\underset{t}{\sup }|F_n(t)-F(t)|\le \frac{1}{m}\text{for all }\omega \notin N_m.$$

Let $N={\bigcup }_m{N}_m$, a null set. For $\omega \notin N$ the bound holds for every $m$, so the $\mathrm{limsup}$ is $0$, which is uniform almost-sure convergence. $\square$

Bridge. The grid-and-monotonicity device builds toward the abstract Glivenko-Cantelli theorem, where monotonicity is replaced by the more flexible bracketing of a function class, and it appears again in the uniform law of large numbers that drives M-estimator consistency 45.04.04, where the objective function must be controlled uniformly over the parameter. The foundational reason a pointwise strong law lifts to a uniform one is that a class small enough to be straddled by finitely many brackets of small $L^1(P)$ width can only oscillate, between brackets, by the bracket widths; this is exactly the mechanism by which the indicators $1_{(-\infty ,t]}$ — totally ordered by $t$ and hence bracketable by a coarse grid of quantiles — are tamed. The classical theorem generalises in two directions that the chapter pursues in parallel: the bracketing route, which measures the size of $\mathcal{F}$ by $L^1(P)$-covering with brackets, and the combinatorial Vapnik-Chervonenkis route, which measures it by shattering. Putting these together, the empirical measure $P_n$ is a uniformly consistent estimator of $P$ over any class that is not too rich, and the bridge is the passage from the single distribution function $F$ to an arbitrary index class $\mathcal{F}$, which is the move that opens empirical-process theory.

Exercises Intermediate+

Advanced results Master

Theorem 1 (bracketing Glivenko-Cantelli). If $N_{[]}(\epsilon ,\mathcal{F},L^1(P))<\infty$ for every $\epsilon >0$, then $\mathcal{F}$ is $P$-Glivenko-Cantelli, with convergence in outer almost-sure sense ^{[van der Vaart Wellner 1996]}. The proof brackets $\mathcal{F}$ by finitely many $L^1(P)$-small brackets and applies the strong law to the integrable endpoints; the bracket width controls the oscillation of $P_{n}f-Pf$ within each bracket, and the strong law controls the finitely many endpoints. The classical theorem is the special case of the totally ordered class $\{1_{(-\infty ,t]}\}$, where the brackets are quantile cells and the bracketing number is $O(1/\epsilon )$.

Theorem 2 (VC Glivenko-Cantelli). If $\mathcal{C}$ is a VC class of sets with $V(\mathcal{C})<\infty$ (more generally if $\mathcal{F}$ is a VC class of functions with integrable envelope $F$, $PF<\infty$), then $\mathcal{F}$ is $P$-Glivenko-Cantelli for every $P$ — the property is distribution-free ^{[Vapnik Chervonenkis 1971]}. The mechanism is symmetrisation followed by Sauer's lemma: the expected uniform deviation is bounded by a Rademacher average over the at most ${\sum }_{i\le V}\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le (n+1{)}^V$ distinct sample-traces, and the polynomial growth against the $\sqrt{n}$ normalisation forces ${\mathbb{E}}^{\ast }\Vert P_n-P{\Vert }_{\mathcal{F}}\to 0$; a concentration (bounded-difference) inequality upgrades the mean convergence to almost-sure. The same finite-VC hypothesis is the exact condition under which empirical risk minimisation generalises in statistical learning theory 45.07.03.

Theorem 3 (Dvoretzky-Kiefer-Wolfowitz, Massart's constant). For i.i.d. real data with any distribution function $F$ and every $\epsilon >0$,

$$\mathbb{P}(\underset{t}{\sup }|F_n(t)-F(t)|>\epsilon )\le 2e^{-2n{\epsilon }^2},$$

with the constant $2$ sharp ^{[Massart 1990]}; the original DKW bound ^{[Dvoretzky Kiefer Wolfowitz 1956]} carried an unspecified constant. This is a non-asymptotic, distribution-free, uniform tail for the EDF, strictly stronger than what Hoeffding gives at a single $t$, and it yields the exact-coverage Kolmogorov-Smirnov confidence band $F_n(t)\pm \sqrt{(2n{)}^{-1}\log (2/\alpha )}$. The asymptotic constant matches: $\sqrt{n}{\sup }_t|F_n-F|$ converges in law to the supremum of a Brownian bridge, whose tail is $2{\sum }_{j\ge 1}(-1{)}^{j-1}{e}^{-2j^2{x}^2}\sim 2e^{-2x^2}$, the Kolmogorov distribution.

Theorem 4 (uniform-entropy / Pollard's GC theorem). If $\mathcal{F}$ has integrable envelope $F$ and finite uniform-entropy integral in the weak sense that ${\sup }_{Q}N(\epsilon \Vert F{\Vert }_{Q,1},\mathcal{F},L^1(Q))<\infty$ for each $\epsilon$ (supremum over finitely supported probability measures $Q$), then $\mathcal{F}$ is $P$-Glivenko-Cantelli ^{[van der Vaart Wellner 1996]}. VC classes satisfy the uniform-entropy bound by Sauer's lemma, so Theorem 2 is the combinatorial corollary; bracketing classes satisfy Theorem 1 instead. The two entropy regimes — bracketing in a fixed $L^r(P)$ versus uniform covering across all $Q$ — are the two standard sufficient conditions, neither containing the other.

Theorem 5 (preservation and consequences). The Glivenko-Cantelli property is stable under the operations that arise in plug-in statistics: if $\mathcal{F}$ and $\mathcal{G}$ are $P$-GC with integrable envelopes and $\phi$ is Lipschitz, then $\phi \circ (\mathcal{F},\mathcal{G})$, finite sums, finite products of uniformly bounded GC classes, and pointwise minima/maxima are again $P$-GC ^{[van der Vaart 1998]}. The statistical payoff is uniform consistency of M-estimators: if the criterion functions $\{m_{\theta }:\theta \in \Theta \}$ form a GC class, then ${\sup }_{\theta }|P_n{m}_{\theta }-P{m}_{\theta }|\to 0$ a.s., which is exactly the uniform law of large numbers that, with a well-separated maximum, forces argmax consistency 45.04.04.

Synthesis. The empirical measure $P_n$ is the most economical estimator of $P$, and the entire chapter is the study of when it is a uniformly good one. The foundational reason a pointwise strong law lifts to a uniform law over a class $\mathcal{F}$ is that the class must be small in a sense that admits a finite description at every resolution: either bracketed by finitely many $L^1(P)$-small brackets, or shattering only sets up to a finite VC dimension, and these are two faces of one demand on the metric entropy of $\mathcal{F}$. This is exactly the dichotomy that organises the subject — bracketing entropy controls classes through a fixed reference measure, uniform entropy controls them combinatorially and distribution-free — and the classical Glivenko-Cantelli theorem is the point where both routes degenerate to the totally ordered indicator class with $V=1$ and $O(1/\epsilon )$ brackets.

Putting these together, the DKW inequality supplies the sharp non-asymptotic rate that the qualitative theorems leave open, and its asymptotic shadow is the Brownian-bridge supremum that Donsker's empirical-process limit 37.03.03 makes precise, so the EDF's worst gap has a finite-sample exponential tail and a limiting Kolmogorov law that agree in their leading constant. The central insight is that the VC condition that makes $P_n$ uniformly consistent here is identical to the condition that makes empirical risk minimisation generalise in learning theory 45.07.03: uniform convergence of empirical means to population means over a hypothesis class is simultaneously the engine of nonparametric statistics and of statistical learning, and Glivenko-Cantelli is its qualitative skeleton, with Donsker the quantitative refinement that adds a limit law on top.

Full proof set Master

Proposition 1 (the classical theorem as a bracketing corollary). The class $\mathcal{F}=\{1_{(-\infty ,t]}:t\in \mathbb{R}\}$ has bracketing number $N_{[]}(\epsilon ,\mathcal{F},L^1(P))\le \lceil 1/\epsilon \rceil +1$, and is therefore $P$-Glivenko-Cantelli for every $P$.

Proof. Pick quantile grid points $-\infty =t_0<t_1<\cdots <t_m=+\infty$ with $F(t_j-)-F(t_{j-1})\le \epsilon$, achievable with $m\le \lceil 1/\epsilon \rceil +1$ since $F$ rises from $0$ to $1$. Form the brackets $[{\ell }_j,u_j]$ with ${\ell }_j=1_{(-\infty ,t_{j-1}]}$ and $u_j=1_{(-\infty ,t_j)}$. Any $1_{(-\infty ,t]}$ with $t\in [t_{j-1},t_j)$ satisfies ${\ell }_j\le 1_{(-\infty ,t]}\le u_j$ pointwise, and $P(u_j-{\ell }_j)=F(t_j-)-F(t_{j-1})\le \epsilon$. So $m$ brackets of $L^1(P)$-width $\le \epsilon$ cover $\mathcal{F}$, giving the stated bound. Finiteness of the bracketing number for every $\epsilon$ invokes the bracketing Glivenko-Cantelli theorem (Proposition 2 below), recovering ${\sup }_t|F_n-F|\to 0$ a.s. without the explicit grid sandwich of the Key theorem. $\square$

Proposition 2 (bracketing Glivenko-Cantelli). If $N_{[]}(\epsilon ,\mathcal{F},L^1(P))<\infty$ for every $\epsilon >0$, then $\Vert P_n-P{\Vert }_{\mathcal{F}}\stackrel{a.s{.}^{\ast }}{\to }0$.

Proof. Fix $\epsilon >0$ and brackets $[{\ell }_i,u_i{]}_{i=1}^N$ of $L^1(P)$-width $\le \epsilon$ covering $\mathcal{F}$, endpoints integrable. For $f\in \mathcal{F}$ in bracket $i$,

$$P_{n}f-Pf\le P_n{u}_i-Pf=(P_n{u}_i-P{u}_i)+P(u_i-f)\le (P_n{u}_i-P{u}_i)+P(u_i-{\ell }_i),$$

and the lower bound is symmetric with ${\ell }_i$. Hence $\Vert P_n-P{\Vert }_{\mathcal{F}}\le {\max }_i(|P_n{u}_i-P{u}_i|\vee |P_n{\ell }_i-P{\ell }_i|)+\epsilon$. The maximum is over $2N$ averages each governed by the strong law of large numbers 37.02.02, so it tends to $0$ almost surely; therefore ${\mathrm{limsup}}_n\Vert P_n-P{\Vert }_{\mathcal{F}}\le \epsilon$ a.s. Intersecting the corresponding full-measure events over $\epsilon =1/k$ gives ${\mathrm{limsup}}_n\Vert P_n-P{\Vert }_{\mathcal{F}}=0$ a.s. Measurability issues are absorbed into the outer expectation, under which the max of finitely many measurable averages is measurable and the bound is exact. $\square$

Proposition 3 (Sauer-Shelah lemma). If $\mathcal{C}$ shatters no set of size $V+1$, then for every $n$ and every $n$-point set, $\#\{\{x_1,\dots ,x_n\}\cap C:C\in \mathcal{C}\}\le {\sum }_{i=0}^V\left(\genfrac{}{}{0ex}{}{n}{i}\right)$.

Proof. Induct on $n+V$. Write $\Phi (n,V)={\sum }_{i=0}^V\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. Fix points $S=\{x_1,\dots ,x_n\}$ and let $\mathcal{T}=\{S\cap C:C\in \mathcal{C}\}$ be the trace, a set system on $S$ shattering no $(V+1)$-subset. Remove $x_n$: let ${\mathcal{T}}^{\prime }=\{T\setminus \{x_n\}:T\in \mathcal{T}\}$ be the trace on $S^{\prime }=S\setminus \{x_n\}$, and let ${\mathcal{T}}^{\prime \prime }=\{T\in {\mathcal{T}}^{\prime }:T\in \mathcal{T}\text{ and }T\cup \{x_n\}\in \mathcal{T}\}$ be the family of subsets of $S^{\prime }$ appearing both with and without $x_n$. Then $|\mathcal{T}|=|{\mathcal{T}}^{\prime }|+|{\mathcal{T}}^{\prime \prime }|$, because each $T^{\prime }\in {\mathcal{T}}^{\prime }$ lifts to one member of $\mathcal{T}$ unless both extensions are present, contributing the extra count $|{\mathcal{T}}^{\prime \prime }|$. Now ${\mathcal{T}}^{\prime }$ shatters no $(V+1)$-subset of $S^{\prime }$ (a shattered subset would be shattered in $\mathcal{T}$), so $|{\mathcal{T}}^{\prime }|\le \Phi (n-1,V)$ by induction. And ${\mathcal{T}}^{\prime \prime }$ shatters no $V$-subset of $S^{\prime }$: if it shattered a $V$-set $A\subseteq S^{\prime }$, then $\mathcal{T}$ would shatter $A\cup \{x_n\}$, a $(V+1)$-set, since every subset of $A$ appears in ${\mathcal{T}}^{\prime \prime }$ both with and without $x_n$. Hence $|{\mathcal{T}}^{\prime \prime }|\le \Phi (n-1,V-1)$. Adding, $|\mathcal{T}|\le \Phi (n-1,V)+\Phi (n-1,V-1)=\Phi (n,V)$ by Pascal's identity. $\square$

Proposition 4 (VC Glivenko-Cantelli via symmetrisation). Let $\mathcal{C}$ be a VC class of sets with $V(\mathcal{C})=V<\infty$. Then ${\mathbb{E}}^{\ast }\Vert P_n-P{\Vert }_{\mathcal{C}}\to 0$, and consequently $\Vert P_n-P{\Vert }_{\mathcal{C}}\stackrel{a.s{.}^{\ast }}{\to }0$.

Proof. Let $X_1^{\prime },\dots ,X_n^{\prime }$ be an independent ghost sample with empirical measure $P_n^{\prime }$, and ${\sigma }_1,\dots ,{\sigma }_n$ independent Rademacher signs independent of the data. By the standard symmetrisation inequality,

$${\mathbb{E}}^{\ast }\Vert P_n-P{\Vert }_{\mathcal{C}}\le 2{\mathbb{E}}^{\ast }\Vert \frac{1}{n}\sum _{k=1}^n{\sigma }_k{1}_C(X_k){\Vert }_{\mathcal{C}}.$$

Condition on $X_1,\dots ,X_n$. The sets of $\mathcal{C}$ induce at most ${\Delta }_n(\mathcal{C})\le \Phi (n,V)\le (n+1{)}^V$ distinct vectors $(1_C(X_1),\dots ,1_C(X_n))$ by Proposition 3. For each fixed such vector $v\in \{0,1{\}}^n$, $n^{-1}{\sum }_k{\sigma }_k{v}_k$ is a Rademacher average with ${\sum }_k{v}_k^2\le n$, hence sub-Gaussian with parameter $\le 1/n$; the maximal inequality over $M$ sub-Gaussian variables gives

$${\mathbb{E}}_{\sigma }\underset{C}{\max }|\frac{1}{n}\sum _k{\sigma }_k{1}_C(X_k)|\le \sqrt{\frac{2\log (2{\Delta }_n(\mathcal{C}))}{n}}\le \sqrt{\frac{2(V\log (n+1)+\log 2)}{n}}.$$

The right-hand side is deterministic and tends to $0$, so taking expectations over the data, ${\mathbb{E}}^{\ast }\Vert P_n-P{\Vert }_{\mathcal{C}}\le 2\sqrt{2(V\log (n+1)+\log 2)/n}\to 0$. For the almost-sure upgrade, $\Vert P_n-P{\Vert }_{\mathcal{C}}$ is a function of $n$ independent variables changing by at most $1/n$ when one is altered, so the bounded-difference (McDiarmid) inequality gives $\mathbb{P}(|\Vert P_n-P{\Vert }_{\mathcal{C}}-{\mathbb{E}}^{\ast }\Vert P_n-P{\Vert }_{\mathcal{C}}|>t)\le 2e^{-2n{t}^2}$; summability over $n$ and Borel-Cantelli, combined with the mean tending to $0$, yield $\Vert P_n-P{\Vert }_{\mathcal{C}}\to 0$ a.s. $\square$

Proposition 5 (DKW gives the classical theorem with a rate). With the DKW inequality $\mathbb{P}({\sup }_t|F_n-F|>\epsilon )\le 2e^{-2n{\epsilon }^2}$ in hand, ${\sup }_t|F_n-F|\stackrel{a.s.}{\to }0$, and moreover ${\mathrm{limsup}}_n\sqrt{n/\log \log n}{\sup }_t|F_n-F|\le 1/\sqrt{2}$ almost surely.

Proof. For fixed $\epsilon$, ${\sum }_{n}2e^{-2n{\epsilon }^2}<\infty$, so by the first Borel-Cantelli lemma ${\sup }_t|F_n-F|>\epsilon$ finitely often a.s.; intersecting over $\epsilon =1/k$ gives a.s. convergence to $0$, a second proof of Glivenko-Cantelli requiring no monotonicity grid, only the uniform tail. For the rate, set ${\epsilon }_n=\sqrt{(1+\delta )\log \log n/(2n)}$; then $2e^{-2n{\epsilon }_n^2}=2(\log n{)}^{-(1+\delta )}$, which is summable along $n_j=\lfloor {\rho }^j\rfloor$ for $\rho >1$. Borel-Cantelli along this subsequence plus the monotone control of ${\sup }_t|F_n-F|$ between consecutive $n_j$ gives ${\mathrm{limsup}}_n\sqrt{n/\log \log n}{\sup }_t|F_n-F|\le \sqrt{(1+\delta )/2}$ a.s.; let $\delta \downarrow 0$. (The matching lower bound, giving equality $1/\sqrt{2}$, is the Smirnov-Chung law of the iterated logarithm for the EDF.) $\square$

Connections Master

The strong law of large numbers 37.02.02 is the sole probabilistic input to every Glivenko-Cantelli theorem in this unit: the classical proof applies it to the finitely many grid indicators, the bracketing proof applies it to the finitely many bracket endpoints, and the VC proof applies a concentration refinement of it (McDiarmid) to upgrade mean convergence to almost-sure. Glivenko-Cantelli is precisely the statement that the strong law holds uniformly over an index class, so this unit is the uniform-in-index extension of that one.

Consistency and the modes of stochastic convergence 45.04.01 supply the language: the GC property is uniform-in-$\mathcal{F}$ almost-sure consistency of the plug-in estimator $P_n$ for $P$, and the M-estimator argmax route previewed there is completed here, since the uniform law of large numbers ${\sup }_{\theta }|P_n{m}_{\theta }-P{m}_{\theta }|\to 0$ that the Wald argument needs is exactly the assertion that $\{m_{\theta }\}$ is a Glivenko-Cantelli class.

Donsker's invariance principle and the functional CLT 37.03.03 is the quantitative successor: where Glivenko-Cantelli gives ${\sup }_t|F_n-F|\to 0$, the empirical-process invariance principle gives $\sqrt{n}(F_n-F)\Rightarrow$ an $F$-Brownian bridge in $D[0,1]$, whose supremum is the limiting Kolmogorov-Smirnov law, and the DKW exponential tail $2e^{-2n{\epsilon }^2}$ is the finite-sample shadow of that bridge-supremum tail. The Donsker property is to Glivenko-Cantelli what the central limit theorem is to the law of large numbers.

The Vapnik-Chervonenkis theory of learnability 45.07.03 uses the identical VC-dimension and Sauer-lemma machinery proved here: finite VC dimension is simultaneously the condition under which the empirical measure converges uniformly to $P$ (this unit) and the condition under which empirical risk minimisation generalises, so the GC theorem for a VC class and the fundamental theorem of statistical learning are two readings of one uniform-convergence result.

Bernstein's inequality and the sub-exponential regime 45.05.01 furnishes the concentration tools that sharpen these qualitative theorems into rates: the bounded-difference inequality used to upgrade VC mean-convergence to almost-sure convergence, and the sub-Gaussian maximal inequality bounding the Rademacher average over the polynomially many sample-traces, are members of the same concentration family, and they reappear when bracketing entropy is integrated to obtain rates rather than mere convergence.

Historical & philosophical context Master

The uniform convergence of the empirical distribution function was established in 1933 by Valery Glivenko and Francesco Paolo Cantelli in companion papers in the Giornale dell'Istituto Italiano degli Attuari ^{[Glivenko 1933]}. Glivenko proved the result for continuous distribution functions and Cantelli removed the continuity assumption, giving the general statement that the sample distribution function converges to the population distribution function uniformly with probability one. This was the first uniform law of large numbers and the prototype for all later empirical-process theory; the name fundamental theorem of statistics records its role in justifying the sample as a stand-in for the population.

The sharp non-asymptotic form was obtained in 1956 by Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz ^{[Dvoretzky Kiefer Wolfowitz 1956]}, who proved an exponential bound $C{e}^{-2n{\epsilon }^2}$ on the uniform deviation in the course of establishing the asymptotic minimax optimality of the empirical distribution function; the optimal constant $C=2$ resisted proof until Pascal Massart settled it in 1990 ^{[Massart 1990]}. The abstraction from the single distribution function to arbitrary classes of sets came from Vladimir Vapnik and Alexey Chervonenkis in 1971 ^{[Vapnik Chervonenkis 1971]}, whose study of uniform convergence of relative frequencies introduced the combinatorial dimension now bearing their names and the shatter-coefficient bound, work undertaken in the service of pattern recognition and later recognised as the combinatorial core of both nonparametric statistics and statistical learning. Richard Dudley and David Pollard subsequently built the metric-entropy and symmetrisation framework that unifies the bracketing and combinatorial routes, the synthesis codified in van der Vaart and Wellner's monograph ^{[van der Vaart Wellner 1996]}.

Bibliography Master

@article{Glivenko1933gc,
  author  = {Glivenko, Valery I.},
  title   = {Sulla determinazione empirica delle leggi di probabilit\`a},
  journal = {Giornale dell'Istituto Italiano degli Attuari},
  volume  = {4},
  year    = {1933},
  pages   = {92--99}
}

@article{Cantelli1933gc,
  author  = {Cantelli, Francesco Paolo},
  title   = {Sulla determinazione empirica delle leggi di probabilit\`a},
  journal = {Giornale dell'Istituto Italiano degli Attuari},
  volume  = {4},
  year    = {1933},
  pages   = {221--424}
}

@article{DKW1956,
  author  = {Dvoretzky, Aryeh and Kiefer, Jack and Wolfowitz, Jacob},
  title   = {Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator},
  journal = {Annals of Mathematical Statistics},
  volume  = {27},
  number  = {3},
  year    = {1956},
  pages   = {642--669}
}

@article{Massart1990,
  author  = {Massart, Pascal},
  title   = {The tight constant in the {Dvoretzky-Kiefer-Wolfowitz} inequality},
  journal = {Annals of Probability},
  volume  = {18},
  number  = {3},
  year    = {1990},
  pages   = {1269--1283}
}

@article{VC1971,
  author  = {Vapnik, Vladimir N. and Chervonenkis, Alexey Ya.},
  title   = {On the uniform convergence of relative frequencies of events to their probabilities},
  journal = {Theory of Probability and Its Applications},
  volume  = {16},
  number  = {2},
  year    = {1971},
  pages   = {264--280}
}

@book{vanderVaart1998gc,
  author    = {van der Vaart, Aad W.},
  title     = {Asymptotic Statistics},
  publisher = {Cambridge University Press},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  year      = {1998}
}

@book{vanderVaartWellner1996,
  author    = {van der Vaart, Aad W. and Wellner, Jon A.},
  title     = {Weak Convergence and Empirical Processes: With Applications to Statistics},
  publisher = {Springer-Verlag},
  series    = {Springer Series in Statistics},
  address   = {New York},
  year      = {1996}
}

@book{Dudley1999,
  author    = {Dudley, Richard M.},
  title     = {Uniform Central Limit Theorems},
  publisher = {Cambridge University Press},
  series    = {Cambridge Studies in Advanced Mathematics 63},
  year      = {1999}
}