Glivenko–Cantelli theorem explained

In the theory of probability, the Glivenko–Cantelli theorem (sometimes referred to as the Fundamental Theorem of Statistics), named after Valery Ivanovich Glivenko and Francesco Paolo Cantelli, describes the asymptotic behaviour of the empirical distribution function as the number of independent and identically distributed observations grows.^[1] Specifically, the empirical distribution function converges uniformly to the true distribution function almost surely.

The uniform convergence of more general empirical measures becomes an important property of the Glivenko–Cantelli classes of functions or sets.^[2] The Glivenko–Cantelli classes arise in Vapnik–Chervonenkis theory, with applications to machine learning. Applications can be found in econometrics making use of M-estimators.

Statement

Assume that

X _{1,X} _{2,...} are independent and identically distributed random variables in R with common cumulative distribution function F(x) . The empirical distribution function for X _{1,...,X} _{n} is defined byF _{n(x) = (1)/(n)} \sum ^{n} _{i =1} I _{[X _{i,} inf ty)} (x) = (1)/(n) l |\left\{ i \mid X _{i} \leq x, 1 \leq i \leq n \right\} r |

where

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

Theorem

\|F _{n} - F\| _{infty} = \sup _{x} l |F _{n(x)} - F(x) r | \longrightarrow 0 almost surely.^[3]

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

Remarks:

• If

X _{n} is a stationary ergodic process, then F _{n(x)} converges almost surely to F(x) = \operatorname E l [ 1 _{X _{1} \le x} r ] ~. 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] See asymptotic properties of the empirical distribution function for this and related results.

Proof

For simplicity, consider a case of continuous random variable

X . Fix -inf ty = x _{0<x} _{1< …} <x _{m-1} <x _{m=infty} such that F(x _{j)-F(x} _{j-1} ) = (1)/(m) for j =1 , ... ,m . Now for all x \in R there exists j \in \{ 1 , ... ,m\} such that x \in [x _{j-1} ,x _{j]} . \begin{align} F _{n(x)-F(x)} &\leq F _{n(x} _{j)-F(x} _{j-1} ) = F _{n(x} _{j)-F(x} ^{j) + (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} ) - (1 m. \end{align})/()

Therefore,

\|F _{n-F\|} _{infty} = \sup _{x\in} |F _{n(x)-F(x)|} \leq max _{j\in\{1,...,m\} } |F_n(x_j)-F(x_j)| + \frac1m.

Since $\backslash max\_\; |F\_n(x\_j)-F(x\_j)|\; \backslash to\; 0\; \backslash text$ by strong law of large numbers, we can guarantee that for any positive $\backslash varepsilon$ and any integer $m$ such that , we can find $N$ such that for all

n \geq N , we have $\backslash max\_\; |F\_n(x\_j)-F(x\_j)|\backslash leq\; \backslash varepsilon-1/m\; \backslash text$. Combined with the above result, this further implies that $\backslash |F\_n-F\backslash |\_\backslash infty\; \backslash leq\; \backslash varepsilon\; \backslash text$, which is the definition of almost sure convergence.

Empirical measures

One can generalize the empirical distribution function by replacing the set

( -inf ty,x] by an arbitrary set C from a class of sets l{C} to obtain an empirical measure indexed by sets C \in l{C}. P _{n(C) = (1)/(n)} \sum ^{n} _{i =1} I _{C(X} _{i),} C\in l{C} Where I _{C(x)} is the indicator function of each set C .

Further generalization is the map induced by

P _{n} on measurable real-valued functions f, which is given byf\mapsto P _{nf=\int} _{Sf} dP _{n} = (1)/(n) \sum ^{n} _{i =1} f(X _{i),} f\in l{F}.

Then it becomes an important property of these classes whether the strong law of large numbers holds uniformly on

l{F} or l{C} .

Glivenko–Cantelli class

Consider a set

l{S} with a sigma algebra of Borel subsets and a probability measure P ~. For a class of subsets,l{C} \subset l \{ C: C ismeasurablesubsetof l{S} r \}

and a class of functions

l{F} \subset l \{ f: l{S}\to R , f ismeasurable r \}

define random variables

l \| P _{n} - P r \| _{lC} = \sup _{C} } \bigl| \mathbb_n(C) - \mathbb(C) \bigr| l \| P _{n} - P r \| _{lF} = \sup _{f} } \bigl| \mathbb_n f - \mathbb f \bigr|

where

P _{n(C)} is the empirical measure, P _{n} f is the corresponding map, andP f = \int _{l{S}f} d P , assuming that it exists.

Definitions

• A class

l C is called a Glivenko–Cantelli class (or GC class, or sometimes strong GC class) with respect to a probability measure ifl \| P _{n} - P r \| _{l{C}\to} 0 almost surely as n \to inf ty ~.

• A class is

l C is a weak Glivenko-Cantelli class with respect to if it instead satisfies the weaker conditionl \| P _{n} - P r \| _{l{C}\to} 0 in probability as n \to inf ty ~.

• A class is called a universal Glivenko–Cantelli class if it is a GC class with respect to any probability measure

P on ( l{S}, A) .

• A class is a weak uniform Glivenko–Cantelli class if the convergence occurs uniformly over all probability measures

P on ( l{S}, A) : For every \varepsilon > 0 ,\sup _{P} ,A)} \Pr\left( l \| P _{n} - P r \| _{l{C}>} \varepsilon\right) \to 0 as n \to inf ty ~.

