Chernoff/Hoeffding bounds

From Theory
Jump to: navigation, search

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008


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

<math>\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}.</math>

By symmetry (negating the variables),

<math>\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}.</math>

and, by the union bound,

<math>\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}.</math>




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