Zum Inhalt springen

Chernoff-Ungleichung

aus Wikipedia, der freien Enzyklopädie

In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach Herman Chernoff benannt, geht jedoch auf Herman Rubin zurück.[1][2]

Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik.

Allgemeine Formulierung

[Bearbeiten | Quelltext bearbeiten]

Die allgemeinste Form der Chernoff-Ungleichung für eine Zufallsvariable X erhält man durch Anwenden der Markov-Ungleichung auf etX:

Für alle t>0 gilt

Pr⁡(X≥a)=Pr⁡(et⋅X≥et⋅a)≤E⁡[et⋅X]et⋅a

und somit auch

Pr⁡(X≥a)≤inft>0E⁡[et⋅X]et⋅a.

Diese Form der Chernoff-Ungleichung verwendet die momenterzeugende Funktion von X. Für eine gegebene Verteilung von X kann durch Ausrechnen dieser Funktion eine spezifische Chernoff-Ungleichung errechnet werden.

Chernoff-Ungleichung für Binomialverteilungen

[Bearbeiten | Quelltext bearbeiten]

Sei X1,X2,…,Xn eine Sequenz von n unabhängigen Bernoulli-Experimenten mit P[Xi=1]=p und P[Xi=0]=1−p. Demnach beschreibt pn die erwartete Anzahl an Erfolgen (Xi=1) des Experiments.

1. Dann gilt für jedes δ>0
P[∑Xi≥(1+δ)⋅pn]≤exp⁡(−min⁡{δ,δ2}3pn)
2. Für jedes δ∈[0,1] gilt:
P[∑Xi≤(1−δ)⋅pn]≤exp⁡(−δ22pn)
3. Für alle t≥2e⋅pn:
P[∑Xi≥t]≤2−t

Erste Chernoff-Schranke

[Bearbeiten | Quelltext bearbeiten]

Sei t>0 eine zunächst beliebige Konstante. Bezeichne Y im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge Y=exp⁡(t∑Xi). Auf Grund der Monotonie der Abbildung x↦exp⁡(tx) folgt dann

P[∑Xi≥(1+δ)⋅pn]=P[Y≥exp⁡(t(1+δ)⋅pn)]=P[Y≥kE[Y]]≤1k,

wobei k als k=exp⁡(t(1+δ)pn)E[Y] definiert ist und die letzte Abschätzung mittels Markow-Ungleichung folgt. Nun gilt

E[exp⁡(tXi)]=(1−p)e0+pet=1+(et−1)p

und somit

E[Y]=E[exp⁡(t∑Xi)]=E[∏exp⁡(tXi)]=∏E[exp⁡(tXi)]=(1+(et−1)p)n.

Damit folgt

1k=e−t(1+δ)pn(1+(et−1)p)n≤e−t(1+δ)pn⋅e(et−1)pn=e−t(1+δ)pn+(et−1)pn.

Betrachte nun t=log⁡(1+δ). Dann gilt

1k≤e−(log⁡(1+δ))(1+δ)pn+δpn=e(δ−(1+δ)log⁡(1+δ))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(δ)≥δ+13min⁡{δ,δ2} gilt. Auf Grund der Monotonie der Exponentialfunktion gilt

1k≤e(δ−(δ+13min⁡{δ,δ2}))pn=exp⁡(−min⁡{δ,δ2}3pn).

Zusammen mit der ersten Abschätzung folgt die Behauptung.

Zweite Chernoff-Schranke

[Bearbeiten | Quelltext bearbeiten]

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


Dritte Chernoff-Schranke

Die Beweisidee besteht darin die Markow-Ungleichung auf Y=4X≥0 anzuwenden, wobei X=∑Xi.

P[∑Xi≥t]=P[X≥t]=P[Y≥4t]≤E[Y]4t

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

E[Y]=E[4X]=E[4∑Xi]=E[4X1]...E[4Xn]

Was abgeschätzt werden kann durch:

E[4X1]...E[4Xn]≤e3p1...e3pn=e3E[X]

Durch die Zusatzbedingung, dass t≥2e⋅pn=2e⋅E[X], folgt:

e3E[X]≤(e32e)t≤2t

Also gilt:

P[∑Xi≥t]≤E[Y]4t≤2t4t=2−t

Chernoff-Ungleichung mithilfe der Standardabweichung

[Bearbeiten | Quelltext bearbeiten]

Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der Standardabweichung formulieren. Seien X1,X2,…,Xn diskrete, unabhängige Zufallsvariablen mit E[Xi]=0 und |Xi|≤1. Bezeichne σ2 die Varianz von X=∑Xi. Dann gilt für jedes 0<λ≤2σ:

P[|∑Xi|≥λσ]≤2exp⁡(−λ24).

Der Beweis ist technisch analog zu dem oben gezeigten Beweis.

  • 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 X1,X2,…,X10 mit pn=12⋅10=5 dar. Somit folgt nach der ersten Chernoff-Ungleichung:
P[∑Xi≥7]=P[∑Xi≥(1+410)⋅5]
≤exp⁡(−min⁡{410,16100}3⋅5)=exp⁡(−415)≈0,766…
  • 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[∑Xi≥70]=P[∑Xi≥(1+410)⋅50]
≤exp⁡(−min⁡{410,16100}3⋅50)=exp⁡(−83)≈0,069…

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ John Bather: A Conversation with Herman Chernoff. In: Statistical Science. 11. Jahrgang, Nr. 4, November 1996, S. 335–350, doi:10.1214/ss/1032280306 (englisch).
  2. ↑ Herman Chernoff: A career in statistics. In: Xihong Lin, Christian Genest, David L. Banks, Geert Molenberghs, David W. Scott, Jane-Ling Wang (Hrsg.): Past, Present, and Future of Statistics. CRC Press, 2014, ISBN 978-1-4822-0496-4, S. 35 (englisch, Online).