Beweisarchiv: Stochastik: Wahrscheinlichkeitstheorie: Bernstein-Ungleichung

Beweisarchiv: Stochastik

Statistik: Arithmetisches Mittel zweier Zahlen · Eindeutigkeit der Methode der kleinsten Fehlerquadrate

Wahrscheinlichkeitstheorie: Bernstein-Ungleichung · Satz von Moivre-Laplace · Approximationssatz von Stone-Weierstrass

Kombinatorik: Kombinatorische Eigenschaft des Binomialkoeffizienten

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}}}$.

${\begin{aligned}-t\epsilon n+{\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)&=-{\frac {\epsilon n}{B}}\ln \left(1+{\frac {\epsilon B}{\sigma ^{2}}}\right)+{\frac {n\sigma ^{2}}{B^{2}}}(1+{\frac {\epsilon B}{\sigma ^{2}}}-\ln(1+{\frac {\epsilon B}{\sigma ^{2}}})-1)\\&={\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)\\&={\frac {n\sigma ^{2}}{B^{2}}}\left(-x\ln \left(1+x\right)+x-\ln \left(1+x\right)\right)\\&={\frac {n\sigma ^{2}}{B^{2}}}\left(x-(1+x)\ln(1+x)\right)\\&\leqslant {\frac {n\sigma ^{2}}{B^{2}}}\left(-{\frac {3x^{2}}{2(x+3)}}\right)\\&=-{\frac {3n\epsilon ^{2}}{2\epsilon B+6\sigma ^{2}}}\end{aligned}}$

Man setze $\epsilon ={\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}$ wie in Schritt 1 definiert ein:

${\begin{aligned}-{\frac {3n\epsilon ^{2}}{2\epsilon B+6\sigma ^{2}}}&=-{\frac {({\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B)^{2}}{2B({\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B)+18n\sigma ^{2}}}\\&=-{\frac {18n\sigma ^{2}+{\mathcal {T}}B^{2}+2B{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B^{2}}{2B({\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B)+18n\sigma ^{2}}}{\mathcal {T}}\\&=-{\mathcal {T}}\end{aligned}}$

Schritt 5

Zum Schluss wird die Behauptung des Satzes gezeigt. Man wende zunächst Schritt 1 an.:

${\begin{aligned}{\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 {\frac {{\sqrt {18{\mathcal {T}}n\sigma ^{2}+{\mathcal {T}}^{2}B^{2}}}+{\mathcal {T}}B}{3n}}\right]\\&={\textrm {P}}\left[{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geqslant \epsilon \right]\\&={\textrm {P}}\left[t\sum _{i=1}^{n}X_{i}\geqslant t\epsilon n\right]\\&={\textrm {P}}\left[\exp \left(t\sum _{i=1}^{n}X_{i}\right)\geqslant \exp \left(t\epsilon n\right)\right]\end{aligned}}$

Nun wende man die Markow-Ungleichung an:

${\textrm {P}}\left[\exp \left(t\sum _{i=1}^{n}X_{i}\right)\geqslant \exp \left(t\epsilon n\right)\right]\leqslant \exp(-t\epsilon n){\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)$

Aus den Schritten 2 bis 4 folgt:

${\begin{aligned}\exp(-t\epsilon n){\textrm {E}}\left(\prod _{i=1}^{n}\exp(tX_{i})\right)&\leqslant \exp(-t\epsilon n)\prod _{i=1}^{n}\left(1+\sum _{k=2}^{\infty }{\frac {t^{k}}{k!}}{\textrm {E}}X_{i}^{k}\right)\\&\leqslant \exp(-t\epsilon n)\exp \left({\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)\\&=\exp \left(-t\epsilon n+{\frac {n\sigma ^{2}}{B^{2}}}(e^{tB}-tB-1)\right)\\&\leqslant e^{-{\mathcal {T}}}\end{aligned}}$

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

Wikipedia-Verweis

• Bernstein-Ungleichung