Hoeffding inequality for bounded independent random variables
Let X1, X2,…,Xn be independent random variables
, such that Pr(ak≤Xk≤bk)=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ϵ2∑nk=1(bk-ak)2), |
Pr(|Sn-E[Sn]|>ϵ)≤2exp(-2ϵ2∑nk=1(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 |