Desigualdad de Hoeffding

Desigualdad probabilística aplicada a la suma de variables aleatorias acotadas

En teoría de la probabilidad , la desigualdad de Hoeffding proporciona un límite superior a la probabilidad de que la suma de variables aleatorias independientes acotadas se desvíe de su valor esperado en más de una cierta cantidad. La desigualdad de Hoeffding fue demostrada por Wassily Hoeffding en 1963. ^[1]

La desigualdad de Hoeffding es un caso especial de la desigualdad de Azuma-Hoeffding y la desigualdad de McDiarmid . Es similar al límite de Chernoff , pero tiende a ser menos pronunciada, en particular cuando la varianza de las variables aleatorias es pequeña. ^[2] Es similar a, pero incomparable con, una de las desigualdades de Bernstein .

Declaración

Sean X ₁ , ..., X _n variables aleatorias independientes tales que casi con seguridad . Considere la suma de estas variables aleatorias, ${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$

${\displaystyle S_{n}=X_{1}+\cdots +X_{n}.}$

Entonces el teorema de Hoeffding establece que, para todo t > 0 , ^[3]

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\\\operatorname {P} \left(\left|S_{n}-\mathrm {E} \left[S_{n}\right]\right|\geq t\right)&\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\end{aligned}}}$

Aquí E[ S _n ] es el valor esperado de S _n .

Obsérvese que las desigualdades también se cumplen cuando las X _i se han obtenido mediante muestreo sin reemplazo; en este caso, las variables aleatorias ya no son independientes. Se puede encontrar una prueba de esta afirmación en el artículo de Hoeffding. Para límites ligeramente mejores en el caso del muestreo sin reemplazo, véase, por ejemplo, el artículo de Serfling (1974).

Generalización

Sean observaciones independientes tales que y . Sea . Entonces, para cualquier , ^[4] ${\displaystyle Y_{1},\dots ,Y_{n}}$ ${\displaystyle \operatorname {E} (Y_{i})=0}$ ${\displaystyle a_{i}\leq Y_{i}\leq b_{i}}$ ${\displaystyle \epsilon >0}$ ${\displaystyle t>0}$ $${\displaystyle P\left(\sum _{i=1}^{n}Y_{i}\geq \epsilon \right)\leq \exp \left(-t\epsilon +\sum _{i=1}^{n}t^{2}(b_{i}-a_{i})^{2}/8\right)}$$

Caso especial: vehículos recreativos Bernoulli

Supongamos que y para todos los i . Esto puede ocurrir cuando X _i son variables aleatorias independientes de Bernoulli , aunque no es necesario que estén distribuidas de manera idéntica. Entonces obtenemos la desigualdad ^[5] ${\displaystyle a_{i}=0}$ ${\displaystyle b_{i}=1}$

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&\leq \exp(-2t^{2}/n)\\\operatorname {P} \left(\left|S_{n}-\mathrm {E} \left[S_{n}\right]\right|\geq t\right)&\leq 2\exp(-2t^{2}/n)\end{aligned}}}$

o equivalentemente,

$${\displaystyle {\begin{aligned}\operatorname {P} \left((S_{n}-\mathrm {E} \left[S_{n}\right])/n\geq t\right)&\leq \exp(-2nt^{2})\\\operatorname {P} \left(\left|(S_{n}-\mathrm {E} \left[S_{n}\right])/n\right|\geq t\right)&\leq 2\exp(-2nt^{2})\end{aligned}}}$$

para todos . Esta es una versión del límite aditivo de Chernoff que es más general, ya que permite variables aleatorias que toman valores entre cero y uno, pero también más débil, ya que el límite de Chernoff proporciona un mejor límite de cola cuando las variables aleatorias tienen una varianza pequeña. ${\displaystyle t\geq 0}$

Caso general de variables aleatorias acotadas por encima

La desigualdad de Hoeffding se puede extender al caso de variables aleatorias acotadas desde arriba. ^[6]

Sean X ₁ , ..., X _n variables aleatorias independientes tales que y casi con seguridad . Denote por ${\displaystyle \mathrm {E} X_{i}=0}$ ${\displaystyle X_{i}\leq b_{i}}$

${\displaystyle {\begin{aligned}C_{i}^{2}=\left\{{\begin{array}{ll}\mathrm {E} X_{i}^{2},&\mathrm {if} \ \mathrm {E} X_{i}^{2}\geq b_{i}^{2},\\\displaystyle {\frac {1}{4}}\left(b_{i}+{\frac {\mathrm {E} X_{i}^{2}}{b_{i}}}\right)^{2},&{\textrm {otherwise}}.\end{array}}\right.\end{aligned}}}$

La desigualdad de Hoeffding para variables aleatorias acotadas de las anteriores establece que para todos , ${\displaystyle t\geq 0}$

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}C_{i}^{2}}}\right).}$

