Glivenko–Cantelli theorem

Assume that ${\displaystyle X_{1},X_{2},\dots }$ are independent and identically distributed random variables in ${\displaystyle \mathbb {R} }$ with common cumulative distribution function ${\displaystyle F(x)}$. The empirical distribution function for ${\displaystyle X_{1},\dots ,X_{n}}$ is defined by

${\displaystyle F_{n}(x)={\tfrac {1}{n}}\sum _{i=1}^{n}I_{[X_{i},\infty )}(x)={\tfrac {1}{n}}\ {\biggl |}\left\{\ i\ \mid X_{i}\leq x,\ 1\leq i\leq n\right\}{\biggr |}}$

where ${\displaystyle I_{C}}$ is the indicator function of the set ${\displaystyle \ C~.}$ For every (fixed) ${\displaystyle \ x\ ,}$ ${\displaystyle \ F_{n}(x)\ }$ is a sequence of random variables which converge to ${\displaystyle F(x)}$ almost surely by the strong law of large numbers. Glivenko and Cantelli strengthened this result by proving uniform convergence of ${\displaystyle \ F_{n}\ }$ to ${\displaystyle \ F~.}$

Theorem

${\displaystyle \|F_{n}-F\|_{\infty }=\sup _{x\in \mathbb {R} }{\biggl |}F_{n}(x)-F(x){\biggr |}\longrightarrow 0}$ almost surely.[3]^(p 265)

This theorem originates with Valery Glivenko[4] and Francesco Cantelli,[5] in 1933.

Remarks

• If ${\displaystyle \ X_{n}\ }$ is a stationary ergodic process, then ${\displaystyle F_{n}(x)}$ converges almost surely to ${\displaystyle \ F(x)=\operatorname {\mathbb {E} } {\bigl [}1_{X_{1}\leq x}{\bigr ]}~.}$ The Glivenko–Cantelli theorem gives a stronger mode of convergence than this in the iid case.
• An even stronger uniform convergence result for the empirical distribution function is available in the form of an extended type of law of the iterated logarithm.[3]^(p 268) See asymptotic properties of the empirical distribution function for this and related results.

For simplicity, consider a case of continuous random variable ${\displaystyle X}$. Fix ${\displaystyle -\infty =x_{0}<x_{1}<\cdots <x_{m-1}<x_{m}=\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}]}$. Note that

${\displaystyle {\begin{aligned}F_{n}(x)-F(x)&\leq F_{n}(x_{j})-F(x_{j-1})=F_{n}(x_{j})-F(x_{j})+{\frac {1}{m}},\\F_{n}(x)-F(x)&\geq F_{n}(x_{j-1})-F(x_{j})=F_{n}(x_{j-1})-F(x_{j-1})-{\frac {1}{m}}.\end{aligned}}}$

Therefore,

${\displaystyle \|F_{n}-F\|_{\infty }=\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|\leq \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|+{\frac {1}{m}}.}$

Since ${\textstyle \max _{j\in \{1,\dots ,m\}}|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 ${\textstyle \varepsilon }$ and any integer ${\textstyle m}$ such that ${\textstyle 1/m<\varepsilon }$, we can find ${\textstyle N}$ such that for all ${\displaystyle n\geq N}$, we have ${\textstyle \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|\leq \varepsilon -1/m{\text{ a.s.}}}$. Combined with the above result, this further implies that ${\textstyle \|F_{n}-F\|_{\infty }\leq \varepsilon {\text{ a.s.}}}$, which is the definition of almost sure convergence.

One can generalize the empirical distribution function by replacing the set ${\displaystyle (-\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}f\,dP_{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}}}$.

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 {\Bigl \{}C:C{\text{ is measurable subset of }}{\mathcal {S}}{\Bigr \}}}$

and a class of functions

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

define random variables

${\displaystyle {\Bigl \|}P_{n}-P{\Bigr \|}_{\mathcal {C}}=\sup _{C\in {\mathcal {C}}}{\Bigl |}\mathbb {P} _{n}(C)-\mathbb {P} (C){\Bigr |}}$

${\displaystyle {\Bigl \|}P_{n}-P{\Bigr \|}_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}{\Bigl |}\mathbb {P} _{n}f-\mathbb {P} f{\Bigr |}}$

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

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

Definitions

• A class ${\displaystyle \ {\mathcal {C}}\ }$ is called a Glivenko–Cantelli class (or GC class) with respect to a probability measure P if any of the following equivalent statements is true.

1. ${\displaystyle \ {\Bigl \|}\mathbb {P} _{n}-\mathbb {P} {\Bigr \|}_{\mathcal {C}}\to 0\ }$ almost surely as ${\displaystyle \ n\to \infty ~.}$

2. ${\displaystyle \ {\Bigl \|}\mathbb {P} _{n}-\mathbb {P} {\Bigr \|}_{\mathcal {C}}\to 0\ }$ in probability as ${\displaystyle \ n\to \infty ~.}$

3. ${\displaystyle \ \operatorname {\mathbb {E} } {\Bigl \|}\mathbb {P} _{n}-\mathbb {P} {\Bigr \|}_{\mathcal {C}}\to 0\ ,}$ as ${\displaystyle \ n\to \infty \ }$ (convergence in mean).

The Glivenko–Cantelli classes of functions are defined similarly.

• 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 (S,A) .
• A class is called uniformly Glivenko–Cantelli if the convergence occurs uniformly over all probability measures ${\displaystyle \mathbb {P} }$ on (S,A) :

${\displaystyle \sup _{\mathbb {P} \in \mathbb {P} (S,A)}\operatorname {\mathbb {E} } {\Bigl \|}\mathbb {P} _{n}-\mathbb {P} {\Bigr \|}_{\mathcal {C}}\to 0\$ ;}

${\displaystyle \sup _{\mathbb {P} \in \mathbb {P} (S,A)}\operatorname {\mathbb {E} } {\Bigl \|}\mathbb {P} _{n}-\mathbb {P} {\Bigr \|}_{\mathcal {F}}\to 0~.}$

Theorem (Vapnik and Chervonenkis, 1968)[6]

A class of sets ${\displaystyle \ {\mathcal {C}}\ }$ is uniformly GC if and only if it is a Vapnik–Chervonenkis class.

• Let ${\displaystyle S=\mathbb {R} }$ and ${\displaystyle {\mathcal {C}}=\{(-\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 \sup _{P\in {\mathcal {P}}(S,A)}\|P_{n}-P\|_{\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},\ldots ,X_{n}\}\in {\mathcal {C}}}$, ${\displaystyle P(A_{n})=0}$, ${\displaystyle P_{n}(A_{n})=1}$, we have that ${\displaystyle \|P_{n}-P\|_{\mathcal {C}}=1}$ and so ${\displaystyle {\mathcal {C}}}$ is not a GC class with respect to P.

• Donsker's theorem
• Dvoretzky–Kiefer–Wolfowitz inequality – strengthens the Glivenko–Cantelli theorem by quantifying the rate of convergence.