Konzentrations-Ungleichungen: Die Chernoff-Schranke für die Binomialverteilung

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Eigenschaften von Zufallsvariablen
      • Konzentrations-Ungleichungen: Die Tschebyscheff-Ungleichung
      • Konzentrations-Ungleichungen: Die Chernoff-Schranke für die Binomialverteilung

Einführung

In Konzentrations-Ungleichungen: Die Tschebyscheff-Ungleichung wurde eine einfache Ungleichung zur Berechnung der Wahrscheinlichkeiten von seltenen Ereignissen vorgestellt. Die Tschebyscheff-Ungleichung ist zwar einfach herzuleiten und anzuwenden, liefert aber bei vielen Beispielen nur sehr ungenaue Abschätzungen. Diskutiert wurden Beispiele mit Summen von unabhängigen Zufallsvariablen, wo sich die exakten Wahrscheinlichkeiten und die Näherungswerte um mehrere Größenordnungen unterscheiden.

Mit der Chernoff-Schranke wird eine weitere Konzentrations-Ungleichung vorgestellt; sie wird vorerst nur für die Binomialverteilung berechnet. Wie sich zeigen wird, hat die Chernoff-Schranke meist gegenteilige Eigenschaften der Tschebyscheff-Ungleichung:

1. Die Herleitung erfordert die Kenntnis der sogenannten momentenerzeugenden Funktion einer Zufallsvariable. Ihre Definition und die wichtigsten Eigenschaften werden hier besprochen.
2. Der Term, mit dem Wahrscheinlichkeiten seltener Ereignisse abgeschätzt werden, ist selbst für die Binomialverteilung sehr kompliziert. Oft gibt man sich mit schwächeren Abschätzungen zufrieden, die auf einfachere Terme führen.
3. Für Summen von unabhängigen Zufallsvariablen (so wie hier die Binomialverteilung, die man als Summe von Bernoulli-verteilten Zufallsvariablen darstellen kann) liefert die Chernoff-Schranke erstaunlich gute Abschätzungen für Wahrscheinlichkeiten von seltenen Ereignissen. Im Bereich von etwa einer bis drei Standardabweichungen um den Erwartungswert, sind die Ergebnisse ähnlich denen der Tschebyscheff-Ungleichung.

Es wird versucht, die Schritte bei der Herleitung der Chernoff-Schranke verständlich zu machen und zu klären, warum sie Chernoff-Schranke bessere Abschätzungen liefern kann als die Tschebyscheff-Ungleichung.

Die momentenerzeugende Funktion

Definition der momentenerzeugenden Funktion

In vielen Anwendungen wird zu einer gegebenen Zufallsvariable X der Erwartungswert E(X) und die Varianz Var(X) berechnet. Es sollte klar sein, dass man aus diesen beiden Kenngrößen nicht eindeutig auf die Verteilung der Zufallsvariable schließen kann. Auch Zufallsvariablen, die in Erwartungswert und Varianz übereinstimmen, können sich in höheren Momenten, also Erwartungswerten der Art

E(X^k), k = 2, 3, ...,

unterscheiden. Erst wenn zwei Zufallsvariablen in allen Momenten übereinstimmen, ist es sinnvoll zu fragen, ob aus den Momenten eindeutig die Verteilung der Zufallsvariable rekonstruiert werden kann.

Um eine möglichst einfache Beziehung zwischen einer Zufallsvariable X und ihren Momenten herzustellen, wird die momentenerzeugende Funktion M_X (t) einer Zufallsvariable eingeführt. Ihre Definition erfolgt in Abbildung 1, Gleichung (1). Aufgrund der exponentiellen Abhängigkeit, wird oft ihr natürlicher Logarithmus benötigt; dies definiert die logarithmische momentenerzeugende Funktion L_X (t), siehe Gleichung (2) in Abbildung 1.

Abgekürzt werden die Namen der Funktionen mit MGF (= moment generating function) und L-MGF.

Auf die Frage, für welche reellen Zahlen t die momentenerzeugende Funktion einer Zufallsvariable wohldefiniert ist, wird hier nicht eingegangen – die Beispiele sind so gewählt, dass die rechte Seite in Gleichung (1) für jede beliebige reelle Zahl kleiner als unendlich ist. Da die Exponentialfunktion nur echt positive Werte annehmen kann, ist L_X (t) definiert, wenn dies für M_X (t) gilt.

Wie die Beziehung zu den Momenten hergestellt wird, ist auf den ersten Blick nicht erkennbar; dazu wird die Exponentialfunktion in eine Potenzreihe entwickelt und in die momentenerzeugende Funktion eingesetzt (siehe Gleichung (3) in Abbildung 1). Durch Koeffizienten-Vergleich mit der Taylor-Reihe der momentenerzeugenden Funktion (Gleichung (4)) ergibt sich der Zusammenhang von M_X (t) und den Momenten von X (Gleichung (5)).

Abbildung 1: Die Definition der momentenerzeugenden Funktion und der logarithmisch momentenerzeugenden Funktion. Die Darstellung der Exponentialfunktion als Potenzreihe rechtfertigt den Namen der momentenerzeugenden Funktion.

Die Berechnungen in Abbildung 1 setzen natürlich voraus, dass die unendlichen Summen existieren, was hier nicht weiter diskutiert werden soll. Aber es sollte klar sein, dass man auch Zufallsvariablen konstruieren kann, bei denen die momentenerzeugende Funktion nur für t = 0 existiert und man keine Ableitungen der momentenerzeugenden Funktion bilden kann.

