Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Chernoff-Ungleichung aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Chernoff-Ungleichung

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,\; \backslash ldots,\; X\_n$ eine Sequenz von $n$ unabhängigen Bernoulli-Experimenten mit $\backslash Pr[X\_i=1]\; =\; p$ und $\backslash 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 $\backslash delta>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 $\backslash delta\; \backslash 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 (Schindelhauer, 2004)

Sei $t\; >\; 0$ eine zunächst beliebige Konstante.
Bezeichne $Y$ im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge $Y\; =\; \backslash exp\backslash left(\; t\; \backslash sum\; X\_i\; \backslash right)$. Auf Grund der Monotonie der Abbildung $x\; \backslash mapsto\; \backslash 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\; =\; \backslash frac\{\backslash exp(t(1+\backslash delta)pn)\}\{\backslash 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\; =\; \backslash log(1+\backslash 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(\backslash delta)\; \backslash geq\; \backslash delta+\backslash frac\{1\}\{3\}\backslash min\backslash \{\backslash delta,\backslash delta^2\backslash \}$ 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,\; \backslash ldots,\; X\_n$ diskrete, unabhängige Zufallsvariablen mit $\backslash textrm\{E\}[X\_i]\; =\; 0$ und $/\text{'}>X\_i|\; \backslash leq\; 1$. Bezeichne $\backslash sigma^2$ die        VIDEO-NEWS UND ANGEBOTE