Chernoff-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 der ersten Chernoff-Schranke[Bearbeiten]

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


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 = \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+\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+\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[Bearbeiten]

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

Varianten[Bearbeiten]

  • 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 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.

Beispiele[Bearbeiten]

  • 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:

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[Bearbeiten]