Bernstein inequalities (probability theory)

Short description: Inequalities in 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 X1, ..., Xn 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 ε,

ℙ(|1n∑i=1nXi|>ε)≤2exp⁡(−nε22(1+ε3)).

Bernstein inequalities were proven 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. The martingale case of the Bernstein inequality is known as Freedman's inequality [5] and it's refinement is known as Hoeffding's inequality.[6]

## Contents

* 1 Some of the inequalities
* 2 Proofs
* 3 Generalizations
* 4 See also
* 5 References

## Some of the inequalities

1\. Let X1,…,Xn be independent zero-mean random variables. Suppose that |Xi|≤M almost surely, for all i. Then, for all positive t,

ℙ(∑i=1nXi≥t)≤exp⁡(−12t2∑i=1n𝔼[Xi2]+13Mt).

2\. Let X1,…,Xn be independent zero-mean random variables. Suppose that for some positive real L and every integer k≥2,

𝔼[|Xik|]≤12𝔼[Xi2]Lk−2k!

Then

ℙ(∑i=1nXi≥2t∑𝔼[Xi2])<exp⁡(−t2),for0≤t≤12L∑𝔼[Xj2].

3\. Let X1,…,Xn be independent zero-mean random variables. Suppose that

𝔼[|Xik|]≤k!4!(L5)k−4

for all integer k≥4. Denote

Ak=∑𝔼[Xik].

Then,

ℙ(|∑j=1nXj−A3t23A2|≥2A2t[1+A4t26A22])<2exp⁡(−t2),for0<t≤52A24L.

4\. Bernstein also proved generalizations of the inequalities above to weakly dependent random variables. For example, inequality (2) can be extended as follows. Let X1,…,Xn be possibly non-independent random variables. Suppose that for all integers i>0,

𝔼[Xi|X1,…,Xi−1]=0,𝔼[Xi2|X1,…,Xi−1]≤Ri𝔼[Xi2],𝔼[Xik|X1,…,Xi−1]≤12𝔼[Xi2|X1,…,Xi−1]Lk−2k!

Then

ℙ(∑i=1nXi≥2t∑i=1nRi𝔼[Xi2])<exp⁡(−t2),for0<t≤12L∑i=1nRi𝔼[Xi2].

More general results for martingales can be found in Fan et al. (2015).[7]

## Proofs

The proofs are based on an application of Markov's inequality to the random variable

exp⁡(λ∑j=1nXj),

for a suitable choice of the parameter λ>0.

## Generalizations

The Bernstein inequality can be generalized to Gaussian random matrices. Let G=gHAg+2Re⁡(gHa) be a scalar where A is a complex Hermitian matrix and a is complex vector of size N. The vector g∼𝒞𝒩(0,I) is a Gaussian vector of size N. Then for any σ≥0, we have

ℙ(G≤tr⁡(A)−2σ‖vec⁡(A)‖2+2‖a‖2−σs−(A))<exp⁡(−σ),

where vec is the vectorization operation and s−(A)=max⁡(−λmax(A),0) where λmax(A) is the largest eigenvalue of A. The proof is detailed here.[8] Another similar inequality is formulated as

ℙ(G≥tr⁡(A)+2σ‖vec⁡(A)‖2+2‖a‖2+σs+(A))<exp⁡(−σ),

where s+(A)=max⁡(λmax(A),0).

## See also

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

## References

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). "Об определенных модификациях неравенства Чебышева". 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. ↑ Freedman, D.A. (1975). "On tail probabilities for martingales". Ann. Probab. 3: 100–118.
6. ↑ Fan, X.; Grama, I.; Liu, Q. (2012). "Hoeffding’s inequality for supermartingales". Stochastic Process. Appl. 122: 3545–3559.
7. ↑ Fan, X.; Grama, I.; Liu, Q. (2015). "Exponential inequalities for martingales with applications". Electronic Journal of Probability (Electron. J. Probab. 20) 20: 1–22. doi:10.1214/EJP.v20-3496. http://projecteuclid.org/euclid.ejp/1465067107.
8. ↑ Ikhlef, Bechar (2009). "A Bernstein-type inequality for stochastic processes of quadratic forms of Gaussian variables". arXiv:0909.3595 [math.ST].

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

A modern translation of some of these results can also be found in Hazewinkel, Michiel, ed. (2001), "Bernstein inequality", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Bernstein_inequality

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Bernstein inequalities (probability theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Bernstein_inequalities_(probability_theory)&oldid=200468"