Nach einer anschaulichen Bedeutung von M_X (t), die über die Berechnung der Momente hinausgeht, sollte man besser nicht fragen; vorerst ist sie ein formales Hilfsmittel, um eine Wahrscheinlichkeitsverteilung in eine reelle Funktion zu transformieren. Dass diese Transformation insbesondere für die Verteilung der Summe von unabhängigen Zufallsvariablen von Bedeutung ist, wird die Untersuchung der Eigenschaften der momentenerzeugenden Funktion zeigen. Im Laufe dieser Diskussionen wird sich dann auch ein besseres Verständnis für die momentenerzeugende Funktion einstellen.

Beispiel: Die Bernoulli-Verteilung

Ein einfaches Beispiel soll die formalen Definitionen veranschaulichen: Die Bernoulli-Verteilung beschreibt eine diskrete Zufallsvariable, die die beiden Werte 0 oder 1 mit den Wahrscheinlichkeiten q = 1 - p beziehungsweise p annimmt, wobei 0 < p < 1. Für p = 1/2 könnte man an eine faire Münze denken (0 und 1 stehen für Kopf und Zahl), für andere Werte von p ist die Münze nicht fair.

Sämtliche Momente der Verteilung können explizit berechnet werden – hier ist ihre Berechnung nicht schwieriger als die des Erwartungswertes:

E(X^k) = 0^k · q + 1^k · p = p, für k = 1, 2, ...

Für k = 0 erhält man 1, da 0⁰ = 1.

Die momentenerzeugende Funktion definiert für die diskrete Zufallsvariable eine reelle Funktion, siehe Gleichung (1) in Abbildung 2.

Die Ableitungen an der Stelle t = 0 können berechnet werden (Gleichung (2) in Abbildung 2) und liefern die Werte der explizit berechneten Momente.

Abbildung 2: Für eine Bernoulli-verteilte Zufallsvariable X wird die momentenerzeugende Funktion berechnet; sie wird eingesetzt, um die höheren Momente von X zu berechnen.

In Abbildung 3 links oben ist die momentenerzeugende Funktion einer Bernoulli-verteilten Zufallsvariable mit p = 1/2 zu sehen. Rechts oben sind zusätzlich die momentenerzeugenden Funktionen für p = 1/4 und p = 3/4 gezeigt. Unten sind die entsprechenden Funktionen L_X (t) dargestellt.

Abbildung 3: Oben: Die momentenerzeugende Funktion der Bernoulli-Verteilung. Unten: Ihr natürlicher Logarithmus. Jeweils links: Bernoulli-Verteilung mit p = 0.5. Jeweils rechts: zusätzlich p = 0.25 und p = 0.75.

Die momentenerzeugenden Funktion der Summe von unabhängigen Zufallsvariablen

Im folgenden Unterabschnitt soll die momentenerzeugende Funktion für die Binomialverteilung berechnet werden. Man könnte dazu das Verfahren aus Abbildung 2 anwenden und den entsprechenden Erwartungswert direkt berechnen.

Es gibt aber eine einfachere Methode, die darauf beruht, dass die Binomialverteilung aus der Bernoulli-Verteilung erzeugt werden kann. Sind die Zufallsvariablen X₁, X₂, ..., X_N jeweils Bernoulli-verteilt mit Wahrscheinlichkeit p und unabhängig voneinander, so ist die Zufallsvariable

S = X₁ + X₂ + ... + X_N

Binomial-verteilt. Für die Bernoulli-Verteilung ist die momentenerzeugende Funktion bekannt; lässt sich daraus die momentenerzeugende Funktion der Zufallsvariable S, also der Binomialverteilung gewinnen?

Die Zufallsvariablen X₁, X₂, ..., X_N sind unabhängig voneinander, folglich sind für ein festgehaltenes t die Zufallsvariablen

exp(t X₁), exp(t X₂), ..., exp(t X_N)

unabhängig voneinander.

Man benötigt jetzt noch das Argument, dass für unabhängige Zufallsvariablen X und Y gilt:

E (X · Y) = E (X) · E (Y).

Die momentenerzeugende Funktion der Zufallsvariable S wird Gleichung (1) in Abbildung 4 berechnet: es handelt sich um einen Erwartungswert eines Produktes von N Faktoren (hier geht nur das entsprechende Potenzgesetz ein). Da diese N Faktoren unabhängige Zufallsvariablen sind, kann man den Erwartungswert wie in Gleichung (2) berechnen und kann die momentenerzeugenden Funktionen der Zufallsvariablen X₁, X₂, ..., X_N einsetzen.

Da dieses Argument für jedes reelle t gilt, hat man insgesamt die Gleichung (3) in Abbildung 4 hergeleitet.

Abbildung 4: Bei unabhängigen Zufallsvariablen ist die momentenerzeugende Funktion ihrer Summe gleich dem Produkt der momentenerzeugenden Funktionen der Summanden.

Die momentenerzeugende Funktion für Binomial-verteilte Zufallsvariablen

Wird ein Glücksspiel N mal unabhängig voneinander durchgeführt und beträgt die Gewinn-Wahrscheinlichkeit bei einem Spiel p, so wird die Wahrscheinlichkeit dafür, dass man genau k Treffer erzielt durch B(N, p, k) berechnet (siehe Gleichung (1) in Abbildung 5). Entsprechend kann man die Bernoulli-Verteilung interpretieren: Wird ein Glücksspiel einmal durchgeführt, kann mit Wahrscheinlichkeit p gewinnen beziehungsweise mit Wahrscheinlichkeit q = 1 - p verlieren.

