# 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}. 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 HoeffdingInequalityForBoundedIndependentRandomVariables 2013-03-22 17:46:02 2013-03-22 17:46:02 kshum (5987) kshum (5987) 8 kshum (5987) Theorem msc 60E15 ChernoffCramerBound Hoeffding’s inequality