Chernoff-Ungleichung

In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach Herman Chernoff benannt, geht jedoch auf Herman Rubin zurück.

Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik.

Allgemeine Formulierung

Die allgemeinste Form der Chernoff-Ungleichung für eine Zufallsvariable $X$ erhält man durch Anwenden der Markov-Ungleichung auf $e^{tX}$:

Für alle $t>0$ gilt

$\Pr(X\geq a)=\Pr(e^{t\cdot X}\geq e^{t\cdot a})\leq {\frac {\operatorname {E} \left[e^{t\cdot X}\right]}{e^{t\cdot a}}}$

und somit auch

$\Pr(X\geq a)\leq \inf _{t>0}{\frac {\operatorname {E} \left[e^{t\cdot X}\right]}{e^{t\cdot a}}}.$

Diese Form der Chernoff-Ungleichung verwendet die momenterzeugende Funktion von $X$. Für eine gegebene Verteilung von $X$ kann durch Ausrechnen dieser Funktion eine spezifische Chernoff-Ungleichung errechnet werden.

Chernoff-Ungleichung für Binomialverteilungen

Sei $X_{1},X_{2},\ldots ,X_{n}$ eine Sequenz von $n$ unabhängigen Bernoulli-Experimenten mit $P[X_{i}=1]=p$ und $P[X_{i}=0]=1-p$. Demnach beschreibt $pn$ die erwartete Anzahl an Erfolgen ($X_{i}=1$) des Experiments.

1. Dann gilt für jedes $\delta >0$

$P\left[\sum X_{i}\geq (1+\delta )\cdot pn\right]\leq \exp \left(-{\frac {\min\{\delta ,\delta ^{2}\}}{3}}pn\right)$

2. Für jedes $\delta \in [0,1]$ gilt:

$P\left[\sum X_{i}\leq (1-\delta )\cdot pn\right]\leq \exp \left(-{\frac {\delta ^{2}}{2}}pn\right)$

3. Für alle $t\geq 2e\cdot pn$:

$P\left[\sum X_{i}\geq t\right]\leq 2^{-t}$

Beweis

Erste Chernoff-Schranke

Sei $t>0$ eine zunächst beliebige Konstante. Bezeichne $Y$ im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge $\textstyle Y=\exp \left(t\sum X_{i}\right)$. Auf Grund der Monotonie der Abbildung $x\mapsto \exp(tx)$ folgt dann

$P\left[\sum X_{i}\geq (1+\delta )\cdot pn\right]=P\left[Y\geq \exp \left(t(1+\delta )\cdot pn\right)\right]=P\left[Y\geq k{\textrm {E}}\left[Y\right]\right]\leq {\frac {1}{k}}$,

wobei $k$ als $k={\tfrac {\exp(t(1+\delta )pn)}{{\textrm {E}}[Y]}}$ definiert ist und die letzte Abschätzung mittels Markow-Ungleichung folgt. Nun gilt

${\textrm {E}}\left[\exp(tX_{i})\right]=(1-p)e^{0}+pe^{t}=1+(e^{t}-1)p$

und somit

${\textrm {E}}\left[Y\right]={\textrm {E}}\left[\exp(t\sum X_{i})\right]={\textrm {E}}\left[\prod \exp(tX_{i})\right]=\prod {\textrm {E}}\left[\exp(tX_{i})\right]=\left(1+(e^{t}-1)p\right)^{n}$.

Damit folgt

${\frac {1}{k}}=e^{-t(1+\delta )pn}\left(1+(e^{t}-1)p\right)^{n}\leq e^{-t(1+\delta )pn}\cdot e^{(e^{t}-1)pn}=e^{-t(1+\delta )pn+(e^{t}-1)pn}$.

Betrachte nun $t=\log(1+\delta )$. Dann gilt

${\frac {1}{k}}\leq e^{-(\log(1+\delta ))(1+\delta )pn+\delta pn}=e^{(\delta -(1+\delta )\log(1+\delta ))pn}$.

Für einen Teil des Exponenten des rechten Terms

$L(\delta )=(1+\delta )\log(1+\delta )$

kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets $L(\delta )\geq \delta +{\tfrac {1}{3}}\min\{\delta ,\delta ^{2}\}$ gilt. Auf Grund der Monotonie der Exponentialfunktion gilt

