Caso especial de variables aleatorias de Bernoulli
La desigualdad de Hoeffding se puede aplicar al importante caso especial de las variables aleatorias de Bernoulli distribuidas de manera idéntica , y así es como la desigualdad se usa a menudo en combinatoria e informática . Consideramos una moneda que muestra cara con probabilidad py cruz con probabilidad 1 - p . Lanzamos la moneda n veces. El número esperado de veces que la moneda sale cara es pn . Además, la probabilidad de que la moneda salga cara como máximo k veces se puede cuantificar exactamente mediante la siguiente expresión:
donde H ( n ) es el número de caras en n lanzamientos de moneda.
Cuando k = ( p - ε ) n para algunos ε > 0 , la desigualdad de Hoeffding limita esta probabilidad por un término que es exponencialmente pequeño en ε 2 n :
De manera similar, cuando k = ( p + ε ) n para algunos ε > 0 , la desigualdad de Hoeffding limita la probabilidad de que veamos al menos εn más lanzamientos que muestren cara de lo que cabría esperar:
Por tanto, 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.
Por ejemplo, tomando da:
Caso general de variables aleatorias acotadas
Deje que X 1 , ..., X n ser variables aleatorias independientes delimitadas por el intervalo [0, 1] : 0 ≤ X i ≤ 1 . Definimos la media empírica de estas variables por
Una de las desigualdades en el teorema 1 de Hoeffding (1963) establece
dónde .
El teorema 2 de Hoeffding (1963) es una generalización de la desigualdad anterior cuando se sabe que X i están estrictamente limitados por los intervalos [ a i , b i ] :
que son válidos para valores positivos de t . Aquí E [ X ] es el valor esperado de X . Las desigualdades también se pueden expresar en términos de la suma
de las variables aleatorias:
Tenga en cuenta que las desigualdades también se mantienen cuando X i se ha obtenido utilizando un 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, ver, por ejemplo, el artículo de Serfling (1974) .
Caso general de variables aleatorias subgaussianas
Una variable aleatoria X se llama subgaussiana, [3] si
para algunos c> 0. Para una variable aleatoria X , la siguiente norma es finita si y solo si es subgaussiana:
Entonces, sean X 1 , ..., X n variables aleatorias subgaussianas independientes de media cero, la versión general de la desigualdad de Hoeffding establece que:
donde c > 0 es una constante absoluta. Consulte el teorema 2.6.2 de Vershynin (2018) para obtener más detalles.
Prueba
En esta sección, damos una prueba de la desigualdad de Hoeffding. [4] La demostración utiliza el lema de Hoeffding :
Suponga que X es una variable aleatoria real tal que . Luego
Usando este lema, podemos probar la desigualdad de Hoeffding. Suponga que X 1 , ..., X n son n variables aleatorias independientes tales que
La desigualdad de Hoeffding es útil para analizar el número de muestras requeridas necesarias para obtener un intervalo de confianza al resolver la desigualdad en el Teorema 1:
La desigualdad establece que la probabilidad de que los valores estimados y verdaderos difieran en más de t está limitada por e −2 nt 2 . Simétricamente, la desigualdad también es válida para otro lado de la diferencia:
Sumando ambos, podemos obtener una variante de dos caras de esta desigualdad:
Esta probabilidad se puede interpretar como el nivel de significancia (probabilidad de cometer un error) para un intervalo de confianza alrededor de de tamaño 2 t :
Resolver lo anterior para n nos da lo siguiente:
Por lo tanto, requerimos al menos muestras para adquirir -intervalo de confianza .
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.
Tenga en cuenta que esta desigualdad es la más conservadora de las tres del Teorema 1, y existen métodos más eficientes para estimar un intervalo de confianza .
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 .
Nowak, Robert (2009). "Conferencia 7: Chernoff's Bound y la desigualdad de Hoeffding" (PDF) . ECE 901 (verano de 2009): Apuntes de conferencias sobre teoría del aprendizaje estadístico . Universidad de Wisconsin-Madison . Consultado el 16 de mayo de 2014 .
Vershynin, Roman (2018). Probabilidad de alta dimensión . Prensa de la Universidad de Cambridge. ISBN 9781108415194.
Kahane, JP (1960). "Propriétés locales des fonctions à séries de Fourier aléatoires". Semental. Matemáticas . 19 . págs. 1–25. [1] .