En particular, si para todos , entonces para todos , ${\displaystyle \mathrm {E} X_{i}^{2}\geq b_{i}^{2}}$ ${\displaystyle i}$ ${\displaystyle t\geq 0}$

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}\mathrm {E} X_{i}^{2}}}\right).}$

Caso general de variables aleatorias subgaussianas

La prueba de la desigualdad de Hoeffding se puede generalizar a cualquier distribución subgaussiana . Recordemos que una variable aleatoria X se denomina subgaussiana, ^[7] si

${\displaystyle \mathrm {P} (|X|\geq t)\leq 2e^{-ct^{2}},}$

para algunos . Para cualquier variable acotada X , para algunos T suficientemente grandes . Entonces, para todos, tomando así se obtiene ${\displaystyle c>0}$ ${\displaystyle \mathrm {P} (|X|\geq t)=0\leq 2e^{-ct^{2}}}$ ${\displaystyle t>T}$ ${\displaystyle 2e^{-cT^{2}}\leq 2e^{-ct^{2}}}$ ${\displaystyle t\leq T}$ ${\displaystyle c=\log(2)/T^{2}}$

${\displaystyle \mathrm {P} (|X|\geq t)\leq 1\leq 2e^{-cT^{2}}\leq 2e^{-ct^{2}},}$

para . Por lo tanto, cada variable acotada es subgaussiana. ${\displaystyle t\leq T}$

Para una variable aleatoria X , la siguiente norma es finita si y solo si X es subgaussiana:

${\displaystyle \Vert X\Vert _{\psi _{2}}:=\inf \left\{c\geq 0:\mathrm {E} \left(e^{X^{2}/c^{2}}\right)\leq 2\right\}.}$

Entonces, sean X ₁ , ..., X _n variables aleatorias subgaussianas independientes de media cero; la versión general de la desigualdad de Hoeffding establece que:

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {ct^{2}}{\sum _{i=1}^{n}\Vert X_{i}\Vert _{\psi _{2}}^{2}}}\right),}$

donde c > 0 es una constante absoluta. ^[8]

Prueba

La prueba de la desigualdad de Hoeffding se sigue de manera similar a las desigualdades de concentración como los límites de Chernoff . ^[9] La principal diferencia es el uso del Lema de Hoeffding :

Supongamos que X es una variable aleatoria real tal que casi con seguridad . Entonces ${\displaystyle X\in \left[a,b\right]}$

${\displaystyle \mathrm {E} \left[e^{s\left(X-\mathrm {E} \left[X\right]\right)}\right]\leq \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).}$

Usando este lema, podemos demostrar la desigualdad de Hoeffding. Como en el enunciado del teorema, supongamos que X ₁ , ..., X _n son n variables aleatorias independientes tales que casi con seguridad para todo i , y sea . ${\displaystyle X_{i}\in [a_{i},b_{i}]}$ ${\displaystyle S_{n}=X_{1}+\cdots +X_{n}}$

_{Entonces ,} para s , t > 0 , la desigualdad de Markov y la independencia de Xi implica:

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&=\operatorname {P} \left(\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\geq \exp(st)\right)\\&\leq \exp(-st)\mathrm {E} \left[\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\right]\\&=\exp(-st)\prod _{i=1}^{n}\mathrm {E} \left[\exp(s(X_{i}-\mathrm {E} \left[X_{i}\right]))\right]\\&\leq \exp(-st)\prod _{i=1}^{n}\exp {\Big (}{\frac {s^{2}(b_{i}-a_{i})^{2}}{8}}{\Big )}\\&=\exp \left(-st+{\tfrac {1}{8}}s^{2}\sum _{i=1}^{n}(b_{i}-a_{i})^{2}\right)\end{aligned}}}$

Este límite superior es el mejor para el valor de s, ya que minimiza el valor dentro de la exponencial. Esto se puede hacer fácilmente optimizando una ecuación cuadrática, lo que da

${\displaystyle s={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}.}$

Escribiendo el límite anterior para este valor de s , obtenemos el límite deseado:

${\displaystyle \operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).}$

Uso

Intervalos de confianza