Dies kann mit Zufallsvariablen ausgedrückt werden: Beschreibt die Zufallsvariable X_i den Ausgang des i-ten Spiels (1 für Gewinn, 0 für Verlust), so beschreibt die Zufallsvariable

S = X₁ + X₂ + ... + X_N

die Anzahl der gewonnen Spiele bei N unabhängig voneinander durchgeführten Spielen.

Da die momentenerzeugende Funktion der Bernoulli-Verteilung bekannt ist (siehe Gleichung (1) in Abbildung 2), lässt sich mit den Überlegungen aus dem letzten Unterabschnitt die momentenerzeugende Funktion der Binomialverteilung berechnen, siehe Gleichung (2) in Abbildung 5.

Abbildung 5: Die Berechnung der momentenerzeugenden Funktion für die Binomialverteilung.

Aufgabe:

Diskutieren Sie, wie die Graphen der MGF und der L-MGF der Binomialverteilung aus den Graphen der entsprechenden Funktionen der Bernoulli-Verteilung hervorgehen (siehe Abbildung 3).

Wie äußert sich die Variation von N?

Die Berechnung der Chernoff-Schranke

Die Fragestellung

Die Binomialverteilung B(N, p, k) wird zum Beispiel dafür verwendet, um die Wahrscheinlichkeit zu berechnen, dass bei N Spielen genau k Treffer eintreten (wobei die Gewinn-Wahrscheinlichkeit für ein Spiel p beträgt und die Spiele unabhängig voneinander durchgeführt werden). Die Binomialverteilung zeigt das typische Verhalten, das viele andere Wahrscheinlichkeits-Verteilungen besitzen:

1. Mit hoher Wahrscheinlichkeit werden Werte angenommen, die nur wenig vom Erwartungswert abweichen (Konzentration um den Erwartungswert).
2. Es kommen zwar sehr große Abweichungen vom Erwartungswert vor, diese besitzen aber sehr kleine Wahrscheinlichkeiten (seltene Ereignisse).

Und da für große N die Berechnung von B(N, p, k) sehr aufwendig ist, wird man sich in vielen Anwendungen mit Abschätzungen (etwa für die Wahrscheinlichkeit von seltenen Ereignissen) zufrieden geben. Mit der Tschebyscheff-Ungleichung wurde bereits eine sehr einfache Abschätzung diskutiert (siehe Konzentrations-Ungleichungen: Die Tschebyscheff-Ungleichung).

Abbildung 6 zeigt dazu die Wahrscheinlichkeiten einer Binomial-verteilten Zufallsvariable X mit N = 20 und p = 0.5; der Erwartungswert liegt bei

E(X) = μ = p · N = 10.

Zusätzlich sind zwei Schranken μ ± a (mit a = 2.5) eingetragen, die folgende Ereignisse charakterisieren:

1. |X - μ| < a (blau)
2. X > μ + a (grün)
3. X < μ - a (rot).

Abbildung 6: Die Binomialverteilung B(N, p, k) mit N = 20 und p = 0.5. Farbig gekennzeichnet sind drei Ereignisse, wie sie typischerweise bei Fragestellungen mit der Binomialverteilung auftreten.

Sucht man Abschätzungen für die in Abbildung 6 gekennzeichneten Ereignisse, so kann man etwa die Tschebyscheff-Ungleichung verwenden; in Abbildung 7 ist sie nochmals formuliert (Abschätzungen (1) und (2), wobei in Letzterer nur eine andere Skalierung für die Schranke a gewählt wird). Herleiten kann man die Ungleichung von Tschebyscheff aus der allgemeinen Markov-Ungleichung (siehe Gleichung (4) in Abbildung 7).

Abbildung 7: Die Tschebyscheff-Ungleichung in zwei verschiedenen Formulierungen (1) und (2), die sich nur in der Skalierung der Schranke unterscheiden. Herleiten kann man sie aus der allgemeinen Markov-Ungleichung (4), wenn man f(x) = x² setzt.

In Konzentrations-Ungleichungen: Die Tschebyscheff-Ungleichung wurde diskutiert, dass die Ungleichung von Tschebyscheff zwar einfach herzuleiten und anzuwenden ist, dass sie aber in vielen Anwendungen sehr schlechte Abschätzungen liefert. Dies sollen die Abbildung 8 bis 10 verdeutlichen.

Abbildung 8 ist folgendermaßen zu lesen:

1. Man gibt sich einen Wert für die Schranke a vor und berechnet die Wahrscheinlichkeit P(|X - E(X)| ≥ a) wie auf der linken Seite in Gleichung (1) in Abbildung 7. Hier wird die exakte Wahrscheinlichkeit mit Hilfe der Binomialverteilung berechnet. (In Abbildung 6 sind für a = 2.5 die entsprechenden Wahrscheinlichkeiten rot und grün gekennzeichnet. In Abbildung 8 ist wie in Abbildung 6 die Binomialverteilung mit N = 20 und p = 0.5 gewählt.)
2. Die Schranke a kann die Werte von 0 bis N/2 annehmen (in den Abbildungen 6 und 8 also Werte von 0 bis 10).
3. Diese Wahrscheinlichkeit P(|X - E(X)| ≥ a) wird gegen a aufgetragen (blaue Stufenfunktion in Abbildung 8).
4. Zusätzlich wird die Abschätzung gemäß der Ungleichung von Tschebyscheff berechnet (also σ² / a², siehe rechte Seite von Gleichung (1) in Abbildung 7). Der Wert dieser Schranke ist in Abbildung 8 rot eingetragen.
5. Zur besseren Orientierung ist die Standardabweichung der Binomialverteilung eingetragen: a = σ. Hier ist sie ungefähr gleich 2.24 (schwarz). Für a < σ liefert die Ungleichung von Tschebyscheff keine hilfreichen Werte.

