Chernoff-Ungleichung

In der Wahrscheinlichkeitstheorie beschreibt die Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Bernoulli-Experimente 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.

Satz

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)$

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.

Varianten

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