Glivenko–Cantelli theorem

Proof

For simplicity, consider a case of continuous random variable ${\displaystyle X}$. Fix ${\displaystyle -\mathrm{\infty }=x_0<x_1<\cdots <x_{m-1}<x_m=\mathrm{\infty }}$ such that ${\displaystyle F(x_j)-F(x_{j-1})=\frac{1}{m}}$ for ${\displaystyle j=1,\dots ,m}$. Now for all ${\displaystyle x\in \mathbb{R}}$ there exists ${\displaystyle j\in \{1,\dots ,m\}}$ such that ${\displaystyle x\in [x_{j-1},x_j]}$.

${\displaystyle \begin{array}{cc}{F}_n(x)-F(x)& \le F_n(x_j)-F(x_{j-1})=F_n(x_j)-F(x_j)+\frac{1}{m},\\ F_n(x)-F(x)& \ge F_n(x_{j-1})-F(x_j)=F_n(x_{j-1})-F(x_{j-1})-\frac{1}{m}.\end{array}}$

Therefore,

${\displaystyle \Vert F_n-F{\Vert }_{\mathrm{\infty }}=\underset{x\in \mathbb{R}}{sup}|F_n(x)-F(x)|\le \underset{j\in \{1,\dots ,m\}}{max}|F_n(x_j)-F(x_j)|+\frac{1}{m}.}$

Since $\underset{j\in \{1,\dots ,m\}}{max}|F_n(x_j)-F(x_j)|\to 0\text{ a.s.}$ by strong law of large numbers, we can guarantee that for any positive $\epsilon$ and any integer $m$ such that $1/m<\epsilon$, we can find $N$ such that for all ${\displaystyle n\ge N}$, we have $\underset{j\in \{1,\dots ,m\}}{max}|F_n(x_j)-F(x_j)|\le \epsilon -1/m\text{ a.s.}$. Combined with the above result, this further implies that $\Vert F_n-F{\Vert }_{\mathrm{\infty }}\le \epsilon \text{ a.s.}$, which is the definition of almost sure convergence.

Empirical measures

One can generalize the empirical distribution function by replacing the set ${\displaystyle (-\mathrm{\infty },x]}$ by an arbitrary set C from a class of sets ${\displaystyle \mathcal{C}}$ to obtain an empirical measure indexed by sets ${\displaystyle C\in \mathcal{C}.}$

${\displaystyle P_n(C)=\frac{1}{n}\sum _{i=1}^n{I}_C(X_i),C\in \mathcal{C}}$

Where ${\displaystyle I_C(x)}$ is the indicator function of each set ${\displaystyle C}$.

Further generalization is the map induced by ${\displaystyle P_n}$ on measurable real-valued functions f, which is given by

${\displaystyle f\mapsto P_{n}f={\int }_{S}fd{P}_n=\frac{1}{n}\sum _{i=1}^{n}f(X_i),f\in \mathcal{F}.}$

Then it becomes an important property of these classes whether the strong law of large numbers holds uniformly on ${\displaystyle \mathcal{F}}$ or ${\displaystyle \mathcal{C}}$.

Glivenko–Cantelli class

Consider a set ${\displaystyle \mathcal{S}}$ with a sigma algebra of Borel subsets A and a probability measure ${\displaystyle \mathbb{P}.}$ For a class of subsets,

${\displaystyle \mathcal{C}\subset \{C:C\text{ is measurable subset of }\mathcal{S}\}}$

and a class of functions

${\displaystyle \mathcal{F}\subset \{f:\mathcal{S}\to \mathbb{R},f\text{ is measurable}\}}$

define random variables

${\displaystyle \Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{C}}=\underset{C\in \mathcal{C}}{sup}|{\mathbb{P}}_n(C)-\mathbb{P}(C)|}$

${\displaystyle \Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}}=\underset{f\in \mathcal{F}}{sup}|{\mathbb{P}}_{n}f-\mathbb{P}f|}$

where ${\displaystyle {\mathbb{P}}_n(C)}$ is the empirical measure, ${\displaystyle {\mathbb{P}}_{n}f}$ is the corresponding map, and

${\displaystyle \mathbb{P}f={\int }_{\mathcal{S}}f\mathrm{d}\mathbb{P},}$ assuming that it exists.

Definitions

• A class ${\displaystyle \mathcal{C}}$ is called a Glivenko–Cantelli class (or GC class, or sometimes strong GC class) with respect to a probability measure P if

${\displaystyle \Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{C}}\to 0}$ almost surely as ${\displaystyle n\to \mathrm{\infty }.}$

• A class ${\displaystyle \mathcal{C}}$ is a weak Glivenko-Cantelli class with respect to P if it instead satisfies the weaker condition

${\displaystyle \Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{C}}\to 0}$ in probability as ${\displaystyle n\to \mathrm{\infty }.}$

• A class is called a universal Glivenko–Cantelli class if it is a GC class with respect to any probability measure ${\displaystyle \mathbb{P}}$ on ${\displaystyle (\mathcal{S},A)}$.

• A class is a weak uniform Glivenko–Cantelli class if the convergence occurs uniformly over all probability measures ${\displaystyle \mathbb{P}}$ on ${\displaystyle (\mathcal{S},A)}$: For every ${\displaystyle \epsilon >0}$,