Abbildung 8: Wahrscheinlichkeiten von Ereignissen der Art |X - μ| ≥ a für die Binomialverteilung (blau) mit N = 20 und p = 0.5 und ihre Abschätzung mit Hilfe der Tschebyscheff-Ungleichung (rot).

In Abbildung 9 wird N = 100 und p = 0.5 gewählt; schwarz eingetragen ist wieder die Standardabweichung.

Abbildung 9: Wahrscheinlichkeiten von Ereignissen der Art |X - μ| ≥ a für die Binomialverteilung (blau) und ihre Abschätzung mit Hilfe der Tschebyscheff-Ungleichung (rot). Hier für N = 100 und p = 0.5.

In Abbildung 10 wird N = 1000 und p = 0.5 gewählt.

Abbildung 10: Wahrscheinlichkeiten von Ereignissen der Art |X - μ| ≥ a für die Binomialverteilung (blau) und ihre Abschätzung mit Hilfe der Tschebyscheff-Ungleichung (rot). Hier für N = 1000 und p = 0.5.

In Konzentrations-Ungleichungen: Die Tschebyscheff-Ungleichung wurde ebenso diskutiert, dass die Ungleichung von Tschebyscheff deshalb eine so schlechte Abschätzung liefert, da sie nur den Erwartungswert und die Varianz einer Verteilung berücksichtigt; höhere Momente gehen nicht in die Abschätzung ein.

Genau hier setzt die Abschätzung von Chernoff an: es soll eine schärfere Abschätzung hergeleitet werden, indem man die höheren Momente der Verteilung berücksichtigt. Die nächsten Abschnitte zeigen die Vorgehensweise und veranschaulichen die Ergebnisse.

Die Herleitung der Chernoff-Schranke für die Binomialverteilung

Im Folgenden ist X eine Binomial-verteilte Zufallsvariable mit

P(X = k) = B(N, p, k), k = 0, 1, ..., N (siehe Gleichung (1) in Abbildung 5).

Wie immer wird q = 1 - p gesetzt.

Im Gegensatz zur Ungleichung von Tschebyscheff wird hier die Wahrscheinlichkeit eines "einseitigen" seltenen Ereignisses abgeschätzt; damit ist gemeint, dass nur die Werte der Zufallsvariable rechts (beziehungsweise links) der Schranke b betrachtet werden, also

P (X > b) beziehungsweise P (X < b).

Vorerst wird eine beliebige reelle Zahl t > 0 betrachtet. Da die Exponentialfunktion exp(t) für t > 0 streng monoton zunehmend ist, gilt die erste Gleichheit (1) in Abbildung 11. Die Abschätzung in (1) folgt aus der allgemeinen Markov-Ungleichung (siehe Gleichung (4) in Abbildung 7).

Im Zähler der rechten Seite von Gleichung (1) in Abbildung 11 steht die momentenerzeugende Funktion von X; setzt man diese für eine Binomial-verteilte Zufallsvariable X ein, erhält man die Abschätzung (2) in Abbildung 11.

Somit stehen auf der rechten Seite der Abschätzung (2):

• Größen, die die Verteilung charakterisieren (q = 1 - p, p, N),
• die Schranke b und
• die Zahl t, die noch beliebige positive Werte annehmen kann.

Abbildung 11: Herleitung der Chernoff-Schranke für die Binomialverteilung aus der momentenerzeugenden Funktion und der Markov-Ungleichung; ausführliche Erklärung im Text.

Da t > 0 noch frei wählbar ist, kann man die optimale Abschätzung für P (X ≥ b) bestimmen, indem man das Minimum der rechten Seite in (2) bei Variation von t sucht. Dies geschieht, indem man die Ableitung nach t bildet und untersucht, ob man damit ein Minimum identifiziert.

Man beachte, dass hier mit "optimale Abschätzung für P (X ≥ b)" nicht gemeint ist, dass die Ungleichung zu einer Gleichung wird. Mit "optimal" ist vielmehr gemeint, dass nach Anwendung der Markov-Ungleichung die optimale Schranke gesucht wird. Ob die Markov-Ungleichung hier eine echte Ungleichung oder eine Gleichung ist, wird nicht behauptet oder untersucht. (Wenn man allerdings die Herleitung der Markov-Ungleichung betrachtet, kann es sich nur um eine Ungleichung handeln!)

Wie bei der Ungleichung von Tschebyscheff ist man an seltenen Ereignissen interessiert, daher wählt man in P (X ≥ b) die Schranke

b = p N + a mit a > 0.

Wie man an der folgenden Rechnung sehen wird, kann man die Terme vereinfachen, indem man a neu skaliert durch a = r · N. Insgesamt ist dann

b = p N + r N = (p + r) N.

Bei gegebenen Werten von p und N kann a nur sinnvolle Werte zwischen 0 und (1 - p) · N annehmen; folglich kann r nur Werte zwischen 0 und 1 - p annehmen.

