Bernstein-Ungleichung

Die Bernstein-Ungleichung ist eine Abschätzung aus der Wahrscheinlichkeitstheorie und wurde von Sergei Bernstein 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\epsilon B+6 \sigma ^2}$

Nun wird die Ungleichung gezeigt. Man wende man 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(t X_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$

Siehe auch

• Hoeffding-Ungleichung
• Tschebyschow-Ungleichung
• Markow-Ungleichung

Literatur

• Ingo Steinwart, Andreas Christmann, Support Vector Machines, Information Science and Statistics, Verlag: Springer, Berlin; Auflage: 1 (25. Juli 2008)