---
tag: E7B78X780X
kind: statement
role: theorem
name: Glivenko–Cantelli theorem
msc: [62G30, 60F15]
uses: [00MRN0FARV, 0H8H7ZTHW2, 0ST21PGDAP, 08VZ57PT26]
about: [0H8H7ZTHW2]
sources:
  - url: https://en.wikipedia.org/wiki/Glivenko%E2%80%93Cantelli_theorem
same_as:
  wikidata: Q544369
  wikipedia: Glivenko–Cantelli theorem
---

## Statement

Let $X_1, X_2, \dots$ be [[i.i.d.|00MRN0FARV]] real random variables with [[cumulative distribution function|0H8H7ZTHW2]] $F$.
For $n \ge 1$ and $x \in \R$, let
$$F_n(x) = \frac{1}{n} \#\set{k \le n : X_k \le x}$$
be the empirical distribution function.
Then, [[almost surely|0ST21PGDAP]],
$$\sup_{x \in \R} \abs{F_n(x) - F(x)} \to 0 \quad \text{as } n \to \infty.$$

## Remarks

For each fixed $x$, the [[strong law of large numbers|0DFWHQ839T]] applied to the indicators $\mathbf{1}_{\set{X_k \le x}}$ gives $F_n(x) \to F(x)$ almost surely.
The same holds for the left limits $F_n(x-) \to F(x-)$.
To make the convergence [[uniform|08VZ57PT26]], choose finitely many points $x_0 < x_1 < \cdots < x_m$ such that $F$ grows by at most $\varepsilon$ between consecutive points, apart from jumps at the points themselves.
Since $F_n$ and $F$ are non-decreasing, the uniform error is at most $\varepsilon$ plus the error at these finitely many points.

Example: if the $X_k$ are uniform on $[0, 1]$, then the step function $F_n$ lies within any fixed distance of the line $F(x) = x$ on $[0, 1]$, for all large $n$, almost surely.

The rate is given by the Dvoretzky–Kiefer–Wolfowitz inequality, and the fluctuations of order $n^{-1/2}$ are described by the [[empirical process|XKFG1676CG]] and [[Donsker's theorem|818832PMSV]].

## Explanations

### L1 human

Take a large sample from an unknown distribution and draw the step function that records which fraction of the sample lies below each value.
This step function gets close to the true distribution function everywhere at once as the sample grows.
So a large sample reveals the whole distribution, not only its mean.

### L2 human

The theorem is often called the fundamental theorem of statistics, since it justifies estimating a distribution by its empirical version.
It is the first uniform law of large numbers.
Empirical process theory generalises it to classes of sets or functions, called Glivenko–Cantelli classes, on which the empirical averages converge uniformly; the Vapnik–Chervonenkis condition is a sufficient criterion.