Desigualdad de concentración

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 desviación u otra función de la variable aleatoria puede considerarse una variable aleatoria secundaria. El ejemplo más simple de la concentración de una variable aleatoria secundaria de este tipo es la CDF de la primera variable aleatoria que concentra la probabilidad en la unidad. Si se dispone de una forma analítica de la CDF, esta proporciona una igualdad de concentración que proporciona la probabilidad exacta de concentración. Es precisamente cuando la CDF es difícil de calcular o incluso se desconoce la forma exacta de la primera variable aleatoria que las desigualdades de concentración aplicables proporcionan información útil.

Otro ejemplo casi universal de variable aleatoria secundaria es la ley de los grandes números de la teoría de probabilidad clásica, que establece que las sumas de variables aleatorias independientes, en condiciones moderadas, se concentran alrededor de su valor esperado 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 poder utilizarlas. ^{[ cita requerida ]}

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

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

Nótese la siguiente extensión de la desigualdad de Markov: si es una función estrictamente creciente y no negativa, entonces ${\estilo de visualización \Phi}$

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

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

• El valor esperado es finito.${\displaystyle \nombre del operador {E} [X]}$
• La varianza es finita.${\displaystyle \nombreoperador {Var} [X]=\nombreoperador {E} [(X-\nombreoperador {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 equivalentemente,

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

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

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

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, véase, por ejemplo, ^[1] ).

Para una variable aleatoria unimodal y , la desigualdad unilateral de Vysochanskij-Petunin ^[2] se cumple de la siguiente manera: ${\estilo de visualización 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}}}$

A diferencia de la mayoría de las desigualdades de concentración comúnmente utilizadas, la desigualdad de Paley-Zygmund proporciona un límite inferior a la probabilidad de desviación.

El límite genérico de Chernoff ^{[3] : 63–65} requiere la función generadora de momentos de , definida como Siempre existe, pero puede ser infinita. A partir 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 compilación de más desigualdades de concentración. ${\displaystyle t}$

Dejar . Entonces${\displaystyle Z\sim N(0,1)}$$${\displaystyle \operatorname {P} (|Z|>t)\leq {\sqrt {\frac {2}{\pi }}}{\frac {\exp(-t^{2}/2)}{t}}}$$

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 seguro .

${\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 inecuaciones.

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 una martingala y . Por lo tanto, también se puede utilizar la forma general de la desigualdad de Azuma y se obtiene 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 . Consulte Fan et al. (2015). ^[5] Nótese 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 suma, , es un caso especial de una función de n variables. Esta función cambia de manera acotada: si se cambia la variable i , el valor de f cambia como máximo en . Por lo tanto, también se puede utilizar la desigualdad de McDiarmid y se obtiene 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 suma, siempre que cambien de manera 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 inferior: ${\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 desigualdad de 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

La desigualdad de Efron-Stein (o desigualdad de influencia, o límite de MG en la varianza) limita la varianza de una función general.

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

Dejalo 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}].}$

Una prueba puede encontrarse, por ejemplo, en ^[7].

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 se distribuye multinomialmente 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 .

La desigualdad de Mason y van Zwet ^[11] para vectores aleatorios multinomiales se refiere a una ligera modificación de la estadística clásica de chi-cuadrado.

Sea el vector aleatorio distribuido multinomialmente con parámetros y tales que para Entonces, para cada y existen constantes tales que para todos y que satisfacen 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 }.}$

La desigualdad de Dvoretzky-Kiefer-Wolfowitz limita la diferencia entre la función de distribución acumulativa real y la 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 (·). Sea 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} .}$

Entonces, es la probabilidad de que una sola variable aleatoria sea menor que , y es 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}}.}$

Por otra parte, las desigualdades de anticoncentración proporcionan un límite superior sobre cuánto puede concentrarse una variable aleatoria, ya sea en un valor específico o en un rango de valores. Un ejemplo concreto es que si lanzas una moneda al aire varias veces, la probabilidad de que salga cara será menor que . Esta idea se puede generalizar en gran medida. Por ejemplo, un resultado de Rao y Yehudayoff ^[12] implica que para cualquier existe algún tal que, para cualquier , lo siguiente es cierto para al menos valores de : ${\displaystyle n}$${\displaystyle {\frac {1}{\sqrt {n}}}}$${\displaystyle \beta ,\delta >0}$${\displaystyle C>0}$${\displaystyle k}$${\displaystyle 2^{n(1-\delta )}}$${\displaystyle x\in \{\pm 1\}^{n}}$

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

donde se dibuja uniformemente desde . ${\displaystyle Y}$${\displaystyle \{\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 de Rademacher independientes utilizando las desigualdades de Paley-Zygmund y Khintchine . ^[15]

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