Bernstein Inequality (Stochastics)

The Bernstein inequality is an estimate from probability theory and was proven by Sergei Bernstein (1880–1968). It is an extension of the Hoeffding inequality , the estimation of which can be improved by adding an additional requirement to the variance of the random variables.

The inequality holds for arbitrarily distributed limited random variables with vanishing expectation and limited variance.

sentence

Be a probability space . Let and be positive real numbers and a natural number. be independently distributed random variables with and for all . ${\displaystyle (\Omega ,{\mathcal {A}},{\mathcal {P}})}$ ${\displaystyle B,{\mathcal {T}}}$ ${\displaystyle \displaystyle {\sigma }}$ ${\displaystyle \displaystyle {n}}$ ${\displaystyle X_{1},\ldots ,X_{n}:\Omega \rightarrow \mathbb {R} }$ ${\displaystyle {\textrm {E}}X_{i}=0,\Vert X_{i}\Vert _{\infty }\leqslant B}$ ${\displaystyle {\textrm {E}}(X_{i}^{2})\leqslant \sigma ^{2}}$ ${\displaystyle i=1,\ldots ,n}$

Then:

${\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\right]\leqslant e^{-{\mathcal {T}}}}$

lemma

The following applies to all : ${\displaystyle \displaystyle {x>-1}}$

${\displaystyle x-(1+x)\ln(1+x)\leqslant -{\frac {3x^{2}}{2(x+3)}}}$

A proof of the lemma and a more detailed proof of the theorem are in the evidence archive .

Proof (proposition)

This proof follows the approach from "Support Vector Machines" (see literature).

To simplify, define ${\displaystyle \epsilon ={\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}}$

After switching, it results: ${\displaystyle {\mathcal {T}}}$ ${\displaystyle {\mathcal {T}}={\frac {3n\epsilon }{2\epsilon B+6\sigma ^{2}}}}$

Now the inequality is shown. Apply the Markov inequality with and for a (t will be chosen specifically later): ${\displaystyle X={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$ ${\displaystyle f(\epsilon )=e^{t\epsilon n}}$ ${\displaystyle \displaystyle {t>0}}$

${\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\right]\leqslant {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant \epsilon \right]\leqslant e^{-t\epsilon n}{\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)}$

Since the random variables are independent according to the assumption, the product and the expected value can be exchanged. Form an infinite exponential series from the exponential function. This is limited by the integrable majorante . So expectation and sum can be swapped. With and the prerequisite follows: ${\displaystyle \displaystyle {e^{tB}}}$ ${\displaystyle X_{i}^{0}=1}$ ${\displaystyle \displaystyle {{\textrm {E}}X_{i}=0}}$

${\displaystyle e^{-t\epsilon n}{\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)=e^{-t\epsilon n}\prod _{i=1}^{n}{\textrm {E}}\left(\sum _{k=0}^{\infty }{\frac {t^{k}}{k!}}X_{i}^{k}\right)=e^{-t\epsilon n}\prod _{i=1}^{n}\left(\sum _{k=0}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)=e^{-t\epsilon n}\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)}$

With the estimate it follows: ${\displaystyle {\textrm {E}}X_{i}^{k}\leqslant {\textrm {E}}X_{i}^{2}B^{k-2}\leqslant \sigma ^{2}B^{k-2}}$

${\displaystyle e^{-t\epsilon n}\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)\leqslant e^{-t\epsilon n}\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}\sigma ^{2}B^{k-2}\right)=e^{-t\epsilon n}\left(1+{\frac {\sigma ^{2}}{B^{2}}}\sum _{k=2}^{\infty }{\frac {(tB)^{k}}{k!}}\right)^{n}}$

