La 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 determinada cantidad. La desigualdad de Hoeffding fue probada 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 nítido, en particular cuando la varianza de las variables aleatorias es pequeña. ^[2] Es similar, pero incomparable, a 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 los X _i se han obtenido mediante muestreo sin reemplazo; en este caso las variables aleatorias ya no son independientes. Una prueba de esta afirmación se puede encontrar 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).

Ejemplo

Supongamos y para todos yo . 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 ^[4] ${\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 equivalente,

$${\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 desde arriba

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

Sean X ₁ , ..., X _n variables aleatorias independientes tales que y casi con seguridad . Denotamos 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 a partir de arriba 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 . Recuerde que una variable aleatoria X se llama subgaussiana, ^[6] si

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

para algunos c>0. Para cualquier variable acotada X , para alguna T suficientemente grande . Entonces, para todos , así se obtienen rendimientos. ${\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 . Entonces toda variable acotada es subgaussiana. ${\displaystyle t\leq T}$

Para una variable aleatoria X , la siguiente norma es finita si y sólo 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. ^[7]

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 . ^[8] 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 minimizando el valor dentro del exponencial. Esto se puede hacer fácilmente optimizando una cuadrática, dando

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

Al escribir 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 iid de Bernoulli ). 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 mediante 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, requerimos al menos muestras para adquirir un intervalo de confianza - . ${\displaystyle \textstyle {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}}$ ${\displaystyle \textstyle (1-\alpha )}$ ${\displaystyle \textstyle p\pm \varepsilon }$

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

Ver también

• Desigualdad de concentración : un resumen de los límites finales de 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. Hoeffding (1963, teorema 1)
5. Fan, Grama y Liu (2015, Corolario 2.7)
6. Kahane (1960)
7. Vershynin (2018, teorema 2.6.2)
8. Boucheron (2013)

Referencias

• Serfling, Robert J. (1974). "Desigualdades de probabilidad de la suma en muestreo sin reemplazo". Los anales de la estadística . 2 (1): 39–48. doi : 10.1214/aos/1176342611 . SEÑOR  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. SEÑOR  0144363.
• Ventilador, X.; Grama, I.; Liu, Q. (2015). "Desigualdades exponenciales para martingalas con aplicaciones". Electrón. J. Probab . 20 (1): 1–22. arXiv : 1311.6273 . doi : 10.1214/EJP.v20-3496 .
• Vershynin, romano (2018). Probabilidad de alta dimensión . Prensa de la Universidad de Cambridge. 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: Prensa de la Universidad de Oxford. 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].