Desigualdad de concentración

Desigualdad matemática que explica la concentración de variables aleatorias

En la teoría de la probabilidad , las desigualdades de concentración proporcionan límites matemáticos a la probabilidad de que una variable aleatoria se desvíe de algún valor (normalmente, su valor esperado ).

La ley de los grandes números de la teoría de probabilidad clásica establece que las sumas de variables aleatorias independientes, en condiciones suaves, se concentran alrededor de su expectativa con una alta probabilidad. Estas sumas son los ejemplos más básicos de variables aleatorias concentradas alrededor de su media .

Las desigualdades de concentración se pueden ordenar según la cantidad de información sobre la variable aleatoria que se necesita para utilizarlas. ^{[ cita necesaria ]}

La desigualdad de Markov

Sea una variable aleatoria que no sea negativa ( casi con seguridad ). Entonces, para cada constante , ${\displaystyle X}$ ${\displaystyle a>0}$

${\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} (X)}{a}}.}$

Tenga en cuenta la siguiente extensión de la desigualdad de Markov: si es una función estrictamente creciente y no negativa, entonces ${\displaystyle \Phi }$

${\displaystyle \Pr(X\geq a)=\Pr(\Phi (X)\geq \Phi (a))\leq {\frac {\operatorname {E} (\Phi (X))}{\Phi (a)}}.}$

La desigualdad de Chebyshev

La desigualdad de Chebyshev requiere la siguiente información sobre una variable aleatoria : ${\displaystyle X}$

• El valor esperado es finito. ${\displaystyle \operatorname {E} [X]}$
• La varianza es finita. ${\displaystyle \operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]}$

Entonces, para cada constante , ${\displaystyle a>0}$

${\displaystyle \Pr(|X-\operatorname {E} [X]|\geq a)\leq {\frac {\operatorname {Var} [X]}{a^{2}}},}$

o equivalente,

${\displaystyle \Pr(|X-\operatorname {E} [X]|\geq a\cdot \operatorname {Std} [X])\leq {\frac {1}{a^{2}}},}$

¿Dónde está la desviación estándar de ? ${\displaystyle \operatorname {Std} [X]}$ ${\displaystyle X}$

La desigualdad de Chebyshev puede verse como un caso especial de la desigualdad generalizada de Markov aplicada a la variable aleatoria con . ${\displaystyle |X-\operatorname {E} [X]|}$ ${\displaystyle \Phi (x)=x^{2}}$

Desigualdad de Vysochanskij-Petunin

Sea X una variable aleatoria con distribución unimodal, media μ y varianza finita distinta de cero σ ² . Entonces, para cualquier ${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299\ldots ,}$

${\displaystyle {\text{Pr}}(\left|X-\mu \right|\geq \lambda \sigma )\leq {\frac {4}{9\lambda ^{2}}}.}$

(Para una prueba relativamente elemental, consulte, por ejemplo, ^[1] ).

Desigualdad unilateral de Vysochanskij-Petunin

Para una variable aleatoria unimodal y , la desigualdad unilateral de Vysochanskij-Petunin ^[2] se cumple de la siguiente manera: ${\displaystyle X}$ ${\displaystyle r\geq 0}$

${\displaystyle {\text{Pr}}(X-E[X]\geq r)\leq {\begin{cases}{\dfrac {4}{9}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}&{\text{for }}r^{2}\geq {\dfrac {5}{3}}\operatorname {Var} (X),\\[5pt]{\dfrac {4}{3}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}-{\dfrac {1}{3}}&{\text{otherwise.}}\end{cases}}}$

Desigualdad de Paley-Zygmund

A diferencia de las desigualdades de concentración más utilizadas, la desigualdad de Paley-Zygmund proporciona un límite inferior a la probabilidad de desviación.

La desigualdad de Cantelli

La desigualdad de Gauss

Límites de Chernoff

El límite genérico de Chernoff ^{[3] : 63–65} requiere la función generadora de momento de , definida como Siempre existe, pero puede ser infinita. De la desigualdad de Markov, para cada : ${\displaystyle X}$ ${\displaystyle M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right].}$ ${\displaystyle t>0}$

${\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}},}$

y para cada : ${\displaystyle t<0}$

${\displaystyle \Pr(X\leq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}}.}$

