Bernstein's Inequality

Let $X_1, \ldots, X_n$ be independent with common mean $0$, variances $\mathbb{V}(X_i) \leq \sigma^2$, and suppose that $|X_i| \leq M$ for all $i$.
Then, for every $\epsilon > 0$,

(1)
\begin{align} \mathbb{P}(|\overline{X}| \geq \epsilon) \leq 2 e^{-c \, 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} = 2 \sigma^2 + \frac{2}{3}M \epsilon. \end{align}
page revision: 0, last edited: 05 Nov 2015 01:06