Bernstein inequalities (probability theory)

El directorio enciclopédico desde la Wikipedia.

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.

1 Some of the inequalities
2 Proofs
3 Related inequalities
4 References

[edit] Some 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}\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] 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.

[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

Página espejo de la Wikipedia

Directorio de Enlaces Directorio dmoz Directorio espejo dmoz Pedro Bernardo