Existen varios límites de Chernoff para diferentes distribuciones y diferentes valores del parámetro . Véase ^{[4] : ​​5–7} para una recopilación de más desigualdades de concentración. ${\displaystyle t}$

Límites de sumas de variables acotadas independientes

Sean variables aleatorias independientes tales que, para todo i : ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$

${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ casi seguramente .

${\displaystyle c_{i}:=b_{i}-a_{i}}$

${\displaystyle \forall i:c_{i}\leq C}$

Sea su suma, su valor esperado y su varianza: ${\displaystyle S_{n}}$ ${\displaystyle E_{n}}$ ${\displaystyle V_{n}}$

${\displaystyle S_{n}:=\sum _{i=1}^{n}X_{i}}$

${\displaystyle E_{n}:=\operatorname {E} [S_{n}]=\sum _{i=1}^{n}\operatorname {E} [X_{i}]}$

${\displaystyle V_{n}:=\operatorname {Var} [S_{n}]=\sum _{i=1}^{n}\operatorname {Var} [X_{i}]}$

A menudo resulta interesante acotar la diferencia entre la suma y su valor esperado. Se pueden utilizar varias desigualdades.

1. La desigualdad de Hoeffding dice que:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)\leq 2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

2. La variable aleatoria es un caso especial de martingala y . Por lo tanto, la forma general de la desigualdad de Azuma también se puede utilizar y produce un límite similar: ${\displaystyle S_{n}-E_{n}}$ ${\displaystyle S_{0}-E_{0}=0}$

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

Esta es una generalización de Hoeffding ya que puede manejar otros tipos de martingalas, así como supermartingalas y submartingalas . Véase Fan et al. (2015). ^[5] Tenga en cuenta que si se utiliza la forma más simple de la desigualdad de Azuma, el exponente en el límite es peor por un factor de 4.

3. La función de suma, , es un caso especial de una función de n variables. Esta función cambia de forma acotada: si se cambia la variable i , el valor de f cambia como máximo . Por lo tanto, la desigualdad de McDiarmid también se puede utilizar y produce un límite similar: ${\displaystyle S_{n}=f(X_{1},\dots ,X_{n})}$ ${\displaystyle b_{i}-a_{i}<C}$

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

Esta es una generalización diferente de Hoeffding, ya que puede manejar otras funciones además de la función de suma, siempre que cambien de forma acotada.

4. La desigualdad de Bennett ofrece cierta mejora con respecto a la de Hoeffding cuando las varianzas de los sumandos son pequeñas en comparación con sus límites casi seguros C. Dice que:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left[-{\frac {V_{n}}{C^{2}}}h\left({\frac {Ct}{V_{n}}}\right)\right],}$dónde ${\displaystyle h(u)=(1+u)\log(1+u)-u}$

5. La primera de las desigualdades de Bernstein dice que:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}/2}{V_{n}+C\cdot t/3}}\right)}$

Esta es una generalización de Hoeffding, ya que puede manejar variables aleatorias no solo con un límite casi seguro sino también con un límite casi seguro y un límite de varianza.

6. Los límites de Chernoff tienen una forma particularmente simple en el caso de la suma de variables independientes, ya que . ${\displaystyle \operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}}$

Por ejemplo, ^[6] supongamos que las variables satisfacen , para . Entonces tenemos una desigualdad de cola más baja: ${\displaystyle X_{i}}$ ${\displaystyle X_{i}\geq E(X_{i})-a_{i}-M}$ ${\displaystyle 1\leq i\leq n}$

${\displaystyle \Pr[S_{n}-E_{n}<-\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}$

Si satisface , tenemos la desigualdad de la cola superior: ${\displaystyle X_{i}}$ ${\displaystyle X_{i}\leq E(X_{i})+a_{i}+M}$

${\displaystyle \Pr[S_{n}-E_{n}>\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}$

Si son iid y es la varianza de , una versión típica de la desigualdad de Chernoff es: ${\displaystyle X_{i}}$ ${\displaystyle |X_{i}|\leq 1}$ ${\displaystyle \sigma ^{2}}$ ${\displaystyle X_{i}}$

${\displaystyle \Pr[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n}{\text{ for }}0\leq k\leq 2\sigma .}$

7. Se pueden encontrar límites similares en: Distribución de Rademacher#Límites en sumas

Desigualdad de Efron-Stein

La desigualdad de Efron-Stein (o desigualdad de influencia, o MG ligada a la varianza) limita la varianza de una función general.

Supongamos que , son independientes y tienen la misma distribución para todos . ${\displaystyle X_{1}\dots X_{n}}$ ${\displaystyle X_{1}'\dots X_{n}'}$ ${\displaystyle X_{i}'}$ ${\displaystyle X_{i}}$ ${\displaystyle i}$

deja entonces ${\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).}$

${\displaystyle \mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}].}$

