Bernstein inequalities

1) Let ${\{X_i\}}_{i=1}^n$ be a collection of independent random variables satisfying the conditions:
a) $\forall i$, so that one can write ${\sum }_{i=1}^{n}E[X_i^2]=v^2$
b) $\exists c\in ℝ:{\sum }_{i=1}^{n}E[{\left|X_i\right|}^k]\le \frac{1}{2}k!v^2{c}^{k-2}$ for all integers $k\ge 3$

Then, for any $\epsilon \ge 0$,

$$\mathrm{Pr}\left\{\sum _{i=1}^n\left(X_i-E[X_i]\right)>\epsilon \right\}\le \exp \left[-\frac{v^2}{c^2}\left(1+\frac{c\epsilon }{v^2}-\sqrt{1+2\frac{c\epsilon }{v^2}}\right)\right]\le \exp \left(-\frac{{\epsilon }^2}{2\left(v^2+c\epsilon \right)}\right)$$

$$\mathrm{Pr}\left\{\left|\sum _{i=1}^n\left(X_i-E[X_i]\right)\right|>\epsilon \right\}\le 2\exp \left[-\frac{v^2}{c^2}\left(1+\frac{c\epsilon }{v^2}-\sqrt{1+2\frac{c\epsilon }{v^2}}\right)\right]\le 2\exp \left(-\frac{{\epsilon }^2}{2\left(v^2+c\epsilon \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 $\mathrm{Pr}\left\{\left|X_i\right|\le M\right\}=1\forall i$.
Then, for any $\epsilon \ge 0$,

$$\mathrm{Pr}\left\{\sum _{i=1}^n\left(X_i-E[X_i]\right)>\epsilon \right\}\le \exp \left[-\frac{9v^2}{M^2}\left(1+\frac{M\epsilon }{3v^2}-\sqrt{1+2\frac{M\epsilon }{3v^2}}\right)\right]\le \exp \left(-\frac{{\epsilon }^2}{2\left(v^2+\frac{M}{3}\epsilon \right)}\right)$$

$$\mathrm{Pr}\left\{\left|\sum _{i=1}^n\left(X_i-E[X_i]\right)\right|>\epsilon \right\}\le 2\exp \left[-\frac{9v^2}{M^2}\left(1+\frac{M\epsilon }{3v^2}-\sqrt{1+2\frac{M\epsilon }{3v^2}}\right)\right]\le 2\exp \left(-\frac{{\epsilon }^2}{2\left(v^2+\frac{M}{3}\epsilon \right)}\right)$$

Title	Bernstein inequalities
Canonical name	BernsteinInequalities
Date of creation	2013-03-22 16:09:08
Last modified on	2013-03-22 16:09:08
Owner	Andrea Ambrosio (7332)
Last modified by	Andrea Ambrosio (7332)
Numerical id	21
Author	Andrea Ambrosio (7332)
Entry type	Theorem
Classification	msc 60E15