Beweisarchiv: Stochastik: Wahrscheinlichkeitstheorie: Bernstein-Ungleichung

Satz (Bernstein-Ungleichung)

Sei $(\Omega ,{\mathcal {A}},{\mathcal {P}})$ ein Wahrscheinlichkeitsraum. Seien $B,{\mathcal {T}}$ und $\sigma$ positive reelle Zahlen und $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,...,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}}}

Für den Beweis benötigt man folgendes

Lemma

Für alle $x>-1$ gilt:

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

Beweis (Lemma)

Man definiere die Linke Seite der Ungleichung als $\displaystyle {f(x)}$ , die rechte Seite als $\displaystyle {g(x)}$ und leite jeweils zweimal ab.

\displaystyle {f(x)=x-(1+x)\ln(1+x)}

\displaystyle {f'(x)=-\ln(1+x)}

f''(x)=-{\frac {1}{1+x}}

g(x)=-{\frac {3x^{2}}{2(x+3)}}

g'(x)=-{\frac {3x^{2}+18x}{2(x+3)^{2}}}

g''(x)=-{\frac {27}{(x+3)^{3}}}

Es gilt: $\displaystyle {f(0)=f'(0)=g(0)=g'(0)=0}$

Für $\displaystyle {x>-1}$ gilt:

{\begin{aligned}{\frac {1}{g''(x)}}&=-{\frac {(x+3)^{3}}{27}}\\&=-{\frac {1}{27}}(x^{2}(x+9)+27x+27)\\&<-{\frac {1}{27}}(27x+27)\\&=-1-x\\&={\frac {1}{f''(x)}}\end{aligned}}

\Rightarrow f''(x)<g''(x)

Für $\displaystyle {x>0}$ gilt:

f(x)=\int _{0}^{x}\int _{0}^{t}f''(s)dsdt<\int _{0}^{x}\int _{0}^{t}g''(s)dsdt=g(x)

Das gilt auch analog für $\displaystyle {x<0}$ mit vertauschten Integralgrenzen.

Damit ist das Lemma gezeigt.

Beweis (Satz)

Der Beweis wird in fünf Schritte unterteilt:

Schritt 1

Es wird zunächst gezeigt:

{\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}\geqslant {\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}

Allgemein gilt für $a>0$ , $b>0$ : $({\sqrt {a}}+{\sqrt {b}})^{2}=a+2{\sqrt {ab}}+b\geqslant a+b$

Zieht man auf beiden Seiten die Wurzel, dann folgt: ${\sqrt {a}}+{\sqrt {b}}\geqslant {\sqrt {a+b}}$

Mit $a=18{\mathcal {T}}n\sigma ^{2}$ und $b=({\mathcal {T}}B)^{2}$ folgt die Ungleichung. Zur Vereinfachung wird die rechte Seite durch $\displaystyle {\epsilon }$ definiert.

{\begin{aligned}{\sqrt {\frac {2\sigma ^{2}{\mathcal {T}}}{n}}}+{\frac {2B{\mathcal {T}}}{3n}}&={\frac {\sqrt {18{\mathcal {T}}n\sigma ^{2}}}{3n}}+{\frac {B{\mathcal {T}}+B{\mathcal {T}}}{3n}}\\&={\frac {{\sqrt {a}}+{\sqrt {b}}+B{\mathcal {T}}}{3n}}\\&\geqslant {\frac {{\sqrt {a+b}}+B{\mathcal {T}}}{3n}}\\&={\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}\\&=:\epsilon \end{aligned}}

Schritt 2

Zu zeigen: $\forall _{t>0}{\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)=\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)$

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

{\begin{aligned}{\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)&=\prod _{i=1}^{n}{\textrm {E}}\left(\exp(tX_{i})\right)\\&=\prod _{i=1}^{n}{\textrm {E}}\left(\sum _{k=0}^{\infty }{\frac {t^{k}}{k!}}X_{i}^{k}\right)\\&=\prod _{i=1}^{n}\left(\sum _{k=0}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)\\&=\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)\end{aligned}}

Schritt 3

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

Sei $\displaystyle {F_{i}}$ die Verteilungsfunktion von $\displaystyle {X_{i}}$ .

Nach Voraussetzung gilt: $\Vert X_{i}\Vert _{\infty }\leqslant B$

\Rightarrow F_{i}(x)=0=const.

für

x<-B

bzw.

\displaystyle {F_{i}(x)=1=const.}

für

x>B

\Rightarrow dF_{i}(x)=0

für alle

\displaystyle {x<-B}

und

\displaystyle {x>B}

{\begin{aligned}\Rightarrow {\textrm {E}}X_{i}^{k}&=\int _{\mathbb {R} }x^{k}dF_{i}(x)\\&\leqslant \int _{\mathbb {R} }\vert x\vert ^{k}dF_{i}(x)\\&\leqslant \int _{\mathbb {R} }\vert x\vert ^{2}B^{k-2}dF_{i}(x)\\&=B^{k-2}\int _{\mathbb {R} }x^{2}dF_{i}(x)\\&=B^{k-2}{\textrm {E}}X_{i}^{2}\\&\leqslant B^{k-2}\sigma ^{2}\end{aligned}}

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

Diese Faktoren sind unabhängig von $i$ . Mit $e^{tB}-tB-1=\sum _{k=0}^{\infty }{\frac {(tB)^{k}}{k!}}-tB-1=\sum _{k=2}^{\infty }{\frac {(tB)^{k}}{k!}}$ erhält man:

{\begin{aligned}\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}\sigma ^{2}B^{k-2}\right)&=\left(1+{\frac {\sigma ^{2}}{B^{2}}}\sum _{k=2}^{\infty }{\frac {(tB)^{k}}{k!}}\right)^{n}\\&=\left(1+{\frac {\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)^{n}\end{aligned}}

Aus $1+x=1+\int _{0}^{x}dt\leqslant 1+\int _{0}^{x}e^{t}dt=e^{x}$ folgt, falls $x$ positiv ist $(1+x)^{n}\leqslant e^{nx}$ und man erhält mit $x={\frac {\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)$

\left(1+{\frac {\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)^{n}\leqslant \exp \left({\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)

Damit ist Schritt 3 gezeigt.

Schritt 4

Zu zeigen: $-t\epsilon n+{\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\leqslant -{\mathcal {T}}$

Man setze $t={\frac {1}{B}}\ln(1+{\frac {\epsilon B}{\sigma ^{2}}})$ . Um das Lemma (oben) anzuwenden, setze man dann $x={\frac {\epsilon B}{\sigma ^{2}}}$ .