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\geq 2}$,

${\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\geq 4.}$ 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. Let ${\displaystyle X_{1},\ldots ,X_{n}}$ be possibly non-independent random variables. Suppose that for all integers ${\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).[7]

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}$.

The Bernstein inequality can be generalized to Gaussian random matrices. Let ${\displaystyle G=g^{H}Ag+2\operatorname {Re} (g^{H}a)}$ be a scalar where ${\displaystyle A}$ is a complex Hermitian matrix and ${\displaystyle a}$ is complex vector of size ${\displaystyle N}$. The vector ${\displaystyle g\sim {\mathcal {CN}}(0,I)}$ is a Gaussian vector of size ${\displaystyle N}$. Then for any ${\displaystyle \sigma \geq 0}$, we have

${\displaystyle \mathbb {P} \left(G\leq \operatorname {tr} (A)-{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}-\sigma s^{-}(A)\right)<\exp(-\sigma ),}$

where ${\displaystyle \operatorname {vec} }$ is the vectorization operation and ${\displaystyle s^{-}(A)=\max(-\lambda _{\max }(A),0)}$ where ${\displaystyle \lambda _{\max }(A)}$ is the largest eigenvalue of ${\displaystyle A}$. The proof is detailed here.[8] Another similar inequality is formulated as

${\displaystyle \mathbb {P} \left(G\geq \operatorname {tr} (A)+{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}+\sigma s^{+}(A)\right)<\exp(-\sigma ),}$

where ${\displaystyle s^{+}(A)=\max(\lambda _{\max }(A),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