Indem man r einführt, wird Ungleichung (2) zu Ungleichung (3) in Abbildung 11; hier sieht man, warum b neu skaliert wurde: die Potenz N muss in der Nullstellensuche der Ableitung nicht berücksichtigt werden.

Differenziert man die rechte Seite in (3) nach t und setzt die Ableitung gleich null, so muss Gleichung (4) gelten (dazu wird solange umgeformt, bis man eine in q und p möglichst symmetrische Darstellung findet).

Setzt man dies in die rechte Seite von (3) ein, erhält man – nach einigen Umformungen, die wieder versuchen q und p symmetrisch darzustellen – die Abschätzung (5).

Aufgaben:

1. Untersuchen Sie auf der rechten Seite von (3) in Abbildung 11 die Grenzwerte t → 0 und t → ∞. Folgern Sie daraus, dass die Differentiation nach t tatsächlich ein Minimum geliefert hat.

2. Leiten Sie die optimale Chernoff-Schranke für

P (X ≤ b)

her, indem Sie entweder von X zu -X oder von t zu -t übergehen.

Veranschaulichung der Herleitung der Chernoff-Schranke

Abbildung 12 soll die Vorgehensweise bei der Herleitung der Chernoff-Schranke für eine Binomial-verteilte Zufallsvariable X veranschaulichen. Dazu ist links oben die Binomialverteilung

B(N, p, k) mit N = 100, p = 0.5, k = 0, 1, ..., 100

gezeigt.

Die vertikalen Linien sind zunächst verwirrend, sind aber für das Verständnis der Herleitung hilfreich. Eingetragen sind:

1. Violett: Der Erwartungswert E(X) bei k = N · p = 50.
2. Grün: Rechts des Erwartungswertes eine Standardabweichung σ, die hier gleich 5 ist.
3. Rot: Eine Schranke b, die hier gleich E(X) + 3 · σ = 65 gewählt wurde.

Als Bildüberschrift ist im Diagramm links oben der optimale Wert für t eingetragen, der nach Gleichung (4) in Abbildung 11 berechnet wird (hier t0 = 0.619). Als Bildunterschrift wird der exakte Wert für die Wahrscheinlichkeit

P(X > b) = 0.000895

berechnet (hier wurde die Verteilungsfunktion der Binomialverteilung ausgewertet).

Die anderen 8 Diagramme beschreiben Transformationen der Zufallsvariable X der Art

X ↦ exp(t · X), mit t = 0.1, 0,3, ..., 1.5.

Die t-Werte sind jeweils in der Bildüberschrift angegeben.

Dass die Zufallsvariable transformiert wurde, ist auf den ersten Blick nicht erkennbar, da alle Verteilungen die identische Form besitzen. Wegen der logarithmischen Skalierung der x-Achse erhalten die Zufallsvariablen, die durch die Transformation X ↦ exp(t · X) entstehen, wieder die Glockenform. Achtet man auf die Beschriftung der x-Achse, erkennt man die Transformation der Zufallsvariable.

Abbildung 12: Die Binomialverteilung (links oben) und ihre Transformation X ↦ exp(t · X) für verschiedene Werte von t (andere 8 Diagramme). Ausführliche Erklärung im Text.

Die vertikalen Geraden müssen erklärt werden – sie sollen helfen die Abschätzung (1) in Abbildung 11 besser zu verstehen (diese Erklärungen beziehen sich ausschließlich auf die Darstellungen der transformierten Zufallsvariablen):

1. Grün eingetragen ist die Transformation der Standardabweichung der ursprünglichen Binomialverteilung, also μ + σ ↦ exp(t · (μ + σ)). Sie liegt scheinbar immer an der selben Stelle der Verteilung, beschreibt aber nicht mehr die Standardabweichung der transformierten Zufallsvariable exp(t · X). Sie ist eigentlich irrelevant, sie hilft aber das Verhalten der Standardabweichung der transformierten Zufallsvariable (blau) besser zu verstehen (siehe Erklärung unten).
2. Rot eingetragen ist die transformierte Schranke exp(t · b), die scheinbar immer an der selben Stelle der Verteilung liegt (logarithmische Darstellung beachten!).
3. Orange eingetragen ist der Erwartungswert E(exp(t · X)). Da die Transformation X ↦ exp(t · X) nichtlinear ist, liegt dieser Erwartungswert nicht mehr an dem x-Wert mit der höchsten Wahrscheinlichkeit; durch die in der logarithmischen Darstellung nicht mehr erkennbaren zunehmenden Streckung bei größeren x-Werten wird dieser Erwartungswert immer weiter nach rechts verschoben, wenn t größer wird.
4. Blau eingetragen sind E(exp(t · X)) ± σ (exp(t · X)), also die Standardabweichung der transformierten Zufallsvariable. Aufgrund der logarithmischen Skala ist allerdings nur bei t = 0.1 die linke Grenze erkennbar. (Bei t = 0.1 stimmen auch noch die transformierte Standardabweichung und die tatsächliche Standardabweichung nahezu überein.)

Als Bildunterschrift ist jeweils eingetragen die Wahrscheinlichkeit

P(X ≥ b),

wie sie sich nach Gleichung (3) in Abbildung 11 zu dem gegebenen t-Wert berechnet. Vergleicht man diese Werte mit dem exakten Wert (im ersten Diagramm), erkennt man, dass die beste Näherung bei t = 0.7 angenommen wird, was auch dem optimalen t0 = 0.619 am Nächsten kommt.

Insgesamt erkennt man an den Diagrammen:

