Hoeffding inequality for bounded independent random variables


Let X1, X2,,Xn be independentPlanetmathPlanetmath random variablesMathworldPlanetmath, such that Pr(akXkbk)=1 for all k, where ak and bk are constant, ak<bk. Let Sn be the sum X1++Xn. Then

Pr(Sn-E[Sn]>ϵ)exp(-2ϵ2k=1n(bk-ak)2),
Pr(|Sn-E[Sn]|>ϵ)2exp(-2ϵ2k=1n(bk-ak)2).

References

  • 1 W. Hoeffding, “Probability inequalities for sums of bounded random variables”, J. Amer. Statist. Assoc., vol. 58, pp.13-30, 1963.
Title Hoeffding inequality for bounded independent random variables
Canonical name HoeffdingInequalityForBoundedIndependentRandomVariables
Date of creation 2013-03-22 17:46:02
Last modified on 2013-03-22 17:46:02
Owner kshum (5987)
Last modified by kshum (5987)
Numerical id 8
Author kshum (5987)
Entry type Theorem
Classification msc 60E15
Related topic ChernoffCramerBound
Defines Hoeffding’s inequality