imported>Leonry: Entfernen einer Kategorie

2026-04-22T16:06:19Z

Entfernen einer Kategorie

Neue Seite

{{Überarbeiten|||grund=Der Artikel betrachtet zur Zeit nur zwei der zahlreich existierenden Chernoff-Ungleichungen, insbesondere nur für Bernoulli-Experimente mit identischem Parameter (im allgemeinen ist dies jedoch keine Voraussetzung für Chernoff-Schranken), wobei auch für in diesem Falle schärfere Chernoff-Schranken existieren.}}

In der [[Wahrscheinlichkeitstheorie]] beschreibt der Begriff '''Chernoff-Ungleichung''' eine obere Schranke für die [[Wahrscheinlichkeit]], dass eine Sequenz unabhängiger [[Zufallsvariable|Zufallsvariablen]] von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach [[Herman Chernoff]] benannt, geht jedoch auf [[Herman Rubin]] zurück.<ref>
{{cite journal |author=John Bather |year=1996 |month=11 |title=A Conversation with Herman Chernoff |journal=Statistical Science |volume=11 |issue=4 |pages=335–350 |doi=10.1214/ss/1032280306 |language=en}}
</ref><ref>{{Literatur |Autor=Herman Chernoff |Titel=A career in statistics. |Hrsg=Xihong Lin, Christian Genest, David L. Banks, Geert Molenberghs, David W. Scott, Jane-Ling Wang |Sammelwerk=Past, Present, and Future of Statistics. |Verlag=CRC Press |Datum=2014 |ISBN=9781482204964 |Seiten=35 |Online=[http://www.crcpress.com/product/isbn/9781482204964 Online] |Sprache=en}}</ref>

Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der [[Algorithmus#Algorithmenanalyse|Analyse]] von [[Randomisierter Algorithmus|randomisierten Algorithmen]] in der [[Informatik]].

== Allgemeine Formulierung ==
Die allgemeinste Form der Chernoff-Ungleichung für eine Zufallsvariable <math>X</math> erhält man durch Anwenden der [[Markow-Ungleichung (Stochastik)|Markov-Ungleichung]] auf <math>e^{tX}</math>:

Für alle <math>t > 0</math> gilt

:<math>\Pr(X \geq a) = \Pr(e^{t\cdot X} \geq e^{t\cdot a}) \leq \frac{\operatorname E \left [e^{t\cdot X}\right]}{e^{t\cdot a}}</math>

und somit auch

:<math>\Pr(X \geq a) \leq \inf_{t > 0} \frac{\operatorname{E}\left [e^{t\cdot X}\right]}{e^{t\cdot a}}.</math>
Diese Form der Chernoff-Ungleichung verwendet die [[momenterzeugende Funktion]] von <math>X</math>. Für eine gegebene Verteilung von <math>X</math> kann durch Ausrechnen dieser Funktion eine spezifische Chernoff-Ungleichung errechnet werden.

== Chernoff-Ungleichung für Binomialverteilungen ==
Sei <math>X_1, X_2, \ldots, X_n</math> eine Sequenz von <math>n</math> unabhängigen Bernoulli-Experimenten mit <math>P[X_i=1] = p</math> und <math>P[X_i=0] = 1-p</math>. Demnach beschreibt <math>pn</math> die [[Erwartungswert|erwartete Anzahl]] an Erfolgen (<math>X_i=1</math>) des Experiments.

:1. Dann gilt für jedes <math>\delta>0</math>
::<math>
P\left[ \sum X_i \geq (1+\delta)\cdot pn \right]
\leq \exp\left( -\frac{\min\{\delta,\delta^2\}}{3}pn \right)
</math>
:2. Für jedes <math>\delta \in [0,1]</math> gilt:
::<math>
P\left[ \sum X_i \leq (1-\delta)\cdot pn \right]
\leq \exp\left( -\frac{\delta^2}{2}pn \right)
</math>
:3. Für alle <math>t \geq 2e \cdot p n</math>:
::<math>
P\left[ \sum X_i \geq t \right]
\leq 2^{-t}
</math>

=== Beweis ===
==== Erste Chernoff-Schranke ====
Sei <math>t > 0</math> eine zunächst beliebige [[Mathematische Konstante|Konstante]].
Bezeichne <math>Y</math> im Folgenden zur Vereinfachung der Schreibweise eine neue [[Zufallsvariable]] vermöge <math>\textstyle Y = \exp\left( t \sum X_i \right)</math>. Auf Grund der [[Reelle monotone Funktion|Monotonie]] der [[Abbildung (Mathematik)|Abbildung]] <math>x \mapsto \exp(tx)</math> folgt dann
:<math>
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}
</math>,
wobei <math>k</math> als <math>k = \tfrac{\exp(t(1+\delta)pn)}{\textrm{E}[Y]}</math> definiert ist und die letzte Abschätzung mittels [[Markow-Ungleichung (Stochastik)|Markow-Ungleichung]] folgt.
Nun gilt
:<math>
\textrm{E}\left[ \exp(tX_i) \right]
= (1-p) e^0 + p e^t
= 1 + (e^t-1)p
</math>
und somit
:<math>
\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
</math>.
Damit folgt
:<math>
\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}
</math>.
Betrachte nun <math>t = \log(1+\delta)</math>. Dann gilt
:<math>
\frac{1}{k} \leq e^{-(\log(1+\delta))(1+\delta)pn + \delta pn}
= e^{( \delta-(1+\delta)\log(1+\delta) ) pn}
</math>.
Für einen Teil des [[Exponent (Mathematik)|Exponenten]] des rechten Terms
:<math>
L(\delta) = (1+\delta) \log(1+\delta)
</math>
kann man mittels [[Kurvendiskussion]] und [[Taylor-Reihe]]nentwicklung zeigen, dass stets <math>L(\delta) \geq \delta+\tfrac{1}{3}\min\{\delta,\delta^2\}</math> gilt. Auf Grund der Monotonie der [[Exponentialfunktion]] gilt
:<math>
\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)
</math>.

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 (Stochastik)|Markow-Ungleichung]] auf <math>
Y = 4^X \geq 0
</math> anzuwenden, wobei <math>
X = \sum X_i
</math>.

