La desigualdad de Bennett

En teoría de la probabilidad , la desigualdad de Bennett proporciona un límite superior a la probabilidad de que la suma de variables aleatorias independientes se desvíe de su valor esperado en más de una cantidad especificada. La desigualdad de Bennett fue demostrada por George Bennett de la Universidad de Nueva Gales del Sur en 1962. ^[1]

Declaración

Sean X ₁ , … X _n variables aleatorias independientes con varianza finita. Supongamos además que | X _i - E X _i | ≤ a casi con seguridad para todo i , y definamos y Entonces para cualquier t ≥ 0 , ${\displaystyle S_{n}=\sum _{i=1}^{n}\left[X_{i}-\operatorname {E} (X_{i})\right]}$ ${\displaystyle \sigma ^{2}=\sum _{i=1}^{n}\operatorname {E} (X_{i}-\operatorname {E} X_{i})^{2}.}$

${\displaystyle \Pr \left(S_{n}>t\right)\leq \exp \left(-{\frac {\sigma ^{2}}{a^{2}}}h\left({\frac {at}{\sigma ^{2}}}\right)\right),}$

donde h ( u ) = (1 + u )log(1 + u ) – u y log denota el logaritmo natural. ^{[2] [3]}

Generalizaciones y comparaciones con otros límites

Para generalizaciones, véase Freedman (1975) ^[4] y Fan, Grama y Liu (2012) ^[5] para una versión martingala de la desigualdad de Bennett y su mejora, respectivamente.

La desigualdad de Hoeffding sólo supone que los sumandos están acotados de forma casi segura, mientras que la desigualdad de Bennett ofrece cierta mejora cuando las varianzas de los sumandos son pequeñas en comparación con sus límites casi seguros. Sin embargo, la desigualdad de Hoeffding implica colas subgaussianas, mientras que en general la desigualdad de Bennett tiene colas poissonianas. ^{[ cita requerida ]}

La desigualdad de Bennett es más similar a las desigualdades de Bernstein , la primera de las cuales también proporciona concentración en términos de la varianza y un límite casi seguro en los términos individuales. La desigualdad de Bennett es más fuerte que este límite, pero más complicada de calcular. ^[3]

En ambas desigualdades, a diferencia de otras desigualdades o teoremas de límites, no existe ningún requisito de que las variables componentes tengan distribuciones idénticas o similares. ^{[ cita requerida ]}

Ejemplo

Supongamos que cada X _i es una variable aleatoria binaria independiente con probabilidad p . Entonces la desigualdad de Bennett dice que:

${\displaystyle \Pr \left(\sum _{i=1}^{n}X_{i}>pn+t\right)\leq \exp \left(-nph\left({\frac {t}{np}}\right)\right).}$

Para , entonces ${\displaystyle t\geq 10np}$ ${\displaystyle h({\frac {t}{np}})\geq {\frac {t}{2np}}\log {\frac {t}{np}},}$

${\displaystyle \Pr \left(\sum _{i=1}^{n}X_{i}>pn+t\right)\leq \left({\frac {t}{np}}\right)^{-t/2}}$

para . ${\displaystyle t\geq 10np}$

Por el contrario, la desigualdad de Hoeffding da un límite de y la primera desigualdad de Bernstein da un límite de . Para , la desigualdad de Hoeffding da , Bernstein da y Bennett da . ${\displaystyle \exp(-2t^{2}/n)}$ ${\displaystyle \exp(-{\frac {t^{2}}{2np+2t/3}})}$ ${\displaystyle t\gg np}$ ${\displaystyle \exp(-\Theta (t^{2}/n))}$ ${\displaystyle \exp(-\Theta (t))}$ ${\displaystyle \exp(-\Theta (t\log {\frac {t}{np}}))}$

Véase también

• Desigualdad de concentración : un resumen de los límites de cola en variables aleatorias.

Referencias

1. Bennett, G. (1962). "Desigualdades de probabilidad para la suma de variables aleatorias independientes". Revista de la Asociación Estadounidense de Estadística . 57 (297): 33–45. doi :10.2307/2282438. JSTOR  2282438.
2. Devroye, Luc ; Lugosi, Gábor (2001). Métodos combinatorios en la estimación de densidad. Springer . p. 11. ISBN 978-0-387-95117-1.
3. Boucheron, Stephane; Lugosi, Gabor; Massart, Pascal (2013). Desigualdades de concentración, una teoría no asintótica de la independencia . Oxford University Press. ISBN 978-0-19-953525-5.
4. Freedman, DA (1975). "Sobre las probabilidades de cola para las martingalas". Anales de probabilidad . 3 (1): 100–118. doi : 10.1214/aop/1176996452 ​​. JSTOR  2959268.
5. Fan, X.; Grama, I.; Liu, Q. (2012). "Desigualdad de Hoeffding para supermartingalas". Procesos estocásticos y sus aplicaciones . 122 (10): 3545–3559. arXiv : 1109.4359 . doi :10.1016/j.spa.2012.06.009. S2CID  13451239.