Hoeffding inequality for bounded independent random variables

Let $X_{1}$ , $X_{2},\ldots,X_{n}$ be independent random variables, such that $\Pr(a_{k}\leq X_{k}\leq b_{k})=1$ for all $k$ , where $a_{k}$ and $b_{k}$ are constant, $a_{k}<b_{k}$ . Let $S_{n}$ be the sum $X_{1}+\ldots+X_{n}$ . Then

\Pr(S_{n}-E[S_{n}]>\epsilon)\leq\exp\Big{(}-\frac{2\epsilon^{2}}{\sum_{k=1}^{n% }(b_{k}-a_{k})^{2}}\Big{)},

\Pr(|S_{n}-E[S_{n}]|>\epsilon)\leq 2\exp\Big{(}-\frac{2\epsilon^{2}}{\sum_{k=1% }^{n}(b_{k}-a_{k})^{2}}\Big{)}.

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