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. 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. 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 are independent and identically distributed random variables in \mathbb{R} with common cumulative distribution function F(x). The empirical distribution function for is defined by 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 This theorem originates with Valery Glivenko and Francesco Cantelli, in 1933.

Proof

For simplicity, consider a case of continuous random variable X. Fix such that for j=1,\dots,m. Now for all there exists such that. Therefore, Since by strong law of large numbers, we can guarantee that for any positive \varepsilon and any integer m such that, we can find N such that for all n \geq N, we have. Combined with the above result, this further implies that, which is the definition of almost sure convergence.

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 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 Then it becomes an important property of these classes whether the strong law of large numbers holds uniformly on \mathcal{F} or \mathcal{C}.

Glivenko–Cantelli class

Consider a set with a sigma algebra of Borel subsets A and a probability measure For a class of subsets, and a class of functions define random variables where is the empirical measure, is the corresponding map, and Definitions Glivenko–Cantelli classes of functions (as well as their uniform and universal forms) are defined similarly, replacing all instances of \mathcal{C} with \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: 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) Theorem (Dudley, Giné, and Zinn, 1991) The following theorem is central to statistical learning of binary classification tasks. Theorem (Vapnik and Chervonenkis, 1968) 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 \mathcal{C} suffice:

Examples