Glivenko-Cantelli Theorem

Get Glivenko%E2%80%93Cantelli Theorem essential facts below. View Videos or join the Glivenko%E2%80%93Cantelli Theorem discussion. Add Glivenko%E2%80%93Cantelli Theorem to your Like2do.com topic list for future reference or share this resource on social media.

## Proof

## Empirical measures

## Glivenko-Cantelli class

## Examples

## See also

## References

## Further reading

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Glivenko%E2%80%93Cantelli Theorem

This article has multiple issues. Please help or discuss these issues on the talk page. (Learn how and when to remove these template messages)
(Learn how and when to remove this template message) |

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 are independent and identically-distributed random variables in with common cumulative distribution function . The *empirical distribution function* for is defined by

where is the indicator function of the set . For every (fixed) , is a sequence of random variables which converge to almost surely by the strong law of large numbers, that is, converges to pointwise. Glivenko and Cantelli strengthened this result by proving uniform convergence of to .

**Theorem**

- almost surely.
^{[3]}

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

**Remarks**

- If is a stationary ergodic process, then converges almost surely to . 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.
^{[6]}See asymptotic properties of the empirical distribution function for this and related results.

For simplicity, consider a case of continuous random variable . Fix such that for . Now for all there exists such that . Note that

Therefore, almost surely

Since by strong law of large numbers, we can guarantee that for any integer we can find such that for all

,

which is the definition of almost sure convergence.

One can generalize the *empirical distribution function* by replacing the set by an arbitrary set *C* from a class of sets to obtain an empirical measure indexed by sets

Where is the indicator function of each set .

Further generalization is the map induced by on measurable real-valued functions *f*, which is given by

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

Consider a set with a sigma algebra of Borel subsets *A* and a probability measure *P*. For a class of subsets,

and a class of functions

define random variables

where is the empirical measure, is the corresponding map, and

- , assuming that it exists.

**Definitions**

- A class is called a
*Glivenko-Cantelli class**GC class*) with respect to a probability measure*P*if any of the following equivalent statements is true.

- 1. almost surely as .
- 2. in probability as .
- 3. , as (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*):

**Theorem** (Vapnik and Chervonenkis, 1968)^{[7]}

*A class of sets is uniformly GC if and only if it is a Vapnik-Chervonenkis class.*

- Let and . The classical Glivenko-Cantelli theorem implies that this class is a universal GC class. Furthermore, by Kolmogorov's theorem,

- , that is is uniformly Glivenko-Cantelli class.

- Let
*P*be a nonatomic probability measure on*S*and be a class of all finite subsets in*S*. Because , , , we have that and so is*not*a GC class with respect to*P*.

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

**^**Howard G.Tucker (1959). "A Generalization of the Glivenko-Cantelli Theorem".*The Annals of Mathematical Statistics*.**30**: 828-830. doi:10.1214/aoms/1177706212.**^**van der Vaart, A. W. (1998).*Asymptotic Statistics*. Cambridge University Press. p. 279. ISBN 0-521-78450-6.**^**van der Vaart, A. W. (1998).*Asymptotic Statistics*. Cambridge University Press. p. 265. ISBN 0-521-78450-6.**^**Glivenko, V. (1933). Sulla determinazione empirica delle leggi di probabilità. Giorn. Ist. Ital. Attuari 4, 92-99.**^**Cantelli, F. P. (1933). Sulla determinazione empirica delle leggi di probabilità. Giorn. Ist. Ital. Attuari 4, 421-424.**^**van der Vaart, A. W. (1998).*Asymptotic Statistics*. Cambridge University Press. p. 268. ISBN 0-521-78450-6.**^**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.

- 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

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Top US Cities

United States

Like2do.com was developed using defaultLogic.com's knowledge management platform. It allows users to manage learning and research. Visit defaultLogic's other partner sites below: