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)={\frac {1}{n}}\sum _{i=1}^{n}I_{[X_{i},\infty )}(x)={\frac {1}{n}}\ {\bigl |}\left\{\ i\ \mid X_{i}\leq x,\ 1\leq i\leq n\right\}{\bigr |}}$ 

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} }{\bigl |}F_{n}(x)-F(x){\bigr |}\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}]}$ .

${\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 \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}=\sup _{C\in {\mathcal {C}}}{\bigl |}\mathbb {P} _{n}(C)-\mathbb {P} (C){\bigr |}}$ 

${\displaystyle {\bigl \|}\mathbb {P} _{n}-\mathbb {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 \ \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 \ {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}\to 0\ }$  almost surely as ${\displaystyle \ n\to \infty ~.}$ 

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

${\displaystyle \ {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}\to 0\ }$  in probability as ${\displaystyle \ n\to \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 \varepsilon >0}$ ,

${\displaystyle \ \sup _{\mathbb {P} \in \mathbb {P} ({\mathcal {S}},A)}\Pr \left({\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}>\varepsilon \right)\to 0\ }$  as ${\displaystyle \ n\to \infty ~.}$ 

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

${\displaystyle \ \sup _{\mathbb {P} \in \mathbb {P} ({\mathcal {S}},A)}\Pr \left(\sup _{m\geq n}{\bigl \|}\mathbb {P} _{m}-\mathbb {P} {\bigr \|}_{\mathcal {C}}>\varepsilon \right)\to 0\ }$  as ${\displaystyle \ n\to \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 \Omega }$  and a surjection ${\displaystyle T:\Omega \rightarrow {\mathcal {F}}}$  such that the map ${\displaystyle (x,y)\mapsto [T(y)](x)}$  is measurable ${\displaystyle {\mathcal {X}}\times \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)^[6]

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)^[7]

Suppose that a function class ${\displaystyle {\mathcal {F}}}$  is bounded. Also suppose that the set ${\displaystyle {\mathcal {F}}_{0}=\{f-\inf f\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)^[8]

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:^[9]

• ${\displaystyle {\mathcal {C}}}$  is image-admissible Suslin.
• ${\displaystyle {\mathcal {C}}}$  is universally separable: There exists a countable subset ${\displaystyle {\mathcal {C_{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}}$ .

• 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.