Beweisarchiv: Stochastik: Wahrscheinlichkeitstheorie: Bernstein-Ungleichung

Satz (Bernstein-Ungleichung)

Sei $(\mathrm{\Omega },𝒜,𝒫)$ ein Wahrscheinlichkeitsraum. Seien $B,𝒯$ und $\sigma$ positive reelle Zahlen und $n$ eine natürliche Zahl. $X_1,\dots ,X_n:\mathrm{\Omega }\to ℝ$ seien unabhängig verteilte Zufallsvariablen mit $\text{E}{X}_i=0,\Vert X_i{\Vert }_{\mathrm{\infty }}⩽B$ und $\text{E}(X_i^2)⩽{\sigma }^2$ für alle $i=1,...,n$.

Dann gilt:

$\text{P}[\frac{1}{n}\sum _{i=1}^n{X}_i⩾\sqrt{\frac{2{\sigma }^2𝒯}{n}}+\frac{2B𝒯}{3n}]⩽e^{-𝒯}$

Für den Beweis benötigt man folgendes

Lemma

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

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

Beweis (Lemma)

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

$f(x)=x-(1+x)\ln (1+x)$

$f^{\prime }(x)=-\ln (1+x)$

$f^{″}(x)=-\frac{1}{1+x}$

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

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

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

Es gilt: $f(0)=f^{\prime }(0)=g(0)=g^{\prime }(0)=0$

Für $x>-1$ gilt:

$\begin{array}{cc}\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{array}$

$\Rightarrow f^{″}(x)<g^{″}(x)$

Für $x>0$ gilt:

$f(x)=\underset{0}{\overset{x}{\int }}\underset{0}{\overset{t}{\int }}{f}^{″}(s)dsdt<\underset{0}{\overset{x}{\int }}\underset{0}{\overset{t}{\int }}{g}^{″}(s)dsdt=g(x)$

Das gilt auch analog für $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𝒯}{n}}+\frac{2B𝒯}{3n}⩾\frac{\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B}{3n}$

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

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

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

$\begin{array}{cc}\sqrt{\frac{2{\sigma }^2𝒯}{n}}+\frac{2B𝒯}{3n}& =\frac{\sqrt{18𝒯n{\sigma }^2}}{3n}+\frac{B𝒯+B𝒯}{3n}\\ & =\frac{\sqrt{a}+\sqrt{b}+B𝒯}{3n}\\ & ⩾\frac{\sqrt{a+b}+B𝒯}{3n}\\ & =\frac{\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B}{3n}\\ & =:ϵ\end{array}$

Schritt 2

Zu zeigen: ${\mathrm{\forall }}_{t>0}\text{E}(\prod _{i=1}^n\exp (t{X}_i))=\prod _{i=1}^n(1+\sum _{k=2}^{\mathrm{\infty }}\frac{t^k}{k!}\text{E}{X}_i^k)$

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

$\begin{array}{cc}\text{E}(\prod _{i=1}^n\exp (t{X}_i))& =\prod _{i=1}^n\text{E}(\exp (t{X}_i))\\ & =\prod _{i=1}^n\text{E}\left(\sum _{k=0}^{\mathrm{\infty }}\frac{t^k}{k!}{X}_i^k\right)\\ & =\prod _{i=1}^n\left(\sum _{k=0}^{\mathrm{\infty }}\frac{t^k}{k!}\text{E}{X}_i^k\right)\\ & =\prod _{i=1}^n(1+\sum _{k=2}^{\mathrm{\infty }}\frac{t^k}{k!}\text{E}{X}_i^k)\end{array}$

Schritt 3

Zu zeigen: $\prod _{i=1}^n(1+\sum _{k=2}^{\mathrm{\infty }}\frac{t^k}{k!}\text{E}{X}_i^k)⩽\exp (\frac{n{\sigma }^2}{B^2}(e^{tB}-tB-1))$

Sei $F_i$ die Verteilungsfunktion von $X_i$.

Nach Voraussetzung gilt: $\Vert X_i{\Vert }_{\mathrm{\infty }}⩽B$

$\Rightarrow F_i(x)=0=const.$ für $x<-B$ bzw. $F_i(x)=1=const.$ für $x>B$

$\Rightarrow d{F}_i(x)=0$ für alle $x<-B$ und $x>B$

$\begin{array}{cc}\Rightarrow \text{E}{X}_i^k& =\underset{ℝ}{\int }{x}^{k}d{F}_i(x)\\ & ⩽\underset{ℝ}{\int }|x{|}^{k}d{F}_i(x)\\ & ⩽\underset{ℝ}{\int }|x{|}^2{B}^{k-2}d{F}_i(x)\\ & =B^{k-2}\underset{ℝ}{\int }{x}^{2}d{F}_i(x)\\ & =B^{k-2}\text{E}{X}_i^2\\ & ⩽B^{k-2}{\sigma }^2\end{array}$

