Teorema de Glivenko-Cantelli

Teoría de la probabilidad

El diagrama de la izquierda ilustra el teorema de Glivenko-Cantelli para distribuciones uniformes. El diagrama de la derecha ilustra el teorema de Donsker-Skorokhod-Kolmogorov.

El mismo diagrama para distribuciones normales

En la teoría de la probabilidad , el teorema de Glivenko-Cantelli (a veces denominado Teorema Fundamental de Estadística ), llamado así por Valery Ivanovich Glivenko y Francesco Paolo Cantelli , describe el comportamiento asintótico de la función de distribución empírica a medida que crece el número de observaciones independientes e idénticamente distribuidas . ^[1] Específicamente, la función de distribución empírica converge de manera uniforme a la función de distribución verdadera casi con seguridad .

La convergencia uniforme de medidas empíricas más generales se convierte en una propiedad importante de las clases de funciones o conjuntos de Glivenko-Cantelli . ^[2] Las clases de Glivenko-Cantelli surgen en la teoría de Vapnik-Chervonenkis , con aplicaciones en el aprendizaje automático . Se pueden encontrar aplicaciones en econometría haciendo uso de estimadores M.

Declaración

Supongamos que son variables aleatorias independientes e idénticamente distribuidas en con una función de distribución acumulativa común . La función de distribución empírica para se define por ${\displaystyle X_{1},X_{2},\dots }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle F(x)}$ ${\displaystyle X_{1},\dots ,X_{n}}$

${\displaystyle F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}I_{[X_{i},\infty )}(x)={\frac {1}{n}}\ {\bigl |}\left\{\ i\ \mid X_{i}\leq x,\ 1\leq i\leq n\right\}{\bigr |}}$

donde es la función indicadora del conjunto Para cada (fijo) es una secuencia de variables aleatorias que convergen a casi con seguridad por la ley fuerte de los grandes números . Glivenko y Cantelli reforzaron este resultado al demostrar la convergencia uniforme de a ${\displaystyle I_{C}}$ ${\displaystyle \ C~.}$ ${\displaystyle \ x\ ,}$ ${\displaystyle \ F_{n}(x)\ }$ ${\displaystyle F(x)}$ ${\displaystyle \ F_{n}\ }$ ${\displaystyle \ F~.}$

Teorema

${\displaystyle \|F_{n}-F\|_{\infty }=\sup _{x\in \mathbb {R} }{\bigl |}F_{n}(x)-F(x){\bigr |}\longrightarrow 0}$casi con toda seguridad. ^{[3] (p 265)}

Este teorema se origina con Valery Glivenko ^[4] y Francesco Cantelli [ ^5] en 1933.

Observaciones

• Si es un proceso ergódico estacionario , entonces converge casi con seguridad a El teorema de Glivenko-Cantelli proporciona un modo de convergencia más fuerte que este en el caso iid . ${\displaystyle \ X_{n}\ }$ ${\displaystyle F_{n}(x)}$ ${\displaystyle \ F(x)=\operatorname {\mathbb {E} } {\bigl [}1_{X_{1}\leq x}{\bigr ]}~.}$
• Un resultado de convergencia uniforme aún más fuerte para la función de distribución empírica está disponible en la forma de un tipo extendido de ley del logaritmo iterado . ^{[3] (p 268)} Véanse las propiedades asintóticas de la función de distribución empírica para este y otros resultados relacionados.

Prueba

Para simplificar, considere un caso de variable aleatoria continua . Fije de modo que para . Ahora, para todos existe tal que . ${\displaystyle X}$ ${\displaystyle -\infty =x_{0}<x_{1}<\cdots <x_{m-1}<x_{m}=\infty }$ ${\displaystyle F(x_{j})-F(x_{j-1})={\frac {1}{m}}}$ ${\displaystyle j=1,\dots ,m}$ ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle j\in \{1,\dots ,m\}}$ ${\displaystyle x\in [x_{j-1},x_{j}]}$

${\displaystyle {\begin{aligned}F_{n}(x)-F(x)&\leq F_{n}(x_{j})-F(x_{j-1})=F_{n}(x_{j})-F(x_{j})+{\frac {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})-{\frac {1}{m}}.\end{aligned}}}$

Por lo tanto,

