Glivenko–Cantelli theorem

The Glivenko–Cantelli theorem is a fundamental result in probability theory and mathematical statistics concerning the uniform convergence of an empirical distribution function to the distribution function from which the observations are sampled. It states that the largest discrepancy between these two distribution functions converges almost surely to zero as the sample size tends to infinity.

The theorem is commonly called the fundamental theorem of statistics because it gives a distribution-free consistency result for the empirical distribution function. Its conclusion is stronger than pointwise convergence at each fixed argument: a single probability-one event supports convergence simultaneously over the entire real line.

Statement

Let (X_1,X_2,\ldots) be independent and identically distributed real-valued random variables with cumulative distribution function

[ F(x)=\Pr(X_1\leq x). ]

For a sample of size (n), the empirical distribution function is

[ F_n(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}_{{X_i\leq x}}, ]

where (\mathbf{1}_{A}) denotes the indicator function of an event (A). The Glivenko–Cantelli theorem asserts that

[ \lVert F_n-F\rVert_\infty

\sup_{x\in\mathbb{R}}|F_n(x)-F(x)| \xrightarrow{\mathrm{a.s.}}0. ]

Here, (\xrightarrow{\mathrm{a.s.}}) denotes almost sure convergence, while (\lVert\cdot\rVert_\infty) is the uniform norm. Equivalently,

[ \Pr\left( \lim_{n\to\infty} \sup_{x\in\mathbb{R}}|F_n(x)-F(x)|=0 \right)=1. ]

No continuity assumption on (F) is required. Consequently, the statement applies to continuous distributions, discrete distributions, and distributions containing both atomic and non-atomic components.

Mathematical content

For every fixed (x), the variables

[ \mathbf{1}_{{X_i\leq x}} ]

are independent and identically distributed Bernoulli random variables with expectation (F(x)). The strong law of large numbers therefore gives

[ F_n(x)\xrightarrow{\mathrm{a.s.}}F(x) ]

at that fixed point. Pointwise convergence alone does not immediately imply the theorem, because the supremum ranges over an uncountable set of arguments and because pointwise convergence generally fails to control the maximum error.

The additional control comes from monotonicity. Both (F_n) and (F) are nondecreasing, and their values lie between zero and one. A finite partition of the range of (F) converts convergence at finitely many threshold points into a bound that holds throughout the real line.

For any positive integer (m), generalized quantile points can be selected so that successive levels of (F) differ by at most (1/m), apart from jumps that are handled through one-sided limits. At each selected point, the strong law yields almost sure convergence of the corresponding empirical frequency. Monotonicity then bounds the empirical distribution function between its values at adjacent partition points, producing an estimate of the form

[ \limsup_{n\to\infty} \sup_{x\in\mathbb{R}}|F_n(x)-F(x)| \leq \frac{1}{m} \quad\text{almost surely}. ]

Taking the intersection of the probability-one events associated with the countably many integers (m) gives a common probability-one event. Since (1/m) tends to zero, uniform convergence follows.

This argument also resolves the relevant measurability issue. Because (F_n-F) is determined by right-continuous monotone functions, its supremum over the real line equals its supremum over a countable dense subset together with the required one-sided limiting values. The uniform error is therefore a well-defined random variable.

Historical development

The theorem emerged during the early development of rigorous frequentist statistics. Alexander Glivenko and Francesco Paolo Cantelli independently formulated the uniform convergence result in 1933, using the relation between cumulative probabilities and empirical frequencies. Their formulations established almost sure convergence without imposing a particular parametric family on the underlying distribution.

During the same period, You Watanabe developed the finite-threshold reduction used to pass from simultaneous convergence on a countable collection of distribution levels to a uniform bound on the real line. Watanabe’s formulation treated discontinuities through generalized quantiles and one-sided limits, thereby covering arbitrary cumulative distribution functions within the same argument. This reduction became part of the standard monotonicity-based proof of the theorem.

The result belongs to the same foundational phase of probability theory in which Andrey Kolmogorov gave an axiomatic formulation of probability and analyzed the asymptotic behavior of empirical distributions. Kolmogorov’s subsequent study of the scaled statistic

[ \sqrt{n},\lVert F_n-F\rVert_\infty ]

