La desigualdad de Bennett

En teoría de la probabilidad , la desigualdad de Bennett proporciona una cota superior para 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 ]}

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

${\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 ]}

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

La desigualdad de Hoeffding solo presupone que los sumandos están acotados casi con seguridad, 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.

La desigualdad de Bennett es muy similar a las desigualdades de Bernstein , la primera de las cuales también proporciona concentración en términos de la varianza y una cota casi segura para los términos individuales. La desigualdad de Bennett es más fuerte que esta cota, pero más compleja de calcular. ^{[ 3 ]}

En ambas desigualdades, a diferencia de otras desigualdades o teoremas límite, no se exige que las variables componentes tengan distribuciones idénticas o similares.

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${\displaystyle t\geq 10np}$, ${\displaystyle h({\frac {t}{np}})\geq {\frac {t}{2np}}\log {\frac {t}{np}},}$ entonces

${\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 proporciona una cota de${\displaystyle \exp(-2t^{2}/n)}$y la primera desigualdad de Bernstein proporciona una cota de${\displaystyle \exp(-{\frac {t^{2}}{2np+2t/3}})}$. Para${\displaystyle t\gg np}$La desigualdad de Hoeffding da${\displaystyle \exp(-\Theta (t^{2}/n))}$Bernstein da${\displaystyle \exp(-\Theta (t))}$y Bennett da${\displaystyle \exp(-\Theta (t\log {\frac {t}{np}}))}$.

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