${\displaystyle \|F_{n}-F\|_{\infty }=\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|\leq \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|+{\frac {1}{m}}.}$

Dado que, por la ley fuerte de los grandes números, podemos garantizar que para cualquier número entero positivo y cualquier número entero tal que , podemos encontrar tal que para todo , tenemos . Combinado con el resultado anterior, esto implica además que , que es la definición de convergencia casi segura. ${\textstyle \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|\to 0{\text{ a.s.}}}$ ${\textstyle \varepsilon }$ ${\textstyle m}$ ${\textstyle 1/m<\varepsilon }$ ${\textstyle N}$ ${\displaystyle n\geq N}$ ${\textstyle \max _{j\in \{1,\dots ,m\}}|F_{n}(x_{j})-F(x_{j})|\leq \varepsilon -1/m{\text{ a.s.}}}$ ${\textstyle \|F_{n}-F\|_{\infty }\leq \varepsilon {\text{ a.s.}}}$

Medidas empíricas

Se puede generalizar la función de distribución empírica reemplazando el conjunto por un conjunto arbitrario C de una clase de conjuntos para obtener una medida empírica indexada por conjuntos. ${\displaystyle (-\infty ,x]}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C\in {\mathcal {C}}.}$

${\displaystyle P_{n}(C)={\frac {1}{n}}\sum _{i=1}^{n}I_{C}(X_{i}),C\in {\mathcal {C}}}$

¿Dónde está la función indicadora de cada conjunto ? ${\displaystyle I_{C}(x)}$ ${\displaystyle C}$

Una generalización adicional es el mapa inducido por sobre funciones reales mensurables f , que se da por ${\displaystyle P_{n}}$

${\displaystyle f\mapsto P_{n}f=\int _{S}f\,dP_{n}={\frac {1}{n}}\sum _{i=1}^{n}f(X_{i}),f\in {\mathcal {F}}.}$

Entonces se convierte en una propiedad importante de estas clases si la ley fuerte de los grandes números se cumple uniformemente en o . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {C}}}$

Clase Glivenko-Cantelli

Consideremos un conjunto con un álgebra sigma de subconjuntos de Borel A y una medida de probabilidad para una clase de subconjuntos, ${\displaystyle \ {\mathcal {S}}\ }$ ${\displaystyle \ \mathbb {P} ~.}$

${\displaystyle {\mathcal {C}}\subset {\bigl \{}C:C{\text{ is measurable subset of }}{\mathcal {S}}{\bigr \}}}$

y una clase de funciones

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

definir variables aleatorias

${\displaystyle {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}=\sup _{C\in {\mathcal {C}}}{\bigl |}\mathbb {P} _{n}(C)-\mathbb {P} (C){\bigr |}}$

${\displaystyle {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}{\bigl |}\mathbb {P} _{n}f-\mathbb {P} f{\bigr |}}$

donde es la medida empírica, es el mapa correspondiente, y ${\displaystyle \ \mathbb {P} _{n}(C)\ }$ ${\displaystyle \ \mathbb {P} _{n}f\ }$

${\displaystyle \ \mathbb {P} f=\int _{\mathcal {S}}f\ \mathrm {d} \mathbb {P} \ ,}$suponiendo que exista.

Definiciones

• Una clase se denomina clase Glivenko-Cantelli (o clase GC , o a veces clase GC fuerte ) con respecto a una medida de probabilidad P si ${\displaystyle \ {\mathcal {C}}\ }$

${\displaystyle \ {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}\to 0\ }$casi seguro como ${\displaystyle \ n\to \infty ~.}$

• Una clase es una clase Glivenko-Cantelli débil con respecto a P si, en cambio, satisface la condición más débil ${\displaystyle \ {\mathcal {C}}\ }$

${\displaystyle \ {\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}\to 0\ }$en probabilidad como ${\displaystyle \ n\to \infty ~.}$

• Una clase se denomina clase universal Glivenko-Cantelli si es una clase GC con respecto a cualquier medida de probabilidad en . ${\displaystyle \mathbb {P} }$ ${\displaystyle ({\mathcal {S}},A)}$

• Una clase es una clase Glivenko-Cantelli uniforme débil si la convergencia ocurre uniformemente sobre todas las medidas de probabilidad en : Para cada , ${\displaystyle \mathbb {P} }$ ${\displaystyle ({\mathcal {S}},A)}$ ${\displaystyle \varepsilon >0}$