The inequality for gives with : ${\displaystyle (1+x)^{n}\leqslant \exp(nx)}$ ${\displaystyle \displaystyle {x\geqslant 0}}$ ${\displaystyle x={\frac {\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)}$

${\displaystyle e^{-t\epsilon n}\left(1+{\frac {\sigma ^{2}}{B^{2}}}\sum _{k=2}^{\infty }{\frac {(tB)^{k}}{k!}}\right)^{n}=e^{-t\epsilon n}\left(1+{\frac {\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)^{n}\leqslant e^{-t\epsilon n}\exp \left({\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)}$

Put : ${\displaystyle t={\frac {1}{B}}\ln(1+{\frac {\epsilon B}{\sigma }})}$

${\displaystyle e^{-t\epsilon n}\exp \left({\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)=\exp \left[{\frac {n\sigma ^{2}}{B^{2}}}\left(-{\frac {\epsilon B}{\sigma ^{2}}}\ln \left(1+{\frac {\epsilon B}{\sigma ^{2}}}\right)+{\frac {\epsilon B}{\sigma ^{2}}}-\ln \left(1+{\frac {\epsilon B}{\sigma ^{2}}}\right)\right)\right]}$

From the lemma (above) follows with . ${\displaystyle x={\frac {\epsilon B}{\sigma ^{2}}}}$

${\displaystyle \exp \left[{\frac {n\sigma ^{2}}{B^{2}}}\left(-{\frac {\epsilon B}{\sigma ^{2}}}\ln \left(1+{\frac {\epsilon B}{\sigma ^{2}}}\right)+{\frac {\epsilon B}{\sigma ^{2}}}-\ln \left(1+{\frac {\epsilon B}{\sigma ^{2}}}\right)\right)\right]\leqslant \exp \left[-{\frac {3n\epsilon ^{2}}{2\epsilon B+6\sigma ^{2}}}\right]=e^{-{\mathcal {T}}}}$

${\displaystyle \Rightarrow {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\right]\leqslant e^{-{\mathcal {T}}}}$

application

Problem 1

Adopted and known. ${\displaystyle n,\,B}$ ${\displaystyle \displaystyle {\sigma }}$

What is the maximum probability that the mean value exceeds a given value k?

Dissolve after . ${\displaystyle k={\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}}$ ${\displaystyle {\mathcal {T}}}$

The probability that the mean value exceeds the value k is at most . ${\displaystyle e^{-{\mathcal {T}}}}$

Problem 2

Would continue to be and known. ${\displaystyle \displaystyle {B}}$ ${\displaystyle \displaystyle {\sigma }}$

The following should apply: ${\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant k\right]\leqslant 0,1}$

Calculate k using Bernstein's inequality .

${\displaystyle e^{-{\mathcal {T}}}=0{,}1}$

${\displaystyle \Rightarrow {\mathcal {T}}=\ln 10}$

${\displaystyle \Rightarrow k={\sqrt {\frac {2\sigma ^{2}\ln 10}{n}}}+{\frac {2B\ln 10}{3n}}}$

Problem 3

Be and known. ${\displaystyle \displaystyle {B}}$ ${\displaystyle \displaystyle {\sigma }}$

How many realizations are required at least, so that for given values and , that ${\displaystyle k}$ ${\displaystyle {\mathcal {T}}}$

${\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant k\right]\leqslant e^{-{\mathcal {T}}}}$ ?

You need at least realizations. ${\displaystyle n^{*}=\min \lbrace n\in \mathbb {N} \vert k\geqslant {\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\rbrace }$

example

Consider a coin as a random variable. We denote the i th coin toss with . This applies to heads and tails . ${\displaystyle \displaystyle {X_{i}}}$ ${\displaystyle \displaystyle {X_{i}=-1}}$ ${\displaystyle \displaystyle {X_{i}=1}}$

What is the probability that the mean value will exceed the value after throws ? ${\displaystyle \displaystyle {n}}$ ${\displaystyle {\frac {16}{75}}}$

Since the probability for heads and tails is 50% each, the expectation value is 0. Since the random variables can only take the values ​​−1 and 1, a choice can be made. ${\displaystyle \displaystyle {B=1}}$

${\displaystyle X_{i}^{2}=1\Rightarrow {\textrm {E}}X_{i}^{2}=1}$. So you can choose . ${\displaystyle \displaystyle {\sigma =1}}$

Now choose one more time . Where is the number of coin flips. According to the Bernstein inequality: ${\displaystyle \displaystyle {{\mathcal {T}}={\frac {n}{50}}}}$ ${\displaystyle \displaystyle {n}}$

${\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\frac {16}{75}}\right]\leqslant e^{-{\frac {n}{50}}}}$

So, for example, with 50 throws:

${\displaystyle {\textrm {P}}\left[{\frac {1}{50}}\sum _{i=1}^{50}X_{i}\geqslant {\frac {16}{75}}\right]\leqslant {\frac {1}{e}}}$

For 50 throws to exceed the mean , you would have to throw your head 31 times. ${\displaystyle {\frac {16}{75}}}$

${\displaystyle {\frac {31\cdot 1+19\cdot (-1)}{50}}={\frac {12}{50}}={\frac {18}{75}}\geqslant {\frac {16}{75}}}$

That is, the probability of getting 31 heads in 50 tosses is less than ${\displaystyle {\frac {1}{e}}\approx 0{,}367879441}$

See also

• Chebyshev inequality

literature

• Ingo Steinwart, Andreas Christmann: Support Vector Machines . Information Science and Statistics. 1st edition. Springer, Berlin 2008

Web links

Wikibooks: Proof of the Bernstein Inequality