# Bernstein inequalities

1) Let $\{X_{i}\}_{i=1}^{n}$ be a collection of independent random variables satisfying the conditions:
a) $E[X_{i}^{2}]<\infty$ $\forall i$, so that one can write $\sum_{i=1}^{n}E[X_{i}^{2}]=v^{2}$
b) $\exists c\in\mathbb{R}:\sum_{i=1}^{n}E[\left|X_{i}\right|^{k}]\leq\frac{1}{2}k% !v^{2}c^{k-2}$ for all integers $k\geq 3$

Then, for any $\varepsilon\geq 0$,

 $\Pr\left\{\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)>\varepsilon\right\}\leq% \exp\left[-\frac{v^{2}}{c^{2}}\left(1+\frac{c\varepsilon}{v^{2}}-\sqrt{1+2% \frac{c\varepsilon}{v^{2}}}\right)\right]\leq\exp\left(-\frac{\varepsilon^{2}}% {2\left(v^{2}+c\varepsilon\right)}\right)$
 $\Pr\left\{\left|\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)\right|>\varepsilon% \right\}\leq 2\exp\left[-\frac{v^{2}}{c^{2}}\left(1+\frac{c\varepsilon}{v^{2}}% -\sqrt{1+2\frac{c\varepsilon}{v^{2}}}\right)\right]\leq 2\exp\left(-\frac{% \varepsilon^{2}}{2\left(v^{2}+c\varepsilon\right)}\right)$

2) Let $\{X_{i}\}_{i=1}^{n}$ be a collection of independent, almost surely absolutely bounded (http://planetmath.org/AlmostSurelyBoundedRandomVariable) random variables, that is $\Pr\left\{\left|X_{i}\right|\leq M\right\}=1\text{ \ }\forall i$.
Then, for any $\varepsilon\geq 0$,

 $\Pr\left\{\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)>\varepsilon\right\}\leq% \exp\left[-\frac{9v^{2}}{M^{2}}\left(1+\frac{M\varepsilon}{3v^{2}}-\sqrt{1+2% \frac{M\varepsilon}{3v^{2}}}\right)\right]\leq\exp\left(-\frac{\varepsilon^{2}% }{2\left(v^{2}+\frac{M}{3}\varepsilon\right)}\right)$
 $\Pr\left\{\left|\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)\right|>\varepsilon% \right\}\leq 2\exp\left[-\frac{9v^{2}}{M^{2}}\left(1+\frac{M\varepsilon}{3v^{2% }}-\sqrt{1+2\frac{M\varepsilon}{3v^{2}}}\right)\right]\leq 2\exp\left(-\frac{% \varepsilon^{2}}{2\left(v^{2}+\frac{M}{3}\varepsilon\right)}\right)$
Title Bernstein inequalities BernsteinInequalities 2013-03-22 16:09:08 2013-03-22 16:09:08 Andrea Ambrosio (7332) Andrea Ambrosio (7332) 21 Andrea Ambrosio (7332) Theorem msc 60E15