${\displaystyle \ \sup _{\mathbb {P} \in \mathbb {P} ({\mathcal {S}},A)}\Pr \left({\bigl \|}\mathbb {P} _{n}-\mathbb {P} {\bigr \|}_{\mathcal {C}}>\varepsilon \right)\to 0\ }$como ${\displaystyle \ n\to \infty ~.}$

• Una clase es una clase Glivenko-Cantelli uniforme (fuerte) si satisface la condición más fuerte de que para cada , ${\displaystyle \varepsilon >0}$

${\displaystyle \ \sup _{\mathbb {P} \in \mathbb {P} ({\mathcal {S}},A)}\Pr \left(\sup _{m\geq n}{\bigl \|}\mathbb {P} _{m}-\mathbb {P} {\bigr \|}_{\mathcal {C}}>\varepsilon \right)\to 0\ }$como ${\displaystyle \ n\to \infty ~.}$

Las clases de funciones de Glivenko-Cantelli (así como sus formas uniformes y universales) se definen de manera similar, reemplazando todas las instancias de con . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {F}}}$

Las versiones débiles y fuertes de las diversas propiedades de Glivenko-Cantelli suelen coincidir en determinadas condiciones de regularidad. La siguiente definición suele aparecer en tales condiciones de regularidad:

• Una clase de funciones es Suslin admisible en imágenes si existe un espacio de Suslin y una sobreyección tales que la función es medible . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \Omega }$ ${\displaystyle T:\Omega \rightarrow {\mathcal {F}}}$ ${\displaystyle (x,y)\mapsto [T(y)](x)}$ ${\displaystyle {\mathcal {X}}\times \Omega }$

• Una clase de conjuntos mensurables es Suslin admisible en imágenes si la clase de funciones es Suslin admisible en imágenes, donde denota la función indicadora para el conjunto . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \{\mathbf {1} _{C}\mid C\in {\mathcal {C}}\}}$ ${\displaystyle \mathbf {1} _{C}}$ ${\displaystyle C}$

Teoremas

Los dos teoremas siguientes proporcionan condiciones suficientes para que las versiones débil y fuerte de la propiedad de Glivenko-Cantelli sean equivalentes.

Teorema ( Talagrand , 1987) ^[6]

Sea una clase de funciones integrables y defina . Entonces las siguientes son equivalentes: ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \mathbb {P} }$ ${\displaystyle {\mathcal {F}}_{0}=\{f-\mathbb {P} f\mid f\in {\mathcal {F}}\}}$

• ${\displaystyle {\mathcal {F}}}$es una clase débil de Glivenko-Cantelli y está dominada por una función integrable ${\displaystyle {\mathcal {F}}_{0}}$
• ${\displaystyle {\mathcal {F}}}$es una clase de Glivenko-Cantelli

Teorema ( Dudley , Giné y Zinn, 1991) ^[7]

Supongamos que una clase de función está acotada. Supongamos también que el conjunto es Suslin admisible en imágenes. Entonces es una clase Glivenko-Cantelli uniforme débil si y solo si es una clase Glivenko-Cantelli uniforme fuerte. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}_{0}=\{f-\inf f\mid f\in {\mathcal {F}}\}}$ ${\displaystyle {\mathcal {F}}}$

El siguiente teorema es fundamental para el aprendizaje estadístico de las tareas de clasificación binaria.

Teorema ( Vapnik y Chervonenkis , 1968) ^[8]

Bajo ciertas condiciones de consistencia, una clase universalmente medible de conjuntos es una clase Glivenko-Cantelli uniforme si y sólo si es una clase Vapnik-Chervonenkis . ${\displaystyle \ {\mathcal {C}}\ }$

Existen diversas condiciones de consistencia para la equivalencia de clases uniformes de Glivenko-Cantelli y Vapnik-Chervonenkis. En particular, cualquiera de las siguientes condiciones para una clase es suficiente: ^[9] ${\displaystyle {\mathcal {C}}}$

• ${\displaystyle {\mathcal {C}}}$Es una imagen admisible de Suslin.
• ${\displaystyle {\mathcal {C}}}$es universalmente separable : existe un subconjunto contable de tal que cada conjunto puede escribirse como el límite puntual de conjuntos en . ${\displaystyle {\mathcal {C_{0}}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}_{0}}$