• A class is a (strong) uniform Glivenko-Cantelli class if it satisfies the stronger condition that for every

\varepsilon > 0 ,\sup _{P} ,A)} \Pr\left(\sup _{m} l \| P _{m} - P r \| _{l{C}>} \varepsilon\right) \to 0 as n \to inf ty ~.

Glivenko–Cantelli classes of functions (as well as their uniform and universal forms) are defined similarly, replacing all instances of

l{C} with l{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

l{F} is image-admissible Suslin if there exists a Suslin space \Omega and a surjection T:\Omega → l{F} such that the map (x, y) \mapsto [T(y)](x) is measurable l{X} x \Omega .

• A class of measurable sets

l{C} is image-admissible Suslin if the class of functions \{ 1 _{C} \mid C\in l{C}\} is image-admissible Suslin, where 1 _{C} denotes the indicator function for the set 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

l{F} be a class of functions that is integrable P , and define l{F} _{0} = \{f - P f \mid f\in l{F}\} . Then the following are equivalent:

l{F} is a weak Glivenko-Cantelli class and l{F} _{0} is dominated by an integrable function

l{F} is a Glivenko-Cantelli class

Theorem (Dudley, Giné, and Zinn, 1991)^[7]

Suppose that a function class

l{F} is bounded. Also suppose that the set l{F} _{0} = \{f - inf f \mid f\in l{F}\} is image-admissible Suslin. Then l{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

l{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

l{C} suffice:^[9] l{C} is image-admissible Suslin.l{C} is universally separable: There exists a countable subset l{C _{0}} of l{C} such that each set C\in l{C} can be written as the pointwise limit of sets in l{C} _{0} .

Examples

• Let

S = R and { l C} = \{( -inf ty,t]:t\in { R}\} . The classical Glivenko–Cantelli theorem implies that this class is a universal GC class. Furthermore, by Kolmogorov's theorem,\sup _{P\in} (S,A)}\|P _{n-P\|} _{lC} \sim n ^{-1/2} , that is l{C} is uniformly Glivenko–Cantelli class.

• Let P be a nonatomic probability measure on S and

l{C} be a class of all finite subsets in S. Because A _{n=\{X} _{1,\ldots,X} _{n\}\in} l{C} , P(A _{n)=0} , P _{n(A} _{n)=1} , we have that \|P _{n-P\|} _{lC} =1 and so l{C} is not a GC class with respect to P.

See also

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

Further reading

• Book: Dudley, R.M. . Richard M. Dudley . 1999 . Uniform Central Limit Theorems . Cambridge University Press . 0-521-46102-2 .
• Book: Pitman, E.J.G. . 1979 . Some Basic Theory for Statistical Inference . London, UK . Chapman and Hall . 0-470-26554-X . The Sample Distribution Function . 79–97 .
• Book: Shorack, G.R. . Galen Shorack . Jon A. Wellner . Wellner . J.A. . 1986 . Empirical Processes with Applications to Statistics . Wiley . 0-471-86725-X .
• Book: Aad van der Vaart . van der Vaart . A.W. . Wellner . J.A. . 1996 . Weak Convergence and Empirical Processes . Springer . 0-387-94640-3 .
• Book: Aad van der Vaart . Aad W. . van der Vaart . Jon A. . Wellner . 1996 . Glivenko-Cantelli Theorems . Springer .
• Book: Aad van der Vaart . Aad W. . van der Vaart . Jon A. . Wellner . 2000 . Preservation Theorems for Glivenko–Cantelli and Uniform Glivenko–Cantelli Classes . Springer .

Notes and References

1. Howard G.Tucker. 1959 . A Generalization of the Glivenko–Cantelli Theorem . The Annals of Mathematical Statistics . 30. 3 . 10.1214/aoms/1177706212 . 828–830. 2237422 . free .
2. Book: van der Vaart, A. W. . 1998 . Asymptotic Statistics . limited . Cambridge University Press . 978-0-521-78450-4 . 279 .
3. Book: van der Vaart, A.W. . 1998 . Asymptotic Statistics . Cambridge University Press . 978-0-521-78450-4 . limited.
4. Glivenko, V. . 1933 . Sulla determinazione empirica delle leggi di probabilità . it . Giorn. Ist. Ital. Attuari . 4 . 92-99.
5. Cantelli, F.P. . Francesco Paolo Cantelli . 1933 . Sulla determinazione empirica delle leggi di probabilità . Giorn. Ist. Ital. Attuari . 4 . 421-424.
6. Talagrand . M. . Michel Talagrand . 1987 . The Glivenko-Cantelli Problem . Annals of Probability . 15 . 837-870 . 10.1214/AOP/1176992069.
7. Dudley . Richard M. . Richard M. Dudley . Giné . Eva . Zinn . Joel C. . 1991 . Uniform and universal Glivenko-Cantelli classes . Journal of Theoretical Probability . 4 . 485-510 . 10.1007/BF01210321.
8. Vapnik . V.N. . Vladimir Vapnik . Chervonenkis . A.Ya. . Alexey Chervonenkis . 1971 . On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability & Its Applications. 16 . 2 . 264–280 . 10.1137/1116025 .
9. Pestov . Vladimir . PAC learnability versus VC dimension: A footnote to a basic result of statistical learning . The 2011 International Joint Conference on Neural Networks . 1141-1145 . 2011 . 10.1109/IJCNN.2011.6033352. 1104.2097 .