1. Im Fall t → 0 wird die Abbildung X ↦ exp(t · X) zur identischen Abbildung und die Abschätzung (1) in Abbildung 11 wird zur gewöhnlichen Markov-Ungleichung.
2. Für große t (man muss hier nicht zum Grenzwert t → ∞ übergehen) wächst der Erwartungswert E(exp(t · X)) schneller als exp(t · b) und die Abschätzung (1) liefert die wertlose Aussage, dass P(X ≥ b) kleiner ist als eine Zahl, die größer ist als 1.
3. Zwischen diesen Werten gibt es ein optimales t0, das die beste Abschätzung für P(X ≥ b) liefert (siehe Gleichung (5) in Abbildung 11).
4. Und auch wenn t0 nicht exakt angenommen wird, kann man in einer Umgebung von t0 ähnlich gute Abschätzungen berechnen.

In der folgenden Abbildung 13 wird versucht, die Transformation X ↦ exp(t · X) für das optimale t = t0 zu veranschaulichen. Dazu werden alle Kombinationen von linearer und logarithmischer Skalierung der Achsen durchgespielt. Aufgetragen sind die Größen und vertikalen Linien wie in Abbildung 12.

1. Links oben: beide Achsen linear: Durch die Abbildung X ↦ exp(t · X) wird die Binomialverteilung so weit auseinandergezogen, dass nur noch wenige k-Werte erkennbar sind (und das auch nur, weil für das Histogramm die Strichbreite sehr groß gewählt wurde). Den rechten Balken kann man mit Hilfe von

exp(t0 · N) = exp(0.619 ·100) = 7.64 · 10²⁶

identifizieren. Auf der linearen Skala sind die vertikalen Linien nicht zu unterscheiden und man erkennt nur diejenige, die zuletzt gezeichnet wurde.

2. Rechts oben: x-Achse logarithmisch, y-Achse linear: Dieses Diagramm entspricht genau der Darstellung in Abbildung 12; wie dort beschrieben, verschleiert die logarithmische Skala die nichtlineare Streckung in x-Richtung. Relevant ist insbesondere die Lage der orangen und roten vertikalen Linie. Erstere beschreibt den Erwartungswert E(exp(t0 · X)), Letztere die Schranke exp(t0 · b). Dadurch dass jetzt große k-Werte überproportional gestreckt werden, hat sich der Erwartungswert weit nach rechts gegenüber dem Maximum (ursprünglich bei k = 50) verschoben. Der Erwartungswert liegt aber immer noch links der Schranke exp(t0 · b), so dass der Quotient

E(exp(t0 · X)) / exp(t0 · b) < 1.

3. Links unten: x-Achse linear, y-Achse logarithmisch: Im Vergleich zur ersten Abbildung sind jetzt die Wahrscheinlichkeiten der extremen Ereignisse besser zu erkennen.

4. Rechts unten: beide Achsen logarithmisch: Die k-Werte der Binomialverteilung, also die möglichen Werte der Zufallsvariable X, sind eigentlich äquidistant. Durch die Exponentialfunktion werden die Werte exponentiell auseinandergezogen. Die logarithmische Skalierung der x-Achse sorgt dafür, dass die k-Werte wieder äquidistant erscheinen. Durch die logarithmische Skalierung der y-Achse wird dann die Glockenform der Binomialverteilung zu einem parabelförmigen Verlauf.

Abbildung 13: Für das optimale t = t0 wird die transformierte Binomialverteilung X ↦ exp(t · X) viermal dargestellt, nämlich alle möglichen Kombinationen von linearen und logarithmischen Achsen.

In den folgenden Diagrammen 14 wird versucht, die Abbildung

t ↦ E(exp(t · X)) / exp(t · b) = M_X (t) / exp(t · b),

also die rechte Seite von (2) beziehungsweise (3) in Abbildung 11 darzustellen. Es wird also die Chernoff-Schranke in ihrer t-Abhängigkeit gezeigt; der Wert t0, wo die Funktion ein Minimum besitzt, liefert die optimale Chernoff-Schranke (Gleichung (5) in Abbildung 11).

Dazu wird wieder N = 100 und p = 0.5 gewählt und die drei b-Werte 55, 65 und 75; dies entspricht μ + σ, μ + 3 · σ und μ + 5 · σ. Umgerechnet in r-Werte aus b = (p + r) · N, erhält man r = 0.05, 0.15 und 0.25.

Im linken Diagramm ist die y-Achse linear skaliert, was hier aber ungeeignet ist, um den exponentiellen Anstieg anschaulich wiederzugeben; auch das Minimum ist bei großen b-Werten sehr breit und schwer zu erkennen. (Es ist aber an den gestrichelten vertikalen Linien erkennbar.)

Im rechten Diagramm ist die y-Achse logarithmisch skaliert, wodurch der Verlauf der Chernoff-Schranke besser nachvollziehbar wird.

Weiter erkennt man an den Diagrammen:

• Für t → 0 geht die Chernoff-Schranke gegen 1; dies gilt für jeden b-Wert. Da exp(0) = 1 wird auf der rechten Seite von (1) in Abbildung 11 lediglich 1/1 geteilt
• Für t > t0 steigt die Chernoff-Schranke exponentiell an; sobald sie einen Wert annimmt, der größer ist als 1, ist sie natürlich zur Abschätzung einer Wahrscheinlichkeit unbrauchbar.
• Für große Werte von b wird das Minimum immer breiter. Das heißt aber, dass es gar nicht so wichtig ist, den exakten Wert von t0 zu bestimmen, um eine "gute" Chernoff-Schranke zu erhalten. Wenn der Aufwand zur Bestimmung von t0 hoch wird, reicht es einen t-Wert in der Umgebung von t0 zu finden. Letzteres ist insbesondere bei anderen Verteilungen (als der Binomialverteilung) bedeutsam, da man das Minimum und die optimale Chernoff-Schranke nicht mehr explizit angeben kann.

