Chernoff-Schranke

In der Wahrscheinlichkeitstheorie beschreibt die nach Herman Chernoff benannte Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Bernoulli-Experimente von ihrer erwarteten Anzahl an Erfolgen abweicht.

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 $\Pr[X_i=1] = p$ und $\Pr[X_i=0] = 1-p$. Demnach beschreibt pn die erwartete Anzahl an Erfolgen (X_i = 1) des Experiments.

1. Dann gilt für jedes δ > 0

$\Pr\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:

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

Beweis der ersten 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\left( t \sum X_i \right)$. Auf Grund der Monotonie der Abbildung $x \mapsto \exp(tx)$ folgt dann

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

wobei k als $k = \frac{\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 + p e^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 + δ). 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(δ) = (1 + δ)log(1 + δ)

kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets $L(\delta) \geq \delta+\frac{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.

Beweis der zweiten 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 E[X_i] = 0 und $|X_i| \leq 1$. Bezeichne σ² die Varianz von $X = \sum X_i$. Dann gilt für jedes $0 < \lambda \leq 2\sigma$:

$\Pr\left[\left|\sum X_i\right| \geq \lambda\sigma\right] \leq 2 \exp(-\frac{\lambda^2}{4})$

Der Beweis ist technisch analog zu dem oben gezeigten.

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

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

$\leq \exp\left( -\frac{\min\{\frac{4}{10},\frac{16}{100}\}}{3} \cdot 5 \right) = \exp(-\frac{4}{15}) \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:

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

$\leq \exp\left( -\frac{\min\{\frac{4}{10},\frac{16}{100}\}}{3} \cdot 50 \right) = \exp(-\frac{8}{3}) \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