Glivenko–Cantelli theorem

In the theory of probability, the Glivenko–Cantelli theorem, named after Valery Ivanovich Glivenko and Francesco Paolo Cantelli, determines the asymptotic behaviour of the empirical distribution function as the number of independent and identically distributed observations grows.[1] 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.

Assume that X_1,X_2,\dots are independent and identically-distributed random variables in \mathbb{R} with common cumulative distribution function F(x). The empirical distribution function for X_1,\dots,X_n is defined by

F_n(x)=\frac{1}{n}\sum_{i=1}^n I_{(-\infty,x]}(X_i),

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, that is, F_n converges to F pointwise. Glivenko and Cantelli strengthened this result by proving uniform convergence of F_n to F.

Theorem

\|F_n - F\|_\infty = \sup_{x\in \mathbb{R}} |F_n(x) - F(x)| {\longrightarrow} 0 almost surely.[3]

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

Remarks

Empirical measures

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

P_n(C)=\frac{1}{n}\sum_{i=1}^n I_C(X_i),   C\in\mathcal{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 by

f\mapsto P_nf=\int_SfdP_n=\frac{1}{n}\sum_{i=1}^n f(X_i), f\in\mathcal{F}.

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

Glivenko–Cantelli class

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

{\mathcal C}\subset\{C:  C \mbox{ is measurable subset of }\mathcal{S}\}

and a class of functions

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

define random variables

\|P_n-P\|_{\mathcal C}=\sup_{c\in {\mathcal C}} |P_n(C)-P(C)|
\|P_n-P\|_{\mathcal F}=\sup_{f\in {\mathcal F}} |P_nf- P(f)|

where P_n(C) is the empirical measure, P_n f is the corresponding map, and

\mathbb{E}f=\int_\mathcal{S} fdP = P (f) , assuming that it exists.

Definitions

1. \|P_n-P\|_\mathcal{C}\to 0 almost surely as n\to\infty.
2. \|P_n-P\|_\mathcal{C}\to 0 in probability as n\to\infty.
3. \mathbb{E}\|P_n-P\|_\mathcal{C}\to 0, as n\to\infty (convergence in mean).
The Glivenko–Cantelli classes of functions are defined similarly.
\sup_{P\in \mathcal{P}(S,A)} \mathbb E \|P_n-P\|_\mathcal{C}\to 0;
\sup_{P\in \mathcal{P}(S,A)} \mathbb E \|P_n-P\|_\mathcal{F}\to 0.

Theorem (Vapnik and Chervonenkis, 1968)[7]

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

Examples

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

See also

References

  1. Howard G.Tucker (1959). "A Generalization of the Glivenko-Cantelli Theorem". The Annals of Mathematical Statistics 30.
  2. van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press. p. 279. ISBN 0-521-78450-6.
  3. van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press. p. 265. ISBN 0-521-78450-6.
  4. Glivenko, V. (1933). Sulla determinazione empirica della legge di probabilita. Giorn. Ist. Ital. Attuari 4, 92-99.
  5. Cantelli, F. P. (1933). Sulla determinazione empirica delle leggi di probabilita. Giorn. Ist. Ital. Attuari 4, 221-424.
  6. van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press. p. 268. ISBN 0-521-78450-6.
  7. Vapnik, V. N.; Chervonenkis, A. Ya (1971). "On uniform convergence of the frequencies of events to their probabilities". Theor. Prob. Appl. 16 (2): 264–280. doi:10.1137/1116025.

Further reading