# Bernstein-Ungleichung (Stochastik)

Die Bernstein-Ungleichung ist eine Abschätzung aus der Wahrscheinlichkeitstheorie und wurde von Sergei Bernstein (1880–1968) bewiesen. Sie ist eine Erweiterung der Hoeffding-Ungleichung, deren Abschätzung durch eine zusätzliche Voraussetzung an die Varianz der Zufallsvariablen verbessert werden kann.
Die Ungleichung gilt für beliebig verteilte beschränkte Zufallsvariablen mit verschwindendem Erwartungswert und beschränkter Varianz.

## Satz

Sei $(\Omega ,{\mathcal {A}},{\mathcal {P}})$ ein Wahrscheinlichkeitsraum. Seien $B,{\mathcal {T}}$ und $\displaystyle {\sigma }$ positive reelle Zahlen und $\displaystyle {n}$ eine natürliche Zahl. $X_{1},\ldots ,X_{n}:\Omega \rightarrow \mathbb {R}$ seien unabhängig verteilte Zufallsvariablen mit ${\textrm {E}}X_{i}=0,\Vert X_{i}\Vert _{\infty }\leqslant B$ und ${\textrm {E}}(X_{i}^{2})\leqslant \sigma ^{2}$ für alle $i=1,\ldots ,n$.
Dann gilt:
    ${\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

Für alle $\displaystyle {x>-1}$ gilt:
    $x-(1+x)\ln(1+x)\leqslant -{\frac {3x^{2}}{2(x+3)}}$
Ein Beweis des Lemmas und ein ausführlicherer Beweis des Satzes befinden sich im Beweisarchiv.

### Beweis (Satz)

Dieser Beweis folgt dem Ansatz aus "Support Vector Machines" (siehe Literatur).
Zur Vereinfachung definiere man $\epsilon ={\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}$
Nach ${\mathcal {T}}$ umgestellt, ergibt sich: ${\mathcal {T}}={\frac {3n\epsilon ^{2}}{2\epsilon B+6\sigma ^{2}}}$
Nun wird die Ungleichung gezeigt. Man wende die Markow-Ungleichung an mit $X={\frac {1}{n}}\sum _{i=1}^{n}X_{i}$ und $f(\epsilon )=e^{t\epsilon n}$ für ein $\displaystyle {t>0}$ (t wird später noch speziell gewählt):
    ${\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 {e^{tB}}$ beschränkt. Also können Erwartungswert und Summe vertauscht werden. Mit $X_{i}^{0}=1$ und der Voraussetzung $\displaystyle {{\textrm {E}}X_{i}=0}$ folgt:
    $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 ${\textrm {E}}X_{i}^{k}\leqslant {\textrm {E}}X_{i}^{2}B^{k-2}\leqslant \sigma ^{2}B^{k-2}$ folgt:
    $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 $(1+x)^{n}\leqslant \exp(nx)$ für $\displaystyle {x\geqslant 0}$ erhält man mit $x={\frac {\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)$:
    $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 $t={\frac {1}{B}}\ln(1+{\frac {\epsilon B}{\sigma }})$:
    $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 $x={\frac {\epsilon B}{\sigma ^{2}}}$.
    $\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}}}$
    $\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}}}$

## Anwendung
### Problem 1

Angenommen $n,\,B$ und $\displaystyle {\sigma }$ sind bekannt.
Wie groß ist die Wahrscheinlichkeit höchstens, dass der Mittelwert einen gegebenen Wert k übersteigt?
Löse $k={\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}$ nach ${\mathcal {T}}$ auf.
Die Wahrscheinlichkeit, dass der Mittelwert den Wert k übersteigt, ist höchstens $e^{-{\mathcal {T}}}$.

### Problem 2

Weiterhin seien $\displaystyle {B}$ und $\displaystyle {\sigma }$ bekannt.
Es soll gelten: ${\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.
    $e^{-{\mathcal {T}}}=0{,}1$
$\Rightarrow {\mathcal {T}}=\ln 10$
$\Rightarrow k={\sqrt {\frac {2\sigma ^{2}\ln 10}{n}}}+{\frac {2B\ln 10}{3n}}$

### Problem 3

Seien $\displaystyle {B}$ und $\displaystyle {\sigma }$ bekannt.
Wie viele Realisierungen werden mindestens benötigt, sodass für gegebene Werte $k$ und ${\mathcal {T}}$ gilt, dass
    ${\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant k\right]\leqslant e^{-{\mathcal {T}}}$ ?
Man benötigt mindestens $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.

## Beispiel

Als Zufallsvariable betrachte man eine Münze. Den i-ten Münzwurf bezeichnen wir mit $\displaystyle {X_{i}}$. Dabei gelte bei Kopf $\displaystyle {X_{i}=-1}$ und bei Zahl $\displaystyle {X_{i}=1}$.
Wie groß ist die Wahrscheinlichkeit, dass der Mittelwert nach $\displaystyle {n}$ Würfen den Wert ${\frac {16}{75}}$ übersteigt?
Da die Wahrscheinlichkeit für Kopf und Zahl jeweils 50 % sind, ist der Erwartungswert 0. Da die Zufallsvariablen nur die Werte −1 und 1 annehmen können, kann $\displaystyle {B=1}$ gewählt werden.
$X_{i}^{2}=1\Rightarrow {\textrm {E}}X_{i}^{2}=1$. Also kann $\displaystyle {\sigma =1}$ gewählt werden.
Nun wähle noch $\displaystyle {{\mathcal {T}}={\frac {n}{50}}}$. Dabei ist $\displaystyle {n}$ die Anzahl der Münzwürfe. Nach der Bernstein-Ungleichung gilt dann:
    ${\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant {\frac {16}{75}}\right]\leqslant e^{-{\frac {n}{50}}}$
Also gilt zum Beispiel bei 50 Würfen:
    ${\textrm {P}}\left[{\frac {1}{50}}\sum _{i=1}^{50}X_{i}\geqslant {\frac {16}{75}}\right]\leqslant {\frac {1}{e}}$
Damit der Mittelwert ${\frac {16}{75}}$ übersteigt, müsste man bei 50 Würfen 31-mal Kopf werfen.
    ${\frac {31\cdot 1+19\cdot (-1)}{50}}={\frac {12}{50}}={\frac {18}{75}}\geqslant {\frac {16}{75}}$
Das heißt, die Wahrscheinlichkeit, in 50 Würfen 31 Kopf zu erhalten, ist kleiner als ${\frac {1}{e}}\approx 0{,}367879441$