Se puede encontrar una prueba, por ejemplo, en. ^[7]

Desigualdad de Bretagnolle-Huber-Carol

La desigualdad de Bretagnolle-Huber-Carol limita la diferencia entre un vector de variables aleatorias distribuidas multinomialmente y un vector de valores esperados. ^{[8] [9]} Una prueba simple aparece en ^[10] (Sección del Apéndice).

Si un vector aleatorio tiene una distribución multinomial con parámetros y satisface entonces ${\displaystyle (Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})}$ ${\displaystyle (p_{1},p_{2},\ldots ,p_{n})}$ ${\displaystyle Z_{1}+Z_{2}+\dots +Z_{n}=M,}$

${\displaystyle \Pr \left(\sum _{i=1}^{n}|Z_{i}-Mp_{i}|\geq 2M\varepsilon \right)\leq 2^{n}e^{-2M\varepsilon ^{2}}.}$

Esta desigualdad se utiliza para limitar la distancia de variación total .

Desigualdad de Mason y van Zwet

La desigualdad de Mason y van Zwet ^[11] para vectores aleatorios multinomiales implica una ligera modificación del estadístico chi-cuadrado clásico.

Sea el vector aleatorio una distribución multinomial con parámetros y tales que para Entonces para cada y existen constantes tales que para todos y satisfactorias y tenemos ${\displaystyle (N_{1},\ldots ,N_{k})}$ ${\displaystyle n}$ ${\displaystyle (p_{1},\ldots ,p_{k})}$ ${\displaystyle p_{i}>0}$ ${\displaystyle i<k.}$ ${\displaystyle C>0}$ ${\displaystyle \delta >0}$ ${\displaystyle a,b,c>0,}$ ${\displaystyle n\geq 1}$ ${\displaystyle \lambda ,p_{1},\ldots ,p_{k-1}}$ ${\displaystyle \lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}}$ ${\displaystyle \sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,}$

${\displaystyle \Pr \left(\sum _{i=1}^{k-1}{\frac {(N_{i}-np_{i})^{2}}{np_{i}}}>\lambda \right)\leq ae^{bk-c\lambda }.}$

Desigualdad de Dvoretzky-Kiefer-Wolfowitz

La desigualdad de Dvoretzky-Kiefer-Wolfowitz limita la diferencia entre la función de distribución acumulativa real y empírica .

Dado un número natural , sean variables aleatorias independientes de valor real e idénticamente distribuidas con función de distribución acumulativa F (·). Denotemos la función de distribución empírica asociada definida por ${\displaystyle n}$ ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ ${\displaystyle F_{n}}$

${\displaystyle F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\}},\qquad x\in \mathbb {R} .}$

También lo es la probabilidad de que una sola variable aleatoria sea menor que y el número promedio de variables aleatorias que son menores que . ${\displaystyle F(x)}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle F_{n}(x)}$ ${\displaystyle x}$

Entonces

${\displaystyle \Pr \left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2}}{\text{ for every }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}}.}$

Desigualdades anticoncentración

Las desigualdades anticoncentración , por otro lado, proporcionan un límite superior sobre cuánto puede concentrarse una variable aleatoria alrededor de una cantidad.

Por ejemplo, Rao y Yehudayoff ^[12] muestran que existe algo tal que, para la mayoría de las direcciones del hipercubo , lo siguiente es cierto: ^{[ se necesita aclaración ]} ${\displaystyle C>0}$ ${\displaystyle x\in \{\pm 1\}^{n}}$

${\displaystyle \Pr \left(\langle x,Y\rangle =k\right)\leq {\frac {C}{\sqrt {n}}},}$