:<math>
P\left[ \sum X_i \geq t \right]
= P\left[ X \geq t \right]
= P\left[ Y \geq 4^t \right]
\leq \frac{E[Y]}{4^t}

</math>

Dann gilt aufgrund der Unabhängigkeit der Bernoulli-Experimente:

:<math>
E[Y] = E[4^X] = E[4^{\sum X_i}] = E[4^{X_1}]...E[4^{X_n}]

</math>

Was abgeschätzt werden kann durch:

:<math>
E[4^{X_1}]...E[4^{X_n}] \leq e^{3 p_1} ... e^{3 p_n} = e^{3E[X]}

</math>

Durch die Zusatzbedingung, dass <math>t \geq 2e \cdot p n = 2e \cdot E[X]</math>, folgt:

:<math>
e^{3E[X]} \leq (e^\frac{3}{2e})^t \leq 2^t

</math>

Also gilt:

:<math>
P\left[ \sum X_i \geq t \right] \leq \frac{E[Y]}{4^t} \leq \frac{2^t}{4^t} = 2^{-t}

</math>

== Chernoff-Ungleichung mithilfe der Standardabweichung ==
Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der [[Standardabweichung (Wahrscheinlichkeitstheorie)|Standardabweichung]] formulieren. Seien <math>X_1, X_2, \ldots, X_n</math> diskrete, unabhängige Zufallsvariablen mit <math>\textrm{E}[X_i] = 0</math> und <math>|X_i| \leq 1</math>. Bezeichne <math>\sigma^2</math> die [[Varianz (Stochastik)|Varianz]] von <math>\textstyle X = \sum X_i</math>. Dann gilt für jedes <math>0 < \lambda \leq 2\sigma</math>:
:<math>P\left[\left|\sum X_i\right| \geq \lambda\sigma\right] \leq 2 \exp\left(-\frac{\lambda^2}{4}\right)</math>.
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-Experiment]]e <math>X_1,X_2,\ldots,X_{10}</math> mit <math>pn = \tfrac{1}{2} \cdot 10 = 5</math> dar. Somit folgt nach der ersten Chernoff-Ungleichung:
:<math>
P\left[ \sum X_i \geq 7 \right] = P\left[ \sum X_i \geq \left(1+\frac{4}{10}\right)\cdot 5 \right]
</math>
:<math>
\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
</math>

* 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:
:<math>
P\left[ \sum X_i \geq 70 \right] = P\left[ \sum X_i \geq \left(1+\frac{4}{10}\right)\cdot 50 \right]
</math>
:<math>
\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
</math>

== Literatur ==
* Christian Schindelhauer: ''[[Peer-to-Peer]] Netzwerke'', [https://pdfs.semanticscholar.org/47bc/b19fa74eea2740b4d46cb57fc434c0199db6.pdf pdfs.semanticscholar.org], Albert-Ludwigs-Universität Freiburg, 2006.
* Kirill Levchenko: [http://www.cs.ucsd.edu/~klevchen/techniques/chernoff.pdf Chernoff Bound]

== Einzelnachweise ==
<references />
[[Kategorie:Satz (Mathematik)]]
[[Kategorie:Ungleichung (Stochastik)]]

Chernoff-Ungleichung - Versionsgeschichte

imported>Leonry: Entfernen einer Kategorie