Bernstein-Ungleichung (Stochastik)

Dieser Beweis folgt dem Ansatz aus "Support Vector Machines" (siehe Literatur).

Zur Vereinfachung definiere man ${\displaystyle \epsilon ={\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}}$

Nach ${\displaystyle {\mathcal {T}}}$ umgestellt, ergibt sich: ${\displaystyle {\mathcal {T}}={\frac {3n\epsilon ^{2}}{2\epsilon B+6\sigma ^{2}}}}$

Nun wird die Ungleichung gezeigt. Man wende die Markow-Ungleichung an mit ${\displaystyle X={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$ und ${\displaystyle f(\epsilon )=e^{t\epsilon n}}$ für ein ${\displaystyle \displaystyle {t>0}}$ (t wird später noch speziell gewählt):

${\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)}$

Da die Zufallsvariablen nach Voraussetzung unabhängig sind, können Produkt und Erwartungswert vertauscht werden. Aus der Exponentialfunktion bilde man eine unendliche Exponentialreihe. Diese ist durch die integrierbare Majorante ${\displaystyle \displaystyle {e^{tB}}}$ beschränkt. Also können Erwartungswert und Summe vertauscht werden. Mit ${\displaystyle X_{i}^{0}=1}$ und der Voraussetzung ${\displaystyle \displaystyle {{\textrm {E}}X_{i}=0}}$ folgt:

${\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)}$

Mit der Abschätzung ${\displaystyle {\textrm {E}}X_{i}^{k}\leqslant {\textrm {E}}X_{i}^{2}B^{k-2}\leqslant \sigma ^{2}B^{k-2}}$ folgt:

${\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}}$

Durch die Ungleichung ${\displaystyle (1+x)^{n}\leqslant \exp(nx)}$ für ${\displaystyle \displaystyle {x\geqslant 0}}$ erhält man mit ${\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)}$

Man setze ${\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]}$

Aus dem Lemma (oben) folgt mit ${\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}}}}$

Angenommen ${\displaystyle n,\,B}$ und ${\displaystyle \displaystyle {\sigma }}$ sind bekannt.

Wie groß ist die Wahrscheinlichkeit höchstens, dass der Mittelwert einen gegebenen Wert k übersteigt?

Löse ${\displaystyle k={\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}}$ nach ${\displaystyle {\mathcal {T}}}$ auf.

Die Wahrscheinlichkeit, dass der Mittelwert den Wert k übersteigt, ist höchstens ${\displaystyle e^{-{\mathcal {T}}}}$.

Weiterhin seien ${\displaystyle \displaystyle {B}}$ und ${\displaystyle \displaystyle {\sigma }}$ bekannt.

Es soll gelten: ${\displaystyle {\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant k\right]\leqslant 0,1}$

Berechne k mit Hilfe der Bernstein-Ungleichung.

${\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}}}$

Seien ${\displaystyle \displaystyle {B}}$ und ${\displaystyle \displaystyle {\sigma }}$ bekannt.

Wie viele Realisierungen werden mindestens benötigt, sodass für gegebene Werte ${\displaystyle k}$ und ${\displaystyle {\mathcal {T}}}$ gilt, dass

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

Man benötigt mindestens ${\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 }$ Realisierungen.