Desigualdad de Hoeffding

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

La desigualdad de Hoeffding es un caso particular de la desigualdad de Azuma-Hoeffding, aunque generaliza la desigualdad de Bernstein, demostrada por Sergei Bernstein en 1923. Ambas son casos especiales de la desigualdad de McDiarmid.

La desigualdad de Hoeffding puede aplicarse al importante especial de variables de Bernouilli idénticamente distribuidas, y este es la manera en que la desigualdad se aplica frecuentemente en combinatoria y en informática.

Si se considera una moneda desequilibrada que muestra cara con probabilidad $p$ y cruz con probabilidad $1-p$ , y se consideran $n$ lanzamientos de esta moneda. El valor esperado del número de veces que se obtiene cara es $p\cdot n$ . Más aún, la probabilidad de que se obtengan como mucho $k$ caras puede cuantificarse exactamente mediante la siguiente expresión:

$\Pr {\Big (}n{\text{ lanzamientos llevan como mucho a }}k{\text{ caras}}{\Big )}=\sum _{i=0}^{k}{\binom {n}{i}}p^{i}(1-p)^{n-i}\,.$

En el caso de que $k=(p-\epsilon )n$ para algún $\epsilon >0$ , la desigualdad de Hoeffding acota esta probabilidad mediante un término que disminuye exponencialmente en $\epsilon ^{2}\cdot n$ :

$\Pr {\Big (}n{\text{ se obtienen como mucho}}(p-\epsilon )n{\text{ caras}}{\Big )}\leq \exp {\big (}-2\epsilon ^{2}n{\big )}\,.$

De manera similar, en el caso de que $k=(p+\epsilon )n$ para algún $\epsilon >0$ , la desigualdad de Hoeffding acota la probabilidad de que se obtengan al menos $\epsilon n$ un número de caras mayor que el valor esperado:

$\Pr {\Big (}n{\text{ se obtienen como poco}}(p+\epsilon )n{\text{ caras}}{\Big )}\leq \exp {\big (}-2\epsilon ^{2}n{\big )}\,.$

En esas condiciones la desigualdad de Hoeffding implica que el número de caras que se obtienen se concentra alrededor de la media, con colas que decrecen exponencialmente.

$\Pr {\Big (}n{\text{ lanzamientos llevan a un número caras entre }}(p-\epsilon )n{\text{ y }}(p+\epsilon )n{\Big )}\geq 1-2\exp {\big (}-2\epsilon ^{2}n{\big )}\,.$

Caso general

Sean $X_{1},\dots ,X_{n}\!$ n variables aleatorias independientes. Si se asume que las $X_{i}$ están acotadas casi con seguridad; es decir, si se asume para $1\leq i\leq n$ que:

$\Pr(X_{i}\in [a_{i},b_{i}])=1.\!$

Se define la media muestral de estas variables como:

${\overline {X}}=(X_{1}+\cdots +X_{n})/n\,.$

El segundo teorema en el artículo de Hoeffding prueba las siguientes desigualdades:

$\Pr({\overline {X}}-\mathrm {E} [{\overline {X}}]\geq t)\leq \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!$

$\Pr(|{\overline {X}}-\mathrm {E} [{\overline {X}}]|\geq t)\leq 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!$

que son válidas para valores positivos de t. Aquí $\mathrm {E} [{\overline {X}}]$ representa el valor esperado de ${\overline {X}}$ .

Nótese que las desigualdades también son válidas cuando las $X_{i}$ han sido obtenidas usando muestreo sin reemplazo; en este caso las variables aleatorias no son de ninguna manera independientes. Una demostración de esta afirmación puede encontrarse en el artículo de Hoeffding. Para cotas ligeramente mejores en el caso de muestreo sin reemplazo, puede consultarse el artículo de Serfling (1974).

Desigualdad de Hoeffding

Caso general

Véase también

Referencias

Bibliografía

Related Articles