La desigualdad de Hoeffding se puede utilizar para derivar intervalos de confianza . Consideramos una moneda que muestra cara con probabilidad p y cruz con probabilidad 1 − p . Lanzamos la moneda n veces, generando n muestras (que son variables aleatorias de Bernoulli iid ). El número esperado de veces que la moneda sale cara es pn . Además, la probabilidad de que la moneda salga cara al menos k veces se puede cuantificar exactamente con la siguiente expresión: ${\displaystyle X_{1},\ldots ,X_{n}}$

${\displaystyle \operatorname {P} (H(n)\geq k)=\sum _{i=k}^{n}{\binom {n}{i}}p^{i}(1-p)^{n-i},}$

donde H ( n ) es el número de caras en n lanzamientos de moneda.

Cuando k = ( p + ε ) n para algún ε > 0 , la desigualdad de Hoeffding limita esta probabilidad por un término que es exponencialmente pequeño en ε ² n :

${\displaystyle \operatorname {P} (H(n)-pn>\varepsilon n)\leq \exp \left(-2\varepsilon ^{2}n\right).}$

Dado que este límite se cumple en ambos lados de la media, la desigualdad de Hoeffding implica que el número de caras que vemos se concentra alrededor de su media, con una cola exponencialmente pequeña.

${\displaystyle \operatorname {P} \left(|H(n)-pn|>\varepsilon n\right)\leq 2\exp \left(-2\varepsilon ^{2}n\right).}$

Pensando en la media "observada", esta probabilidad se puede interpretar como el nivel de significancia (probabilidad de cometer un error) para un intervalo de confianza de tamaño 2 ɛ : ${\displaystyle {\overline {X}}={\frac {1}{n}}H(n)}$ ${\displaystyle \alpha }$ ${\displaystyle p}$

${\displaystyle \alpha =\operatorname {P} (\ {\overline {X}}\notin [p-\varepsilon ,p+\varepsilon ])\leq 2e^{-2\varepsilon ^{2}n}}$

Encontrar n para el signo de desigualdad opuesto en lo anterior, es decir, n que viola la desigualdad pero no la igualdad anterior, nos da:

${\displaystyle n\geq {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}}$

Por lo tanto, necesitamos al menos muestras para adquirir un intervalo de confianza de . ${\displaystyle \textstyle {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}}$ ${\displaystyle \textstyle (1-\alpha )}$ ${\displaystyle \textstyle p\pm \varepsilon }$

Por lo tanto, el costo de adquirir el intervalo de confianza es sublineal en términos de nivel de confianza y cuadrático en términos de precisión. Nótese que existen métodos más eficientes para estimar un intervalo de confianza .

Véase también

• Desigualdad de concentración : un resumen de los límites de cola de las variables aleatorias.
• Lema de Hoeffding
• Desigualdades de Bernstein (teoría de la probabilidad)

Notas

1. Höffding (1963)
2. Vershynin (2018, pág. 19)
3. Hoeffding (1963, Teorema 2)
4. Wasserman, Larry (2004). "Toda la estadística". Springer Texts in Statistics . doi :10.1007/978-0-387-21736-9. ISSN  1431-875X.
5. Hoeffding (1963, Teorema 1)
6. Fan, Grama y Liu (2015, Corolario 2.7)
7. Kahane (1960)
8. Vershynin (2018, teorema 2.6.2)
9. Boucheron (2013)

Referencias

• Serfling, Robert J. (1974). "Desigualdades de probabilidad para la suma en muestreo sin reemplazo". Anales de estadística . 2 (1): 39–48. doi : 10.1214/aos/1176342611 . MR  0420967.
• Hoeffding, Wassily (1963). "Desigualdades de probabilidad para sumas de variables aleatorias acotadas" (PDF) . Revista de la Asociación Estadounidense de Estadística . 58 (301): 13–30. doi :10.1080/01621459.1963.10500830. JSTOR  2282952. MR  0144363.
• Fan, X.; Grama, I.; Liu, Q. (2015). "Desigualdades exponenciales para martingalas con aplicaciones". Electron. J. Probab . 20 (1): 1–22. arXiv : 1311.6273 . doi : 10.1214/EJP.v20-3496 .
• Vershynin, Roman (2018). Probabilidad de alta dimensión . Cambridge University Press. ISBN 9781108415194.
• Boucheron, Stéphane (2013). Desigualdades de concentración: una teoría no asintótica de la independencia. Gábor Lugosi, Pascal Massart. Oxford: Oxford University Press. ISBN 978-0-19-953525-5.OCLC 837517674  .
• Kahane, JP (1960). "Propiedades locales de funciones de la serie de Fourier aléatoires". Semental. Matemáticas . vol. 19, págs. 1 a 25. [1].