Abbildung 14: Darstellung der t-Abhängigkeit der Chernoff-Schranke (mit linearer beziehungsweise logarithmischer Skalierung der y-Achse).

Warum liefert die momentenerzeugende Funktion eine so gute Schranke für die Wahrscheinlichkeiten seltener Ereignisse?

Wenn man die Abbildungen betrachtet, drängt sich eine Frage auf:

Warum liefert das Minimum von

E(exp(t · X)) / exp(t · b) = M_X (t) / exp(t · b)

die optimale Chernoff-Schranke?

Folgende Überlegung kann vielleicht eine Antwort liefern:

Man möchte eine Wahrscheinlichkeit der Art P(X ≥ b) abschätzen. Die Transformation X ↦ exp(t · X) streckt die Zufallsvariable, so dass bei einer anschließenden Berechnung des Erwartungswertes die großen Werte der Zufallsvariable stärker gewichtet werden – also genau diejenigen Werte von X, deren Wahrscheinlichkeit in P(X ≥ b) berechnet werden soll.

So gesehen, erscheint es günstig, möglichst große Werte für t zu verwenden oder gar zum Grenzwert t → ∞ überzugehen. Wählt man allerdings t zu groß, wird der Erwartungswert E(exp(t · X)) größer als die transformierte Schranke exp(t · b). Dann wird der Quotient

E(exp(t · X)) / exp(t · b) > 1

und ist für die Abschätzung einer Wahrscheinlichkeit unbrauchbar.

Für t → 0 geht der Quotient gegen 1 und ist auch unbrauchbar. Wenn es also einen optimalen Wert für t gibt, muss er sich zwischen diesen Grenzfällen befinden. Und wie die Auswertung von (3) in Abbildung 11 zeigt, gibt es ein eindeutiges Minimum des Quotienten.

Und wenn die Chernoff-Schranke tatsächlich eine sehr gute Näherung der exakten Wahrscheinlichkeit liefert (dies wird im nächsten Unterabschnitt untersucht), so heißt dies, dass die Abbildung

X ↦ exp(t0 · X)

die Zufallsvariable weit genug auseinanderzieht, so dass fast nur die gesuchten Werte von X zur Erwartungswert-Bildung beitragen.

Ausblick: Herleitung der Chernoff-Schranke für beliebige Verteilungen

Es mag vielleicht verwundern, warum die Chernoff-Schranke in Gleichung (5) in Abbildung 11 ausgerechnet in der dort angegebenen Form präsentiert wurde. Denn wenn man Gleichung (4) in (3) einsetzt, gibt es unzählige Möglichkeiten, die Chernoff-Schranke als Funktion von p, q, r und N auszudrücken. Die vorliegende Form wurde gewählt, weil diese Ausdruck einen Zusammenhang mit der Entropie suggeriert, die man verwenden kann, um einen Abstand zwischen Wahrscheinlichkeits-Verteilungen zu definieren. Diese Spur wird hier aber nicht weiterverfolgt.

Aber egal, wie man diese Schranke ausdrückt: es entsteht immer ein unhandlicher Term. Und wie man oben gesehen hat, ist das Minimum um t0 sehr breit, so dass man nicht darauf angewiesen ist, tatsächlich t0 zu bestimmen und damit die Chernoff-Schranke zu berechnen.

Für andere Verteilungen sucht man dann auch nach Schranken, die nicht optimal sind, aber zu einfacheren Termen führen. Dies geschieht, indem man zusätzlich zur Markov-Ungleichung weitere Abschätzungen einfließen lässt.

Anwendungen der Chernoff-Schranke

Eine typische Aufgabe zur Berechnung von Wahrscheinlichkeiten seltener Ereignisse

In Konzentrations-Ungleichungen: Die Tschebyscheff-Ungleichung wurden einige Anwendungen besprochen, in denen Wahrscheinlichkeiten berechnet wurden, die exakt nur mit großem Aufwand berechnet werden können und die sehr einfach mit der Tschebyscheff-Ungleichung abgeschätzt werden können. Eine dieser Aufgaben soll hier besprochen werden, um zu sehen, ob die Chernoff-Schranke eine bessere Abschätzung liefert.

Ein Glücksspiel wird 100 mal unabhängig voneinander wiederholt, wobei die Gewinn-Wahrscheinlichkeit p = 0.5 beträgt.

Naheliegend sind dann Fragen der Art:

1. Wie groß ist die Wahrscheinlichkeit dafür, 80 oder mehr Treffer zu erzielen?
2. Wie groß ist die Wahrscheinlichkeit für ein Extrem-Ereignis der Art: "die Anzahl der Treffer ist kleiner gleich 10 oder größer gleich 90"?
3. In welchem Intervall (mit Mittelpunkt k = 50) liegen mit 90 Prozent Wahrscheinlichkeit die Trefferzahlen?

Lösung:

1. Hier kann man sofort in die Chernoff-Schranke nach Gleichung (5) in Abbildung 11 einsetzen, man muss lediglich die Schranke b in r umrechnen. Es ist b = 80 und

(p + r) · N = b ⇒ r = 0.8 - 0.5 = 0.3.

