Bernstein inequalities (probability theory)

From Wikipedia, the free encyclopedia

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 \right\} is exponentially small.

[edit] Some of the inequalities

First (1.-3.) suppose that the variables Xj are independent (see [1], [3], [4])

1. Assume that |\mathbf{E} X_j^k| \leq \frac{k!}{4!} \left(\frac{L}{5}\right)^{k-4} for k = 4, 5, 6, \dots. Denote A_k = \sum \mathbf{E} X_j^k . Then

\mathbf{P} \left\{ |\sum_{j=1}^n X_j - \frac{A_3 t^2}{3A_2}| \geq \sqrt{2A_2} \, t \left[ 1 + \frac{A_4 t^2}{6 A_2^2} \right] \right\} < 2 \exp \left\{ - t^2\right\}

for

0 < t \leq \frac{5 \sqrt{2A_2}}{4L} .

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
\mathbf{P} \left\{ \sum_{j=1}^n X_j \geq 2 t \sqrt{\sum \mathbf{E} X_j^2} \right\} < \exp \left\{ - t^2\right\} for 0 < t \leq \frac{\sqrt{\sum X_j^2}}{2L} .

3. If |X_j| \leq M almost surely, then
\mathbf{P} \left\{ \sum_{j=1}^n X_j > t \right\} \leq \exp \left\{ - \frac{t^2/2}{\sum \mathbf{E} X_j^2 + Mt/3 } \right\} 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 \right\} = 0 ; assume that \mathbf{E} \left\{ X_j^2 | X_1, \dots, X_{j-1} \right\} \leq R_j \mathbf{E} X_j^2 and
\mathbf{E} \left\{ X_j^k | X_1, \dots, X_{j-1} \right\} \leq \frac{\mathbf{E} \left\{ X_j^2 | X_1, \dots, X_{j-1} \right\}}{2} L^{k-2} k! .
Then \mathbf{P} \left\{ \sum_{j=1}^n X_j \geq 2 t \sqrt{\sum_{j=1}^n R_j \mathbf{E} X_j^2} \right\} < \exp(-t^2) \quad \text{for} \quad 0 < t \leq \frac{\sqrt{\sum_{j=1}^n R_j \mathbf{E} X_j^2}}{2L}.

[edit] 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 \right\} , for a suitable choice of the parameter λ > 0.

[edit] 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

Languages