Blue Monday (date)

2014-01-21T04:57:55Z

202.70.36.50: /* Happiest day */

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''1, ..., ''X''''n'' be independent [[Bernoulli trial|Bernoulli random variables]] taking values +1 and −1 with probability 1/2, then for every positive <math>\varepsilon</math>,

:<math> \mathbf{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).</math>

'''Bernstein inequalities''' were proved and published by [[Sergei Bernstein]] in the 1920s and 1930s.<ref>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)</ref><ref>{{cite journal |last=Bernstein |first=S. N. |year=1937 |title=На определенных модификациях неравенства Чебишева |trans_title=On certain modifications of Chebyshev's inequality |journal=[[Doklady Akademii Nauk SSSR]] |volume=17 |issue=6 |pages=275–277}}</ref><ref>S.N.Bernstein, "Theory of Probability" (Russian), Moscow, 1927</ref><ref>J.V.Uspensky, "Introduction to Mathematical Probability", McGraw-Hill Book Company, 1937</ref> 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 ''X''1, ..., ''X''''n'' be independent zero-mean random variables. Suppose that |''X'' ''i''| ≤ ''M'' almost surely, for all ''i''. Then, for all positive ''t'',

:<math>\mathbf{P} \left (\sum_{i=1}^n X_i > t \right ) \leq \exp \left ( -\frac{\tfrac{1}{2} t^2}{\sum \mathbf{E} \left[X_j^2 \right ]+\tfrac{1}{3} Mt} \right ).</math>

2. Let ''X''1, ..., ''X''''n'' be independent random variables. Suppose that for some positive real '''L''' and every integer ''k'' > 1,

:<math> \mathbf{E} \left [|X_i^k|\right ] \leq \tfrac{1}{2} \mathbf{E} \left[X_i^2\right] L^{k-2} k!</math>

Then

:<math>\mathbf{P} \left ( \sum_{i=1}^n X_i \geq 2 t \sqrt{\sum \mathbf{E} \left [ X_i^2 \right ]} \right ) < \exp (-t^2), \qquad \text{for } 0 < t \leq \tfrac{1}{2L}\sqrt{\sum \mathbf{E} \left[X_j^2\right ]}. </math>

3. Let ''X''1, ..., ''X''''n'' be independent random variables. Suppose that

:<math> \mathbf{E} \left[|X_i^k|\right ] \leq \frac{k!}{4!} \left(\frac{L}{5}\right)^{k-4}</math>

for all integer ''k'' > 3. Denote

:<math> A_k = \sum \mathbf{E} \left [ X_i^k\right ].</math>

Then,

: <math> \mathbf{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}{6 A_2^2} \right] \right ) < 2 \exp (- t^2), \qquad \text{for } 0 < t \leq \frac{5 \sqrt{2A_2}}{4L}. </math>

4. Bernstein also proved generalizations of the inequalities above to weakly dependent random variables. For example, inequality (2) can be extended as follows. Let ''X''1, ..., ''X''''n'' be possibly non-independent random variables. Suppose that for all integer ''i'' > 0,

:<math>\begin{align}
\mathbf{E} \left [ X_i | X_1, \dots, X_{i-1} \right ] &= 0, \\
\mathbf{E} \left [ X_i^2 | X_1, \dots, X_{i-1} \right ] &\leq R_i \mathbf{E} \left [ X_i^2 \right ], \\
\mathbf{E} \left [ X_i^k | X_1, \dots, X_{i-1} \right ] &\leq \tfrac{1}{2} \mathbf{E} \left[ X_i^2 | X_1, \dots, X_{i-1} \right ] L^{k-2} k!
\end{align}</math>

Then

:<math> \mathbf{P} \left( \sum_{i=1}^n X_i \geq 2 t \sqrt{\sum_{i=1}^n R_i \mathbf{E}\left [ X_i^2 \right ]} \right) < \exp(-t^2), \qquad \text{for } 0 < t \leq \tfrac{1}{2L} \sqrt{\sum_{i=1}^n R_i \mathbf{E} \left [X_i^2 \right ]}. </math>
More general results for martingales can be found in Fan et al. (2012).<ref name=fan>{{cite journal |title=Hoeffding's inequality for supermartingales| first1=X. |last1=Fan| first2=I. |last2=Grama | publisher=Stochastic Process. Appl. 122| year=2012| pages=3545–3559| url=http://www.sciencedirect.com/science/article/pii/S0304414912001378 | doi=10.1016/j.spa.2012.06.009}}</ref>

==Proofs==

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

:<math> \exp \left ( \lambda \sum_{j=1}^n X_j \right ),</math>

for a suitable choice of the parameter λ > 0.

==See also==
* [[McDiarmid's inequality]]
* [[Markov inequality]]
* [[Hoeffding's inequality]]
* [[Chebyshev's inequality]]
* [[Azuma's inequality]]
* [[Bennett's inequality]]

==References==

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

{{reflist}}

A modern translation of some of these results can also be found in {{SpringerEOM| title=Bernstein inequality | id=Bernstein_inequality | oldid=15217 | first=A.V. | last=Prokhorov | first2=N.P. | last2=Korneichuk | first3=V.P. | last3=Motornyi }}

{{DEFAULTSORT:Bernstein Inequalities (Probability Theory)}}
[[Category:Probability theory]]
[[Category:Probabilistic inequalities]]

formulasearchengine - User contributions [en]

Blue Monday (date)