Hoeffding's Inequality
Let
$X_1, \ldots, X_n$ be iid with mean $\mu$ and suppose that $a_i \leq X_i \leq b_i$ for all i.
Then, for every $\epsilon > 0$,
\begin{align} P(|\overline{X} - \mu| > \epsilon) \leq 2 e^{-2c \, n \epsilon^2} \end{align}
where
(2)\begin{align} \overline{X} = \frac{1}{n}\sum_{i=1}^n X_i \end{align}
and
(3)\begin{align} \frac{1}{c} = \sum_{i=1}^n (b_i-a_i)^2. \end{align}
page revision: 3, last edited: 05 Nov 2015 00:51