Bernstein inequalities (probability theory)

In probability theory, Bernstein inequalities give bounds on the probability that the sum of random variables deviates from its mean. In the simplest case, let X₁, ..., X_n be independent Bernoulli random variables taking values +1 and −1 with probability 1/2 (this distribution is also known as the Rademacher distribution), then for every positive ${\displaystyle \varepsilon }$,

${\displaystyle \mathbb {P} \left(\left|{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\right|>\varepsilon \right)\leq 2\exp \left(-{\frac {n\varepsilon ^{2}}{2(1+{\frac {\varepsilon }{3}})}}\right).}$

Bernstein inequalities were proved and published by Sergei Bernstein in the 1920s and 1930s.[1][2][3][4] Later, these inequalities were rediscovered several times in various forms. Thus, special cases of the Bernstein inequalities are also known as the Chernoff bound, Hoeffding's inequality and Azuma's inequality.

Some of the inequalities

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]

Proofs

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

See also

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

References

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

1. S.N.Bernstein, "On a modification of Chebyshev’s inequality and of the error formula of Laplace" vol. 4, #5 (original publication: Ann. Sci. Inst. Sav. Ukraine, Sect. Math. 1, 1924)
2. Bernstein, S. N. (1937). "Об определенных модификациях неравенства Чебышева" [On certain modifications of Chebyshev's inequality]. Doklady Akademii Nauk SSSR. 17 (6): 275–277.
3. S.N.Bernstein, "Theory of Probability" (Russian), Moscow, 1927
4. J.V.Uspensky, "Introduction to Mathematical Probability", McGraw-Hill Book Company, 1937
5. Fan, X.; Grama, I.; Liu, Q. (2015). "Exponential inequalities for martingales with applications". Electron. J. Probab. 20: 1–22. arXiv:1311.6273. doi:10.1214/EJP.v20-3496. Cite journal requires |journal= (help)

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