${\frac {1}{k}}\leq e^{(\delta -(\delta +{\frac {1}{3}}\min\{\delta ,\delta ^{2}\}))pn}=\exp \left(-{\frac {\min\{\delta ,\delta ^{2}\}}{3}}pn\right)$.

Zusammen mit der ersten Abschätzung folgt die Behauptung.

Zweite Chernoff-Schranke

Der Beweis der zweiten Schranke folgt technisch analog zur ersten Schranke.

Dritte Chernoff-Schranke

Die Beweisidee besteht darin die Markow-Ungleichung auf $Y=4^{X}\geq 0$ anzuwenden, wobei $X=\sum X_{i}$.

$P\left[\sum X_{i}\geq t\right]=P\left[X\geq t\right]=P\left[Y\geq 4^{t}\right]\leq {\frac {E[Y]}{4^{t}}}$

Dann gilt aufgrund der Unabhängigkeit der Bernoulli-Experimente:

$E[Y]=E[4^{X}]=E[4^{\sum X_{i}}]=E[4^{X_{1}}]...E[4^{X_{n}}]$

Was abgeschätzt werden kann durch:

$E[4^{X_{1}}]...E[4^{X_{n}}]\leq e^{3p_{1}}...e^{3p_{n}}=e^{3E[X]}$

Durch die Zusatzbedingung, dass $t\geq 2e\cdot pn=2e\cdot E[X]$, folgt:

$e^{3E[X]}\leq (e^{\frac {3}{2e}})^{t}\leq 2^{t}$

Also gilt:

$P\left[\sum X_{i}\geq t\right]\leq {\frac {E[Y]}{4^{t}}}\leq {\frac {2^{t}}{4^{t}}}=2^{-t}$

Chernoff-Ungleichung mithilfe der Standardabweichung

Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der Standardabweichung formulieren. Seien $X_{1},X_{2},\ldots ,X_{n}$ diskrete, unabhängige Zufallsvariablen mit ${\textrm {E}}[X_{i}]=0$ und $|X_{i}|\leq 1$. Bezeichne $\sigma ^{2}$ die Varianz von $\textstyle X=\sum X_{i}$. Dann gilt für jedes $0<\lambda \leq 2\sigma$:

$P\left[\left|\sum X_{i}\right|\geq \lambda \sigma \right]\leq 2\exp \left(-{\frac {\lambda ^{2}}{4}}\right)$.

Der Beweis ist technisch analog zu dem oben gezeigten Beweis.

Beispiele

• Betrachte die folgende Frage: Wie wahrscheinlich ist es, beim zehnmaligen Wurf einer fairen Münze wenigstens siebenmal das Ergebnis „Zahl“ zu erhalten? Die Münzwürfe stellen Bernoulli-Experimente $X_{1},X_{2},\ldots ,X_{10}$ mit $pn={\tfrac {1}{2}}\cdot 10=5$ dar. Somit folgt nach der ersten Chernoff-Ungleichung:

$P\left[\sum X_{i}\geq 7\right]=P\left[\sum X_{i}\geq \left(1+{\frac {4}{10}}\right)\cdot 5\right]$

$\leq \exp \left(-{\frac {\min\{{\frac {4}{10}},{\frac {16}{100}}\}}{3}}\cdot 5\right)=\exp \left(-{\frac {4}{15}}\right)\approx 0{,}766\ldots$

• Man formuliere das obige Beispiel nur leicht um und frage stattdessen: Wie wahrscheinlich ist es, bei hundertmaligem fairen Münzwurf wenigstens siebzigmal das Ergebnis „Zahl“ zu erhalten? Sofort erweist sich die erste Chernoff-Schranke als deutlich stärker:

$P\left[\sum X_{i}\geq 70\right]=P\left[\sum X_{i}\geq \left(1+{\frac {4}{10}}\right)\cdot 50\right]$

$\leq \exp \left(-{\frac {\min\{{\frac {4}{10}},{\frac {16}{100}}\}}{3}}\cdot 50\right)=\exp \left(-{\frac {8}{3}}\right)\approx 0{,}069\ldots$

Literatur

• Christian Schindelhauer, Algorithmen für Peer-to-Peer Netzwerke (Vorlesungsmaterialien), http://wwwcs.upb.de/cs/ag-madh/WWW/Teaching/2004SS/AlgoP2P/skript.html, Universität Paderborn, 2004.
• Kirill Levchenko, Notizen, http://www.cs.ucsd.edu/~klevchen/techniques/chernoff.pdf