Es folgt

P(X ≥ 80) ≤ 4.26 · 10^-9.

Der exakte Wert kann aus der Verteilungsfunktion der Binomialverteilung berechnet werden und liefert

P(X ≥ 80) = 5.58 · 10^-10.

Zum Vergleich: Die Schranke aus der Ungleichung von Tschebyscheff liefert:

P(X ≥ 80) ≤ 0.0139.

2. Wegen der Symmetrie kann man die Rechnung von 1. wiederholen, aber mit b = 90 und r = 0.4. Das Ergebnis muss dann mit 2 multipliziert werden.

Chernoff-Schranke:

P(X ≥ 90) + P(X ≤ 10) ≤ 2.07 · 10^-16.

Exakter Wert mit Binomialverteilung:

P(X ≥ 90) + P(X ≤ 10) = 3.06 · 10^-17.

Schranke aus der Ungleichung von Tschebyscheff:

P(X ≥ 90) + P(X ≤ 10) ≤ 0.016.

Fazit: An der ersten und zweiten Frage erkennt man sofort die offensichtlichen Unterschiede zwischen der Schranke aus der Tschebyscheff-Ungleichung und der Chernoff-Schranke. Die Ungleichung von Tschebyscheff ist leicht herzuleiten und ebenso leicht anzuwenden, liefert aber in dem hier gewählten Beispiel eine sehr schlechte Abschätzung für die Wahrscheinlichkeit von seltenen Ereignissen. Dagegen ist die Chernoff-Schranke deutlich schwieriger herzuleiten und zu berechnen, liefert aber Ergebnisse, die dem exakten Wert sehr nahe kommen.

3. Hier sieht man das Problem der Chernoff-Schranke wie sie hier behandelt wurde. Man hat zwar die optimale Chernoff-Schranke bestimmt, der Term, der dadurch entstanden ist, nämlich Gleichung (5) in Abbildung, kann nur schwer nach r aufgelöst werden. Für derartige Fragestellungen wäre man mit einer schlechteren Schranke zufrieden, die sich leichter handhaben lässt.

Das Problem ist daher nur graphisch oder numerisch lösbar, was aber mit einem sehr hohen Aufwand verbunden ist: dazu lässt man r einen geeigneten Bereich durchlaufen und prüft, wann die gegebene Wahrscheinlichkeit (näherungsweise) angenommen wird.

Bei der Ungleichung von Tschebyscheff ist es sehr leicht, zu einer gegebenen Wahrscheinlichkeit die zugehörige Schranke zu bestimmen.

Fazit: Möchte man Fragen wie 3. aus obigem Beispiel einfach behandeln, wird man nach anderen Varianten der Chernoff-Schranke suchen müssen. Damit ist gemeint, dass man nicht die optimale Schranke bestimmt, sondern nur eine Näherung, bei der man wie mit der Tschebyscheff-Schranke leicht zwischen einer Wahrscheinlichkeit und der zugehörigen Schranke umrechnen kann.

Vergleich zwischen der Chernoff-Schranke und der Tschebyscheff-Schranke

In den Abbildungen 8, 9 und 10 wurden Wahrscheinlichkeiten seltener Ereignisse exakt mit der Binomialverteilung berechnet und ihre Näherung mit der Ungleichung von Tschebyscheff berechnet. Man kann in die entsprechenden Abbildungen die Näherungen eintragen, die mit Hilfe der Chernoff-Schranke berechnet werden. Die entsprechenden Diagramme sind für N = 100 beziehungsweise N = 1000 und p = 0.5 in den Abbildung 15 bis 18 zu sehen.

Dargestellt sind jeweils Wahrscheinlichkeiten der Art

P(|X - E(X)| > b)

für eine Binomial-verteilte Zufallsvariable X. Da p = 0.5 gewählt ist, ist die Verteilung symmetrisch zum Erwartungswert und die Chernoff-Schranke aus (5) in Abbildung 11 kann mit 2 multipliziert werden, um die entsprechende Wahrscheinlichkeit zu approximieren; analog wurde mit der Tschebyscheff-Schranke verfahren. Die exakten Wahrscheinlichkeiten wurden mit der Verteilungsfunktion der Binomialverteilung berechnet.

Da für sehr seltene Ereignisse die Chernoff-Schranke sehr gut die exakten Wahrscheinlichkeiten approximiert, ist mit einer linearen Skalierung der y-Achse nur in einem sehr kleinen Bereich von b-Werten der Unterschied zwischen Näherung und exakter Wahrscheinlichkeit zu erkennen (es ist der Bereich bis etwa 3 Standardabweichungen). Daher wurde jedes Diagramm zusätzlich mit logarithmischer Skalierung der y-Achse erzeugt.

Abbildung 15: Darstellung von Wahrscheinlichkeiten der Art P(|X - μ| > b) für die Binomialverteilung mit N = 100 und p = 0.5 (blau) und Näherungen berechnet mit der Tschebyscheff-Ungleichung (rot) und der Chernoff-Schranke (grün).

Abbildung 16: Wie Abbildung 15, aber mit logarithmischer Skalierung der y-Achse.

Abbildung 17: Wahrscheinlichkeiten und Abschätzungen wie in Abbildung 15, aber mit N = 1000.

Abbildung 18: Abbildung 17 mit logarithmischer Skalierung der y-Achse.

Aufgabe: Versuchen Sie die dritte Frage aus dem Beispiel oben mit Hilfe von Abbildung 15 zu beantworten.