stringtranslate.com

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 .

Declaración

Sean X 1 , ..., X n variables aleatorias independientes tales que casi con seguridad . Considere la suma de estas variables aleatorias,

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

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]

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]

o equivalentemente,

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.

Caso general de variables aleatorias acotadas por encima

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

Sean X 1 , ..., X n variables aleatorias independientes tales que y casi con seguridad . Denote por

La desigualdad de Hoeffding para variables aleatorias acotadas de las anteriores establece que para todos ,

En particular, si para todos , entonces para todos ,

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

para algunos . Para cualquier variable acotada X , para algunos T suficientemente grandes . Entonces, para todos, tomando así se obtiene

para . Por lo tanto, cada variable acotada es subgaussiana.

Para una variable aleatoria X , la siguiente norma es finita si y solo si X 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. [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

Usando este lema, podemos demostrar la desigualdad de Hoeffding. Como en el enunciado del teorema, supongamos que X 1 , ..., X n son n variables aleatorias independientes tales que casi con seguridad para todo i , y sea .

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

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 función cuadrática, lo que da

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

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:

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 ε 2 n :

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.

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 ɛ :

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:

Por lo tanto, necesitamos al menos muestras para adquirir un intervalo de confianza de .

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

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