Bernstein inequalities (probability theory)

1. Let ${\displaystyle X_{1},\ldots ,X_{n}}$ be independent zero-mean random variables. Suppose that ${\displaystyle |X_{i}|\leq M}$ almost surely, for all ${\displaystyle i.}$ Then, for all positive ${\displaystyle t}$,

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq t\right)\leq \exp \left(-{\frac {{\tfrac {1}{2}}t^{2}}{\sum _{i=1}^{n}\mathbb {E} \left[X_{i}^{2}\right]+{\tfrac {1}{3}}Mt}}\right).}$

2. Let ${\displaystyle X_{1},\ldots ,X_{n}}$ be independent zero-mean random variables. Suppose that for some positive real ${\displaystyle L}$ and every integer ${\displaystyle k>1}$,

${\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {1}{2}}\mathbb {E} \left[X_{i}^{2}\right]L^{k-2}k!}$

Then

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum \mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0\leq t\leq {\frac {1}{2L}}{\sqrt {\sum \mathbb {E} \left[X_{j}^{2}\right]}}.}$

3. Let ${\displaystyle X_{1},\ldots ,X_{n}}$ be independent zero-mean random variables. Suppose that

${\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {k!}{4!}}\left({\frac {L}{5}}\right)^{k-4}}$

for all integer ${\displaystyle k>3.}$ Denote

${\displaystyle A_{k}=\sum \mathbb {E} \left[X_{i}^{k}\right].}$

Then,

${\displaystyle \mathbb {P} \left(\left|\sum _{j=1}^{n}X_{j}-{\frac {A_{3}t^{2}}{3A_{2}}}\right|\geq {\sqrt {2A_{2}}}\,t\left[1+{\frac {A_{4}t^{2}}{6A_{2}^{2}}}\right]\right)<2\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {5{\sqrt {2A_{2}}}}{4L}}.}$

4. Bernstein also proved generalizations of the inequalities above to weakly dependent random variables. For example, inequality (2) can be extended as follows. ${\displaystyle X_{1},\ldots ,X_{n}}$ be possibly non-independent random variables. Suppose that for all integer ${\displaystyle i>0}$,

${\displaystyle {\begin{aligned}\mathbb {E} \left.\left[X_{i}\right|X_{1},\ldots ,X_{i-1}\right]&=0,\\\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]&\leq R_{i}\mathbb {E} \left[X_{i}^{2}\right],\\\mathbb {E} \left.\left[X_{i}^{k}\right|X_{1},\ldots ,X_{i-1}\right]&\leq {\tfrac {1}{2}}\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]L^{k-2}k!\end{aligned}}}$

Then

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {1}{2L}}{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}.}$

More general results for martingales can be found in Fan et al. (2015).[5]

The proofs are based on an application of Markov's inequality to the random variable

${\displaystyle \exp \left(\lambda \sum _{j=1}^{n}X_{j}\right),}$

for a suitable choice of the parameter ${\displaystyle \lambda >0}$.

• Concentration inequality - a summary of tail-bounds on random variables.
• Hoeffding's inequality

(according to: S.N.Bernstein, Collected Works, Nauka, 1964)

A modern translation of some of these results can also be found in Prokhorov, A.V.; Korneichuk, N.P.; Motornyi, V.P. (2001) [1994], "Bernstein inequality", Encyclopedia of Mathematics, EMS Press