$\Rightarrow \prod _{i=1}^n(1+\sum _{k=2}^{\mathrm{\infty }}\frac{t^k}{k!}\text{E}{X}_i^k)⩽\prod _{i=1}^n(1+\sum _{k=2}^{\mathrm{\infty }}\frac{t^k}{k!}{\sigma }^2{B}^{k-2})$

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

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

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

${(1+\frac{{\sigma }^2}{B^2}(e^{tB}-tB-1))}^n⩽\exp (\frac{n{\sigma }^2}{B^2}(e^{tB}-tB-1))$

Damit ist Schritt 3 gezeigt.

Schritt 4

Zu zeigen: $-tϵn+\frac{n{\sigma }^2}{B^2}(e^{tB}-tB-1)⩽-𝒯$

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

$\begin{array}{cc}-tϵn+\frac{n{\sigma }^2}{B^2}(e^{tB}-tB-1)& =-\frac{ϵn}{B}\ln (1+\frac{ϵB}{{\sigma }^2})+\frac{n{\sigma }^2}{B^2}(1+\frac{ϵB}{{\sigma }^2}-\ln (1+\frac{ϵB}{{\sigma }^2})-1)\\ & =\frac{n{\sigma }^2}{B^2}(-\frac{ϵB}{{\sigma }^2}\ln (1+\frac{ϵB}{{\sigma }^2})+\frac{ϵB}{{\sigma }^2}-\ln (1+\frac{ϵB}{{\sigma }^2}))\\ & =\frac{n{\sigma }^2}{B^2}(-x\ln (1+x)+x-\ln (1+x))\\ & =\frac{n{\sigma }^2}{B^2}(x-(1+x)\ln (1+x))\\ & ⩽\frac{n{\sigma }^2}{B^2}(-\frac{3x^2}{2(x+3)})\\ & =-\frac{3n{ϵ}^2}{2ϵB+6{\sigma }^2}\end{array}$

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

$\begin{array}{cc}-\frac{3n{ϵ}^2}{2ϵB+6{\sigma }^2}& =-\frac{(\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B{)}^2}{2B(\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B)+18n{\sigma }^2}\\ & =-\frac{18n{\sigma }^2+𝒯B^2+2B\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B^2}{2B(\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B)+18n{\sigma }^2}𝒯\\ & =-𝒯\end{array}$

Schritt 5

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

$\begin{array}{cc}\text{P}[\frac{1}{n}\sum _{i=1}^n{X}_i⩾\sqrt{\frac{2{\sigma }^2𝒯}{n}}+\frac{2B𝒯}{3n}]& ⩽\text{P}[\frac{1}{n}\sum _{i=1}^n{X}_i⩾\frac{\sqrt{18𝒯n{\sigma }^2+{𝒯}^2{B}^2}+𝒯B}{3n}]\\ & =\text{P}[\frac{1}{n}\sum _{i=1}^n{X}_i⩾ϵ]\\ & =\text{P}[t\sum _{i=1}^n{X}_i⩾tϵn]\\ & =\text{P}[\exp \left(t\sum _{i=1}^n{X}_i\right)⩾\exp \left(tϵn\right)]\end{array}$

Nun wende man die Markow-Ungleichung an:

$\text{P}[\exp \left(t\sum _{i=1}^n{X}_i\right)⩾\exp \left(tϵn\right)]⩽\exp (-tϵn)\text{E}(\prod _{i=1}^n\exp (t{X}_i))$

Aus den Schritten 2 bis 4 folgt:

$\begin{array}{cc}\exp (-tϵn)\text{E}(\prod _{i=1}^n\exp (t{X}_i))& ⩽\exp (-tϵn)\prod _{i=1}^n(1+\sum _{k=2}^{\mathrm{\infty }}\frac{t^k}{k!}\text{E}{X}_i^k)\\ & ⩽\exp (-tϵn)\exp (\frac{n{\sigma }^2}{B^2}(e^{tB}-tB-1))\\ & =\exp (-tϵn+\frac{n{\sigma }^2}{B^2}(e^{tB}-tB-1))\\ & ⩽e^{-𝒯}\end{array}$

$\Rightarrow \text{P}[\frac{1}{n}\sum _{i=1}^n{X}_i⩾\sqrt{\frac{2{\sigma }^2𝒯}{n}}+\frac{2B𝒯}{3n}]⩽e^{-𝒯}$

Wikipedia-Verweis

• Bernstein-Ungleichung