Bernstein inequalities (probability theory)

In probability theory, the Bernstein inequalities are a family of inequalities proved by Sergei Bernstein in the 1920-s and 1930-s. In these inequalities, $X\_1,\; X\_2,\; X\_3,\; dots,\; X\_n$ are random variables with zero expected value: $mathbf\{E\}\; X\_i\; =\; 0$.
The goal is to show that (under different assumptions) the probability$mathbf\{P\}\; left\{\; sum\_\{j=1\}^n\; X\_j\; >\; t\; ight\}$is exponentially small.

ome of the inequalities

First (1.-3.) suppose that the variables $X\_j$ are independent(see [1] , [3] , [4] )

1. Assume that $|mathbf\{E\}\; X\_j^k|\; leq\; frac\{k!\}\{4!\}\; left(frac\{L\}\{5\}\; ight)^\{k-4\}$for $k\; =\; 4,\; 5,\; 6,\; dots$. Denote $A\_k\; =\; sum\; mathbf\{E\}\; X\_j^k$. Then

:

for

: .

2. Assume that $|mathbf\{E\}\; X\_j^k|\; leq\; frac\{mathbf\{E\}\; X\_j^2\}\{2\}\; L^\{k-2\}\; k!$for $k\; geq\; 2$. Then
for .

3. If $|X\_j|\; leq\; M$ almost surely, then
$mathbf\{P\}\; left\{\; sum\_\{j=1\}^n\; X\_j\; >\; t\; ight\}\; leq\; exp\; left\{\; -\; frac\{t^2/2\}\{sum\; mathbf\{E\}\; X\_j^2\; +\; Mt/3\; \}\; ight\}$ for any $t\; >\; 0$.

In [2] , Bernstein proved a generalisation to weakly dependent random variables. For example,2. can be extended in the following way:

4. Suppose $mathbf\{E\}\; left\{\; X\_\{j+1\}\; |\; X\_1,\; dots,\; X\_j\; ight\}\; =\; 0$;assume that $mathbf\{E\}\; left\{\; X\_j^2\; |\; X\_1,\; dots,\; X\_\{j-1\}\; ight\}\; leq\; R\_j\; mathbf\{E\}\; X\_j^2$ and
$mathbf\{E\}\; left\{\; X\_j^k\; |\; X\_1,\; dots,\; X\_\{j-1\}\; ight\}\; leq\; frac\{mathbf\{E\}\; left\{\; X\_j^2\; |\; X\_1,\; dots,\; X\_\{j-1\}\; ight\{2\}\; L^\{k-2\}\; k!$.

Then

Proofs

The proofs are based on an application of Chebyshev's inequality to the random variable$exp\; left\{\; lambda\; sum\_\{j=1\}^n\; X\_j\; ight\}$ , for a suitable choice of the parameter $lambda\; >\; 0$.

Related inequalities

The Bernstein inequalities were rediscovered several times in various forms. Thus, a particular case of 1.-3. is known as Hoeffding's inequality; see also Chernoff bound. A weaker form of 4. is known as Azuma'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] S.N.Bernstein, "On several modifications of Chebyshev's inequality",vol. 4, #22 (original publication: Doklady Akad. Nauk SSSR, 17, n. 6 (1937), 275-277)

[3] S.N.Bernstein, "Theory of Probability" (Russian), Moscow, 1927

[4] J.V.Uspensky, "Introduction to Mathematical Probability", 1937