donde se extrae uniformemente de un subconjunto de tamaño suficientemente grande. ${\displaystyle Y}$ ${\displaystyle B\subseteq \{\pm 1\}^{n}}$

Estas desigualdades son importantes en varios campos, incluida la complejidad de la comunicación ( por ejemplo , en las pruebas del problema de Hamming ^[13] ) y la teoría de grafos . ^[14]

Se puede obtener una desigualdad anticoncentración interesante para sumas ponderadas de variables aleatorias independientes de Rademacher utilizando las desigualdades de Paley-Zygmund y Khintchine . ^[15]

Referencias

1. Pukelsheim, F., 1994. La regla de las tres sigma. The American Statistician, 48 (2), págs. 88–91
2. Mercadier, Mathieu; Strobel, Frank (16 de noviembre de 2021). "Una desigualdad unilateral de Vysochanskii-Petunin con aplicaciones financieras". Revista europea de investigación operativa . 295 (1): 374–377. doi :10.1016/j.ejor.2021.02.041. ISSN  0377-2217.
3. Mitzenmacher, Michael; Upfal, Eli (2005). Probabilidad y Computación: Algoritmos Aleatorios y Análisis Probabilístico. Prensa de la Universidad de Cambridge. ISBN 0-521-83540-2.
4. Slagle, NP (2012). "Cien estadísticas y desigualdades de probabilidad". arXiv : 2102.07234 .
5. Ventilador, X.; Grama, I.; Liu, Q. (2015). "Desigualdades exponenciales para martingalas con aplicaciones". Revista Electrónica de Probabilidad . 20 . Electrón. J. Probab. 20: 1–22. arXiv : 1311.6273 . doi :10.1214/EJP.v20-3496.
6. Chung, ventilador ; Lu, Linyuan (2010). «Viejas y nuevas desigualdades de concentración» (PDF) . Redes y gráficos complejos . Sociedad Matemática Estadounidense . Consultado el 14 de agosto de 2018 .
7. Boucheron, St{\'e}phane; Lugosi, G{\'a}bor; Bousquet, Olivier (2004). "Desigualdades de concentración". Conferencias avanzadas sobre aprendizaje automático: Escuelas de verano de ML 2003, Canberra, Australia, 2 al 14 de febrero de 2003, T{\"u}bingen, Alemania, 4 al 16 de agosto de 2003, Conferencias revisadas . Springer: 208–240.
8. Bretagnolle, Jean; Huber-Carol, Catherine (1978). Lois empiriques et Distance de Prokhorov. Apuntes de conferencias de matemáticas. vol. 649, págs. 332–341. doi :10.1007/BFb0064609. ISBN 978-3-540-08761-8.
9. van der Vaart, AW; Wellner, JA (1996). Convergencia débil y procesos empíricos: con aplicaciones a la estadística . Medios de ciencia y negocios de Springer.
10. Yuto Ushioda; Masato Tanaka; Tomomi Matsui (2022). "Métodos de Monte Carlo para el índice de potencia Shapley-Shubik". Juegos . 13 (3): 44. arXiv : 2101.02841 . doi : 10.3390/g13030044 .
11. Masón, David M.; Willem R. Van Zwet (1987). "Un refinamiento de la desigualdad del KMT para el proceso empírico uniforme". Los anales de la probabilidad . 15 (3): 871–884. doi : 10.1214/aop/1176992070 .
12. Rao, Anup; Yehudayoff, Amir (2018). "Anticoncentración en la mayoría de direcciones". Coloquio Electrónico sobre Complejidad Computacional.
13. Sherstov, Alexander A. (2012). "La complejidad de la comunicación de la distancia Gap Hamming". Teoría de la Computación .
14. Mateo Kwan; Benny Sudakov; Tuan Tran (2018). "Anticoncentración para estadísticas de subgrafos". Revista de la Sociedad Matemática de Londres . 99 (3): 757–777. arXiv : 1807.05202 . Código Bib : 2018arXiv180705202K. doi :10.1112/jlms.12192. S2CID  54065186.
15. Veraar, Mark (2009). "Sobre las desigualdades de Khintchine con un peso". arXiv : 0909.2586v1 [matemáticas.PR].

enlaces externos

• Karthik Sridharan, "Una suave introducción a las desigualdades de concentración" - Universidad de Cornell