${\displaystyle \underset{\mathbb{P}\in \mathbb{P}(\mathcal{S},A)}{sup}Pr\left(\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{C}}>\epsilon \right)\to 0}$ as ${\displaystyle n\to \mathrm{\infty }.}$

• A class is a (strong) uniform Glivenko-Cantelli class if it satisfies the stronger condition that for every ${\displaystyle \epsilon >0}$,

${\displaystyle \underset{\mathbb{P}\in \mathbb{P}(\mathcal{S},A)}{sup}Pr\left(\underset{m\ge n}{sup}\Vert {\mathbb{P}}_m-\mathbb{P}{\Vert }_{\mathcal{C}}>\epsilon \right)\to 0}$ as ${\displaystyle n\to \mathrm{\infty }.}$

Glivenko–Cantelli classes of functions (as well as their uniform and universal forms) are defined similarly, replacing all instances of ${\displaystyle \mathcal{C}}$ with ${\displaystyle \mathcal{F}}$.

The weak and strong versions of the various Glivenko-Cantelli properties often coincide under certain regularity conditions. The following definition commonly appears in such regularity conditions:

• A class of functions ${\displaystyle \mathcal{F}}$ is image-admissible Suslin if there exists a Suslin space ${\displaystyle \mathrm{\Omega }}$ and a surjection ${\displaystyle T:\mathrm{\Omega }\to \mathcal{F}}$ such that the map ${\displaystyle (x,y)\mapsto [T(y)](x)}$ is measurable ${\displaystyle \mathcal{X}\times \mathrm{\Omega }}$.

• A class of measurable sets ${\displaystyle \mathcal{C}}$ is image-admissible Suslin if the class of functions ${\displaystyle \{{\mathbf{1}}_C\mid C\in \mathcal{C}\}}$ is image-admissible Suslin, where ${\displaystyle {\mathbf{1}}_C}$ denotes the indicator function for the set ${\displaystyle C}$.

Theorems

The following two theorems give sufficient conditions for the weak and strong versions of the Glivenko-Cantelli property to be equivalent.

Theorem (Talagrand, 1987)

Let ${\displaystyle \mathcal{F}}$ be a class of functions that is integrable ${\displaystyle \mathbb{P}}$, and define ${\displaystyle {\mathcal{F}}_0=\{f-\mathbb{P}f\mid f\in \mathcal{F}\}}$. Then the following are equivalent:

• ${\displaystyle \mathcal{F}}$ is a weak Glivenko-Cantelli class and ${\displaystyle {\mathcal{F}}_0}$ is dominated by an integrable function
• ${\displaystyle \mathcal{F}}$ is a Glivenko-Cantelli class

Theorem (Dudley, Giné, and Zinn, 1991)

Suppose that a function class ${\displaystyle \mathcal{F}}$ is bounded. Also suppose that the set ${\displaystyle {\mathcal{F}}_0=\{f-inff\mid f\in \mathcal{F}\}}$ is image-admissible Suslin. Then ${\displaystyle \mathcal{F}}$ is a weak uniform Glivenko-Cantelli class if and only if it is a strong uniform Glivenko-Cantelli class.

The following theorem is central to statistical learning of binary classification tasks.

Theorem (Vapnik and Chervonenkis, 1968)

Under certain consistency conditions, a universally measurable class of sets ${\displaystyle \mathcal{C}}$ is a uniform Glivenko-Cantelli class if and only if it is a Vapnik–Chervonenkis class.

There exist a variety of consistency conditions for the equivalence of uniform Glivenko-Cantelli and Vapnik-Chervonenkis classes. In particular, either of the following conditions for a class ${\displaystyle \mathcal{C}}$ suffice:

• ${\displaystyle \mathcal{C}}$ is image-admissible Suslin.
• ${\displaystyle \mathcal{C}}$ is universally separable: There exists a countable subset ${\displaystyle {\mathcal{C}}_{\mathcal{0}}}$ of ${\displaystyle \mathcal{C}}$ such that each set ${\displaystyle C\in \mathcal{C}}$ can be written as the pointwise limit of sets in ${\displaystyle {\mathcal{C}}_0}$.

Examples

• Let ${\displaystyle S=\mathbb{R}}$ and ${\displaystyle \mathcal{C}=\{(-\mathrm{\infty },t]:t\in \mathbb{R}\}}$. The classical Glivenko–Cantelli theorem implies that this class is a universal GC class. Furthermore, by Kolmogorov's theorem,

${\displaystyle \underset{P\in \mathcal{P}(S,A)}{sup}\Vert P_n-P{\Vert }_{\mathcal{C}}\sim n^{-1/2}}$, that is ${\displaystyle \mathcal{C}}$ is uniformly Glivenko–Cantelli class.

• Let P be a nonatomic probability measure on S and ${\displaystyle \mathcal{C}}$ be a class of all finite subsets in S. Because ${\displaystyle A_n=\{X_1,\dots ,X_n\}\in \mathcal{C}}$, ${\displaystyle P(A_n)=0}$, ${\displaystyle P_n(A_n)=1}$, we have that ${\displaystyle \Vert P_n-P{\Vert }_{\mathcal{C}}=1}$ and so ${\displaystyle \mathcal{C}}$ is not a GC class with respect to P.