# Chernoff/Hoeffding bounds

Let $X_1,X_2,\ldots,X_n\in [-1,1]$ be independent random variables. Let ${\mathbb E}[X_i]=p_i$. Let $\epsilon>0$. Then,

$\Pr\left[\frac{X_1+X_2+\ldots+X_n}{n}-\frac{p_1+p_2+\ldots+p_n}{n} \geq \epsilon\right]\leq e^{-\epsilon^2 n/2}.$

By symmetry (negating the variables),

$\Pr\left[\frac{X_1+X_2+\ldots+X_n}{n}-\frac{p_1+p_2+\ldots+p_n}{n} \leq -\epsilon\right]\leq e^{-\epsilon^2 n/2}.$

and, by the union bound,

$\Pr\left[\left|\frac{X_1+X_2+\ldots+X_n}{n}-\frac{p_1+p_2+\ldots+p_n}{n}\right| \geq \epsilon\right]\leq 2e^{-\epsilon^2 n/2}.$

The production of this material was supported in part by NSF award SES-0734780.