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

$\mathrm{Pr}(X\ge a)=\mathrm{Pr}(e^{t\cdot X}\ge e^{t\cdot a})\le \frac{\mathrm{E}\left[e^{t\cdot X}\right]}{e^{t\cdot a}}$

und somit auch

$\mathrm{Pr}(X\ge a)\le \underset{t>0}{\inf }\frac{\mathrm{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,\dots ,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[\sum X_i\ge (1+\delta )\cdot pn]\le \exp (-\frac{\min \{\delta ,{\delta }^2\}}{3}pn)$

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

$P[\sum X_i\le (1-\delta )\cdot pn]\le \exp (-\frac{{\delta }^2}{2}pn)$

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

$P[\sum X_i\ge t]\le 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 $Y=\exp (t\sum X_i)$. Auf Grund der Monotonie der Abbildung $x\mapsto \exp (tx)$ folgt dann

$P[\sum X_i\ge (1+\delta )\cdot pn]=P[Y\ge \exp (t(1+\delta )\cdot pn)]=P[Y\ge k\text{E}\left[Y\right]]\le \frac{1}{k}$,

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

$\text{E}[\exp (t{X}_i)]=(1-p)e^0+p{e}^t=1+(e^t-1)p$

und somit

$\text{E}\left[Y\right]=\text{E}[\exp (t\sum X_i)]=\text{E}[\prod \exp (t{X}_i)]=\prod \text{E}[\exp (t{X}_i)]={(1+(e^t-1)p)}^n$.

Damit folgt

$\frac{1}{k}=e^{-t(1+\delta )pn}{(1+(e^t-1)p)}^n\le 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}\le 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 )\ge \delta +\frac{1}{3}\min \{\delta ,{\delta }^2\}$ gilt. Auf Grund der Monotonie der Exponentialfunktion gilt

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

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\ge 0$ anzuwenden, wobei $X=\sum X_i$.

$P[\sum X_i\ge t]=P[X\ge t]=P[Y\ge 4^t]\le \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}]\le e^{3p_1}...e^{3p_n}=e^{3E[X]}$

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

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

Also gilt:

$P[\sum X_i\ge t]\le \frac{E[Y]}{4^t}\le \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,\dots ,X_n$ diskrete, unabhängige Zufallsvariablen mit $\text{E}[X_i]=0$ und $|X_i|\le 1$. Bezeichne ${\sigma }^2$ die Varianz von $X=\sum X_i$. Dann gilt für jedes $0<\lambda \le 2\sigma$:

$P[|\sum X_i|\ge \lambda \sigma ]\le 2\exp (-\frac{{\lambda }^2}{4})$.

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,\dots ,X_{10}$ mit $pn=\frac{1}{2}\cdot 10=5$ dar. Somit folgt nach der ersten Chernoff-Ungleichung:

$P[\sum X_i\ge 7]=P[\sum X_i\ge (1+\frac{4}{10})\cdot 5]$

$\le \exp (-\frac{\min \{\frac{4}{10},\frac{16}{100}\}}{3}\cdot 5)=\exp (-\frac{4}{15})\approx 0,766\dots$

• 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[\sum X_i\ge 70]=P[\sum X_i\ge (1+\frac{4}{10})\cdot 50]$

$\le \exp (-\frac{\min \{\frac{4}{10},\frac{16}{100}\}}{3}\cdot 50)=\exp (-\frac{8}{3})\approx 0,069\dots$

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