Ejemplos

• Sea y . El teorema clásico de Glivenko-Cantelli implica que esta clase es una clase GC universal. Además, por el teorema de Kolmogorov , ${\displaystyle S=\mathbb {R} }$ ${\displaystyle {\mathcal {C}}=\{(-\infty ,t]:t\in {\mathbb {R} }\}}$

${\displaystyle \sup _{P\in {\mathcal {P}}(S,A)}\|P_{n}-P\|_{\mathcal {C}}\sim n^{-1/2}}$, es decir, es de clase uniforme Glivenko-Cantelli. ${\displaystyle {\mathcal {C}}}$

• Sea P una medida de probabilidad no atómica en S y una clase de todos los subconjuntos finitos en S . Como , , , tenemos que y por lo tanto no es una clase GC con respecto a P . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A_{n}=\{X_{1},\ldots ,X_{n}\}\in {\mathcal {C}}}$ ${\displaystyle P(A_{n})=0}$ ${\displaystyle P_{n}(A_{n})=1}$ ${\displaystyle \|P_{n}-P\|_{\mathcal {C}}=1}$ ${\displaystyle {\mathcal {C}}}$

Véase también

• Teorema de Donsker
• Desigualdad de Dvoretzky-Kiefer-Wolfowitz : fortalece el teorema de Glivenko-Cantelli al cuantificar la tasa de convergencia.

Referencias

1. Howard G. Tucker (1959). "Una generalización del teorema de Glivenko-Cantelli". Anales de estadística matemática . 30 (3): 828–830. doi : 10.1214/aoms/1177706212 . JSTOR  2237422.
2. van der Vaart, AW (1998). Estadísticas asintóticas . Prensa de la Universidad de Cambridge. pag. 279.ISBN​ 978-0-521-78450-4.
3. van der Vaart, AW (1998). Estadísticas asintóticas . Prensa de la Universidad de Cambridge. ISBN 978-0-521-78450-4.
4. Glivenko, V. (1933). "Sulla determinazione empirica delle leggi di probabilità". Giorn. Ist. Italiano. Attuari (en italiano). 4 : 92–99.
5. Cantelli, FP (1933). "Sulla determinazione empirica delle leggi di probabilità". Giorn. Ist. Italiano. Attuari . 4 : 421–424.
6. Talagrand, M. (1987). "El problema de Glivenko-Cantelli". Anales de probabilidad . 15 : 837–870. doi :10.1214/AOP/1176992069.
7. Dudley, Richard M. ; Giné, Eva; Zinn, Joel C. (1991). "Clases de Glivenko-Cantelli uniformes y universales". Journal of Theoretical Probability . 4 : 485–510. doi :10.1007/BF01210321.
8. Vapnik, VN ; Chervonenkis, A.Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Teoría de la probabilidad y sus aplicaciones . 16 (2): 264–280. doi :10.1137/1116025.
9. Pestov, Vladimir (2011). "Capacidad de aprendizaje de PAC versus dimensión VC: una nota al pie de un resultado básico del aprendizaje estadístico". Conferencia conjunta internacional de 2011 sobre redes neuronales . págs. 1141–1145. arXiv : 1104.2097 . doi :10.1109/IJCNN.2011.6033352.

Lectura adicional

• Dudley, RM (1999). Teoremas del límite central uniforme . Cambridge University Press. ISBN 0-521-46102-2.
• Pitman, EJG (1979). "La función de distribución de la muestra". Algunas teorías básicas para la inferencia estadística . Londres, Reino Unido: Chapman and Hall. págs. 79–97. ISBN 0-470-26554-X.
• Shorack, GR ; Wellner, JA (1986). Procesos empíricos con aplicaciones a la estadística . Wiley. ISBN 0-471-86725-X.
• van der Vaart, AW ; Wellner, JA (1996). Convergencia débil y procesos empíricos . Saltador. ISBN 0-387-94640-3.
• van der Vaart, Aad W .; Wellner, Jon A. (1996). Teoremas de Glivenko-Cantelli . Saltador.
• van der Vaart, Aad W. ; Wellner, Jon A. (2000). Teoremas de preservación para clases Glivenko-Cantelli y Glivenko-Cantelli uniformes . Springer.