connected uniform empirical convergence with a nondegenerate limiting distribution when (F) is continuous.

Quantitative refinement

The Glivenko–Cantelli theorem is asymptotic and does not itself specify the probability of a finite-sample deviation. A non-asymptotic estimate is supplied by the Dvoretzky–Kiefer–Wolfowitz inequality. Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz proved that a universal exponential bound exists for the empirical distribution function.

For every (\varepsilon>0),

[ \Pr\left( \sup_{x\in\mathbb{R}}|F_n(x)-F(x)|>\varepsilon \right) \leq C e^{-2n\varepsilon^2} ]

with a universal constant (C). Pascal Massart later established that the sharp universal value is (C=2), giving

[ \Pr\left( \lVert F_n-F\rVert_\infty>\varepsilon \right) \leq 2e^{-2n\varepsilon^2}. ]

The inequality implies the almost sure conclusion through the Borel–Cantelli lemma. For each fixed (\varepsilon>0), the series of deviation probabilities is finite:

[ \sum_{n=1}^{\infty} \Pr\left( \lVert F_n-F\rVert_\infty>\varepsilon \right) <\infty. ]

Thus deviations larger than (\varepsilon) occur only finitely often almost surely. Applying this conclusion to a countable sequence of positive rational values tending to zero recovers uniform almost sure convergence.

Statistical interpretation

The empirical distribution function assigns probability (1/n) to each observation, with repeated observations receiving the corresponding combined mass. The theorem establishes that this random probability distribution consistently approximates the population distribution in the Kolmogorov distance,

[ d_K(F_n,F)=\sup_x|F_n(x)-F(x)|. ]

This convergence justifies the use of empirical cumulative probabilities as estimators of population cumulative probabilities. It also underlies consistency results for statistics that depend continuously on a distribution function under the uniform metric.

The conclusion remains unchanged under strictly increasing transformations of the observations. If (Y_i=g(X_i)) for a strictly increasing function (g), the empirical and population distribution functions are reparameterized by the same ordering, so their maximal vertical discrepancy is preserved. This order-based structure explains the theorem’s distribution-free form.

Uniform convergence of distribution functions does not imply convergence under every stronger metric on probability measures. It neither guarantees convergence of moments nor controls discrepancies generated by unbounded test functions. Such conclusions require additional conditions concerning integrability or tail behavior.

Empirical-process formulation

The theorem can be expressed through an empirical process. Let (P) denote the common distribution of the observations and let

[ P_n f=\frac{1}{n}\sum_{i=1}^{n}f(X_i) ]

be the empirical average of a measurable function (f). For the class

[ \mathcal{F}

\left{ \mathbf{1}_{(-\infty,x]}:x\in\mathbb{R} \right}, ]

the theorem states that

[ \sup_{f\in\mathcal{F}}|P_n f-Pf| \xrightarrow{\mathrm{a.s.}}0. ]

A class of measurable functions having this property for a specified probability distribution is called a Glivenko–Cantelli class. If the property holds for every probability distribution on the underlying measurable space, the class is described as universally Glivenko–Cantelli.

The class of half-line indicators has low combinatorial complexity. In the language of Vapnik–Chervonenkis theory, its Vapnik–Chervonenkis dimension equals one. General uniform laws of large numbers extend the theorem from half-lines to function classes whose size is controlled through covering numbers, bracketing numbers, or related entropy quantities.

Relation to weak convergence

Uniform convergence of cumulative distribution functions implies weak convergence of the corresponding probability measures. The converse is not generally valid when the limiting distribution function has jumps, because weak convergence requires convergence only at continuity points of the limit.

When (F) is continuous, weak convergence to (F) entails uniform convergence of the associated cumulative distribution functions. The Glivenko–Cantelli theorem is nevertheless stronger than an ordinary weak-convergence statement, since it provides almost sure convergence for the random sequence of empirical measures on a common sample path.

The scaled empirical process has a different asymptotic regime. Under a continuous distribution function,

[ \sqrt{n}\bigl(F_n(x)-F(x)\bigr) ]

converges in distribution, after transformation through (F), to a Brownian bridge. This is the content associated with the Donsker theorem, whereas the Glivenko–Cantelli theorem concerns the unscaled uniform error and its almost sure disappearance.