In probability theory, Bennett's inequality provides an upper bound on the probability that the sum of independent random variables deviates from its expected value by more than any specified amount. Bennett's inequality was proved by George Bennett of the University of New South Wales in 1962.[1]
Statement
Let X1, … Xn be independent random variables with finite variance and assume (for simplicity but without loss of generality) they all have zero expected value. Further assume Xi ≤ a almost surely for all i, and define \( {\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}} \) and \( {\displaystyle \sigma ^{2}=\sum _{i=1}^{n}\operatorname {E} (X_{i}^{2}).} \) Then for any 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),} ])
where h(u) = (1 + u)log(1 + u) – u.[2][3]
Generalizations and comparisons to other bounds
For generalizations see Freedman (1975)[4] and Fan, Grama and Liu (2012)[5] for a martingale version of Bennett's inequality and its improvement, respectively.
Hoeffding's inequality only assumes the summands are bounded almost surely, while Bennett's inequality offers some improvement when the variances of the summands are small compared to their almost sure bounds. However Hoeffding's inequality entails sub-Gaussian tails, whereas in general Bennett's inequality has Poissonian tails. In both inequalities, unlike some other inequalities or limit theorems, there is no requirement that the component variables have identical or similar distributions.
See also
Concentration inequality - a summary of tail-bounds on random variables.
References
Bennett, G. (1962). "Probability Inequalities for the Sum of Independent Random Variables". Journal of the American Statistical Association. 57 (297): 33–45. doi:10.2307/2282438. JSTOR 2282438.
Devroye, Luc; Lugosi, Gábor (2001). Combinatorial methods in density estimation. Springer. p. 11. ISBN 978-0-387-95117-1.
Boucheron, Stephane; Lugosi, Gabor; Massart, Pascal (2013). Concentration inequalities, a nonasymptotic theory of independence. Oxford University Press. ISBN 978-0-19-953525-5.
Freedman, D. A. (1975). "On tail probabilities for martingales". 3. The Annals of Probability: 100–118. JSTOR 2959268.
Fan, X.; Grama, I.; Liu, Q. (2012). "Hoeffding's inequality for supermartingales". Stochastic Processes and their Applications. 122: 3545–3559. arXiv:1109.4359. doi:10.1016/j.spa.2012.06.009.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
