en>Bender235: some copy-editing

2013-08-02T13:25:50Z

New page

{{Multiple issues|
{{Refimprove|date=November 2008}}
{{More footnotes|date=February 2010}}
}}

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 random variables|independent and identically distributed]] observations grows.<ref>{{Cite journal|author = Howard G.Tucker| year = 1959 | url = http://www.jstor.org/discover/10.2307/2237422?uid=3738256&uid=2&uid=4&sid=21102589085583 | title = A Generilisation of the Glivenko-Canttelli Theorem | journal = The Annals of Mathematical Statistics | volume = 30}}</ref> The uniform convergence of more general [[empirical measure]]s becomes an important property of the '''Glivenko–Cantelli classes''' of functions or sets.<ref>{{cite book |last=van der Vaart |first=A. W. |year=1998 |title=Asymptotic Statistics |location= |publisher=Cambridge University Press |isbn=0-521-78450-6 |page=279 }}</ref> The Glivenko–Cantelli classes arise in [[Vapnik–Chervonenkis theory]], with applications to [[machine learning]]. Applications can be found in [[econometrics]] making use of [[M-estimator]]s.

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

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

where <math>I_C</math> is the [[indicator function]] of the set <math>C</math>. For every (fixed) <math>x</math>, <math>F_n(x)</math> is a sequence of random variables which converge to <math>F(x)</math> [[almost surely]] by the strong [[law of large numbers]], that is, <math>F_n</math> converges to <math>F</math> [[pointwise convergence|pointwise]]. Glivenko and Cantelli strengthened this result by proving [[uniform convergence]] of <math>F_n</math> to <math>F</math>.

'''Theorem'''
:<math>\|F_n - F\|_\infty = \sup_{x\in \mathbb{R}} |F_n(x) - F(x)| {\longrightarrow} 0</math> almost surely.<ref>{{cite book |last=van der Vaart |first=A. W. |year=1998 |title=Asymptotic Statistics |location= |publisher=Cambridge University Press |isbn=0-521-78450-6 |page=265 }}</ref>

This theorem originates with [[Valery Ivanovich Glivenko|Valery Glivenko]],<ref>Glivenko, V. (1933). Sulla determinazione empirica della legge di probabilita.
Giorn. Ist. Ital. Attuari 4, 92-99.</ref> and [[Francesco Paolo Cantelli|Francesco Cantelli]],<ref>Cantelli, F. P. (1933). Sulla determinazione empirica delle leggi di probabilita.
Giorn. Ist. Ital. Attuari 4, 221-424.</ref> in 1933.

'''Remarks'''
*If <math>X_n</math> is a stationary [[ergodic process]], then <math>F_n(x)</math> converges almost surely to <math>F(x)=E(1_{X_1\le x})</math>. 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]].<ref>{{cite book |last=van der Vaart |first=A. W. |year=1998 |title=Asymptotic Statistics |location= |publisher=Cambridge University Press |isbn=0-521-78450-6 |page=268 }}</ref> See [[Empirical distribution function#Asymptotic properties|asymptotic properties of the Empirical distribution function]] for this and related results.

==Empirical measures==
One can generalize the ''empirical distribution function'' by replacing the set <math>(-\infty,x]</math> by an arbitrary set ''C'' from a class of sets <math>\mathcal{C}</math> to obtain an [[empirical measure]] indexed by sets <math>C \in \mathcal{C}.</math>

:<math>P_n(C)=\frac{1}{n}\sum_{i=1}^n I_C(X_i), C\in\mathcal{C}.</math>

Further generalization is the map induced by <math>P_n</math> on measurable real-valued functions ''f'', which is given by

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

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

==Glivenko–Cantelli class==
Consider a set <math>\mathcal{S}</math> with a sigma algebra of [[Borel set|Borel subsets]] ''A'' and a [[probability measure]] ''P''. For a class of subsets,

:<math>{\mathcal C}\subset\{C: C \mbox{ is measurable subset of }\mathcal{S}\}</math>

and a class of functions

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

define random variables

:<math>\|P_n-P\|_{\mathcal C}=\sup_{c\in {\mathcal C}} |P_n(C)-P(C)|</math>

:<math>\|P_n-P\|_{\mathcal F}=\sup_{f\in {\mathcal F}} |P_nf- P(f)|</math>

where <math>P_n(C)</math> is the empirical measure, <math>P_n f</math> is the corresponding map, and

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

'''Definitions'''
* A class <math>\mathcal C</math> 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. <math>\|P_n-P\|_\mathcal{C}\to 0</math> almost surely as <math>n\to\infty</math>.
::2. <math>\|P_n-P\|_\mathcal{C}\to 0</math> in probability as <math>n\to\infty</math>.
::3. <math>\mathbb{E}\|P_n-P\|_\mathcal{C}\to 0</math>, as <math>n\to\infty</math> (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 ''P'' on (''S'',''A'').
*A class is called ''uniformly Glivenko–Cantelli'' if the convergence occurs uniformly over all probability measures ''P'' on (''S'',''A''):
::<math>\sup_{P\in \mathcal{P}(S,A)} \mathbb E \|P_n-P\|_\mathcal{C}\to 0;</math>
::<math>\sup_{P\in \mathcal{P}(S,A)} \mathbb E \|P_n-P\|_\mathcal{F}\to 0.</math>

'''Theorem''' ([[Vapnik]] and [[Chervonenkis]], 1968)<ref>{{cite journal |last=Vapnik |first=V. N. |last2=Chervonenkis |first2=A. Ya |year=1971 |title=On uniform convergence of the frequencies of events to their probabilities |journal=Theor. Prob. Appl. |volume=16 |issue=2 |pages=264–280 |doi=10.1137/1116025 }}</ref>
: ''A class of sets <math>\mathcal{C}</math> is uniformly GC if and only if it is a [[Shattering (machine learning)#Vapnik–Chervonenkis_class|Vapnik–Chervonenkis class]]. ''

==Examples==
* Let <math>S=\mathbb R</math> and <math>{\mathcal C}=\{(-\infty,t]:t\in {\mathbb R}\}</math>. The classical Glivenko–Cantelli theorem implies that this class is a universal GC class. Furthermore, by [[Kolmogorov-Smirnov test|Kolmogorov's theorem]],
:<math>\sup_{P\in \mathcal{P}(S,A)}\|P_n-P\|_{\mathcal C} \sim n^{-1/2}</math>, that is <math>\mathcal{C}</math> is uniformly Glivenko–Cantelli class.

* Let ''P'' be a [[atom (measure theory)|nonatomic]] probability measure on ''S'' and <math>\mathcal{C}</math> be a class of all finite subsets in ''S''. Because <math>A_n=\{X_1,\ldots,X_n\}\in \mathcal{C}</math>, <math>P(A_n)=0</math>, <math>P_n(A_n)=1</math>, we have that <math>\|P_n-P\|_{\mathcal C}=1</math> and so <math>\mathcal{C}</math> is ''not'' a GC class with respect to ''P''.

==See also==
* [[Donsker's theorem]]
* [[Dvoretzky–Kiefer–Wolfowitz inequality]] – strengthens Glivenko–Cantelli theorem by quantifying the rate of convergence.

==Notes==

{{Empty section|date=October 2013}}

==References==
{{reflist}}

==Further reading==
* [[Richard M. Dudley|Dudley, R. M.]] (1999). ''Uniform Central Limit Theorems'', Cambridge University Press. ISBN 0-521-46102-2.
* Shorack, G.R., Wellner J.A. (1986) ''Empirical Processes with Applications to Statistics'', Wiley. ISBN 0-471-86725-X.
* van der Vaart, A.W. and Wellner, J.A. (1996) ''Weak Convergence and Empirical Processes'', Springer. ISBN 0-387-94640-3.
*Aad W. van der Vaart, Jon A. Wellner (1996) Glivenko-Cantelli Theorems, Springer.
*Aad W. van der Vaart, Jon A. Wellner (2000) Preservation Theorems for Glivenko-Cantelli and Uniform Glivenko-Cantelli Classes, Springer

{{DEFAULTSORT:Glivenko-Cantelli Theorem}}
[[Category:Empirical process]]
[[Category:Asymptotic statistical theory]]
[[Category:Probability theorems]]
[[Category:Statistical theorems]]

Monetary policy reaction function - Revision history

en>Bender235: some copy-editing