Bernstein-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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[Bearbeiten]

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)[Bearbeiten]

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 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[Bearbeiten]

Problem 1[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Literatur[Bearbeiten]

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