Desigualdad de Hoeffding

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 .

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}\nombre del operador {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)\\\nombre del operador {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).

Sean observaciones independientes tales que y . Sea . Entonces, para cualquier , ^[4]${\displaystyle Y_{1},\puntos ,Y_{n}}$${\displaystyle \operatorname {E} (Y_{i})=0}$${\displaystyle a_{i}\leq Y_{i}\leq b_{i}}$${\displaystyle \epsilon >0}$${\estilo de visualización 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)}$$

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}$

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).}$

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]

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).}$

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 .

• 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)