Die Entropie einer Faltung von Wahrscheinlichkeitsverteilungen

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Spezielle Wahrscheinlichkeitsverteilungen
      • Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen
      • Interpretation der Zufallsexperimente Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen durch Pfade auf einem Gitter
    • Die Entropie
      • Die Entropie einer diskreten Wahrscheinlichkeitsverteilung: Definition und einfache Beispiele
      • Entropien und gegenseitige Information bei Wartezeitproblemen
      • Die Entropie einer Faltung von Wahrscheinlichkeitsverteilungen

Ähnliche Wartezeitprobleme wie hier werden in Wartezeitprobleme beim Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen und Interpretation der Zufallsexperimente Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen durch Pfade auf einem Gitter diskutiert. Beide Artikel verwenden Kenntnisse zur geometrischen Verteilung (siehe Spezielle Wahrscheinlichkeitsverteilungen: die geometrische Verteilung).

Der letzte Abschnitt verwendet Kenntnisse aus Eigenschaften von konvexen Funktionen und die Jensensche Ungleichung.

Einführung und Bezeichnungen

An einem speziellen Beispiel soll diskutiert werden, wie man die Entropie bei einer Faltung von Wahrscheinlichkeitsverteilungen berechnet. Dazu wird die Summe

S₂ = X₁ + X₂

von zwei unabhängigen Zufallsvariablen X₁ und X₂ betrachtet, die bei folgendem Zufallsexperiment entstehen:

• In einer Urne befinden sich Treffer und Nieten.
• Es werden nacheinander Lose aus der Urne gezogen; die Lose werden wieder in die Urne zurückgelegt ("Ziehen mit Zurücklegen").
• Die Trefferwahrscheinlichkeit betrage p, die Wahrscheinlichkeit für eine Niete q = 1 - p.
• Die Zufallsvariable X₁ beschreibe die Anzahl der Nieten bis zum ersten Treffer.
• Die Zufallsvariable X₂ beschreibe die Anzahl der Nieten vom ersten bis zum zweiten Treffer.
• Die Zufallsvariable S₂ = X₁ + X₂ beschreibt dann die Anzahl der Nieten bis zum zweiten Treffer.

Die drei Zufallsvariablen X₁, X₂ und S₂ können jeweils die Werte 0, 1, 2, ... annehmen.

Die beiden Zufallsvariablen X₁ und X₂ besitzen die gleiche Verteilung, nämlich eine geometrische Verteilung, die unten hergeleitet wird. Als Summe von unabhängigen Zufallsvariablen berechnet sich die Verteilung von S₂ dann durch die Faltung der Verteilungen von X₁ und X₂.

Untersucht werden soll, wie die Entropie der Verteilung von S₂ mit den Entropien der Verteilungen von X₁ und X₂ zusammenhängt.

Die Entropie wurde eingeführt (siehe Die Entropie einer diskreten Wahrscheinlichkeitsverteilung: Definition und einfache Beispiele) als eine Größe, welche die Unsicherheit über den Ausgang eines Zufallsexperimentes beschreibt. Qualitativ sollte daher klar sein, dass die Unsicherheit über die Voraussage der Zufallsvariablen X₁ und X₂ größer ist als über S₂. Denn jetzt verschmelzen mehrere Kombinationen von Werten von X₁ und X₂ zum gleichen Summenwert S₂.

Die hier angestellten Überlegungen hängen natürlich nicht von der Wahl der Wahrscheinlichkeitsverteilung der Zufallsvariablen X₁ und X₂ ab (hier geometrische Verteilungen), sondern sollten für jede Verteilung gelten. Im letzten Abschnitt wird angedeutet, wie man diese allgemeinere Aussage, nämlich

H[S₂] ≤ H[X₁] + H[X₂] für S₂ = X₁ + X₂,

wobei X₁ und X₂ unabhängig voneinander sind, zeigt:

• Geht man von einer Zufallsvariable X zu einer vergröberten Zufallsvariable Y über, so kann dabei die Entropie nur abnehmen, H[X] ≥ H[Y].
• Dies zeigt man mit Hilfe der Log-Summen-Ungleichung, die eine Anwendung der Jensenschen Ungleichung ist.
• Um die Jensensche Ungleichung anzuwenden, benötigt man die Konvexität der Funktion f(x) = x·ln x.

Somit beruht die Aussage H[S₂] ≤ H[X₁] + H[X₂] letztlich auf der Konvexität der Funktion f(x) = x·ln x, die verwendet wird, um in der Entropie die Wahrscheinlichkeiten der möglichen Werte einer Zufallsvariable zu bewerten.

Die Zufallsvariablen zu den Wartezeitproblemen und ihre Verteilungen

Darstellung als Pfad im Gitter

Ähnlich wie in Interpretation der Zufallsexperimente Ziehen mit Zurücklegen und Ziehen ohne Zurücklegen durch Pfade auf einem Gitter gezeigt, kann man die Zufallsvariablen X₁ und X₂ und ihre Summe

S₂ = X₁ + X₂

sehr gut mit Hilfe von Pfaden in einem Gitter veranschaulichen. Abbildung 1 zeigt dazu die Vorgehensweise:

• Man startet den Pfad im Ursprung des Koordinatensystem.
• Wird eine Niete gezogen, geht man einen Schritt nach rechts →; wird ein Treffer gezogen, geht man einen Schritt nach oben ↑.
• Zu einem gegebenen Pfad liest man den Wert von X₁ als die Anzahl der Schritte nach rechts bei y = 0 ab; den Wert von X₂ als die Anzahl der Schritte nach rechts bei y = 1.
• Der Wert von S₂ ist die x-Koordinate des Punktes bei y = 1, an dem ein Schritt nach oben stattfindet.

In Abbildung 1 wird der Pfad zu 0010001 gezeigt, also für

X₁ = 2, X₂ = 3, S₂ = 5.

Abbildung 1: Darstellung des Ergebnisses beim Ziehen mit Zurücklegen als Pfad im Gitter.

Insbesondere kann man die hier angestellten Überlegungen leicht verallgemeinern für Summen der Art

S_N = X₁ + X₂ + ... + X_N.

Die Abzählprobleme, die sich dann ergeben, lassen sich leicht an der entsprechenden Abbildung analysieren; diese Überlegungen sollen hier aber nicht angestellt werden.

Die Verteilungen der Zufallsvariablen

Mit Hilfe von Abbildung 1 kann man sofort die Verteilungen der Zufallsvariablen X₁, X₂ und S₂ berechnen. Mit "Verteilungen" ist gemeint, dass man Wahrscheinlichkeiten der Art

P(X = n), n = 0, 1, 2, ...

angibt, wobei X für die Zufallsvariable steht und n den Bereich ihrer Werte durchlaufen kann; hier können die Zufallsvariablen jeweils die Werte n = 0, 1, 2, ... annehmen.

• Damit das Ereignis "X₁ = n" eintritt, müssen zuerst n Nieten und anschließend ein Treffer gezogen werden, man erhält somit Gleichung (1) in Abbildung 2.
• Das Ereignis "X₂ = n" ist unabhängig von der Vorgeschichte – die Zählung der Nieten beginnt lediglich nach dem ersten Treffer und man zählt die Nieten bis zum zweiten Treffer. Man erhält daher die identischen Wahrscheinlichkeiten wie für "X₁ = n" (siehe Gleichung (2) in Abbildung 2)
• Die Berechnung der Verteilung von S₂ wird als Faltung der Verteilungen von X₁ und X₂ angesetzt (siehe Gleichung (3)).
• Aus den Potenzgesetzen und Abzählen der Summanden erhält man die Verteilung (siehe Gleichung (4) und (5)).

Abbildung 2: Die Verteilungen der Zufallsvariablen X₁, X₂ und ihrer Summe S₂. Die Verteilung von S₂ berechnet sich durch Faltung der Verteilungen von X₁ und X₂.

Man kann das Ergebnis aus Gleichung (5) auch ohne die Faltung durch elementares Abzählen berechnen: Damit das Ereignis "S₂ = n" eintritt, muss n+2 mal gezogen werden, wobei insgesamt 2 Treffer eintreten. Der zweite Treffer muss sich am Ende der Folge befinden, der erste Treffer kann sich an einer beliebigen Stelle innerhalb der 01-Folge befinden. Dann gibt es n+1 Möglichkeiten, wo der erste Treffer plaziert werden kann. Da aber jede Folge aus zwei Treffern und n Nieten besteht, hat sie die Wahrscheinlichkeit p²·qⁿ, woraus sich auch Gleichung (5) ergibt.

Aufgaben:

1. Zeigen Sie, dass die Verteilung der Zufallsvariable X₁ normiert ist (Gleichung (3) in Abbildung 3) und den Erwartungswert

E[X₁] = q / p = (1 - p) / p

besitzt (Gleichung (4) in Abbildung 3).

2. Zeigen Sie die Verteilung der Zufallsvariable S₂ normiert ist (Gleichung (6) in Abbildung 3) und den Erwartungswert

E[S₂] = 2·q / p = 2·(1 - p) / p

besitzt (Gleichung (7) in Abbildung 3).

Verwenden Sie dazu die Formeln für die geometrische Reihe (Gleichung (1 - 3) in Abbildung 3).

Abbildung 3: Die Formeln zur Berechnung der geometrischen Reihe und ihre Anwendung auf die Zufallsvariablen X₁ und S₂ (Normierung und Erwartungswert).

Die Abbildungen 4 und 5 zeigen die Verteilungen der Zufallsvariablen X₁ und S₂ für verschiedene Werte der Trefferwahrscheinlichkeit p. Jeweils blau eingetragen ist der Erwartungswert (für p = 0.1 liegt er außerhalb des dargestellten Bereichs der Werte für n). Die Skalierung wurde für alle Diagramme identisch gewählt, um sie untereinander besser vergleichen zu können.

Man erkennt an den Abbildungen sofort das Verhalten in den Grenzfällen p → 0 und p → 1:

1. Geht die Trefferwahrscheinlichkeit p gegen null, so muss man "unendlich lange" auf den ersten Treffer warten und daher sind alle Längen n der Serien von Nieten nahezu gleich wahrscheinlich: Die Verteilung von X₁ nähert sich einer "Gleichverteilung" auf den natürlichen Zahlen (Gleichverteilung ist hier in Anführungsstrichen geschrieben, weil es eine Gleichverteilung auf einer unendlichen Menge nicht geben kann). Der Erwartungswert von X₁ geht gegen unendlich.
2. Geht dagegen die Trefferwahrscheinlichkeit gegen eins, so wird sofort ein Treffer eintreten und die Verteilung von X₁ ist bei n = 0 konzentriert. Der Erwartungswert von X₁ geht gegen null.

Abbildung 4: Die Verteilung der Zufallsvariable X₁ für verschiedene Werte der Trefferwahrscheinlichkeit p. Zusätzlich eingetragen ist jeweils der Erwartungswert (blau). Alle Diagramme sind identisch skaliert, um die Verteilungen besser miteinander vergleichen zu können.

Abbildung 5: Die Verteilung der Zufallsvariable S₂ für verschiedene Werte der Trefferwahrscheinlichkeit p sowie ihr Erwartungswert (blau). Für p = 0.1 liegt der Erwartungswert außerhalb des dargestellten Bereichs der Werte von n. Die Skalierung der Achsen ist wie in Abbildung 4 gewählt.

Aufgabe:

1. Erläutern Sie das qualitative Verhalten der Verteilung von S₂.
2. Warum besitzt die Verteilung (für kleine Werte von p) ein Maximum?
3. Diskutieren Sie die Grenzwerte p → 0 und p → 1.

Die Berechnung der Entropien

Da jetzt die wichtigsten Eigenschaften der Zufallsvariablen X₁ und S₂ bekannt sind, ist es leicht ihre Entropie zu berechnen und deren Eigenschaften zu ermitteln. Die Entropie wird berechnet wie in Die Entropie einer diskreten Wahrscheinlichkeitsverteilung: Definition und einfache Beispiele. Da hier unabhängige Zufallsvariablen betrachtet werden, sind auch die Überlegungen aus Die Additivität der Entropie bei unabhängigen Zufallsvariablen relevant.

Im Folgenden werden berechnet:

• die Entropie H[X₁] der Zufallsvariable X₁,
• die gemeinsame Entropie H(X₁, X₂) sowie
• die Entropie H[S₂] der Zufallsvariable S₂ = X₁ + X₂.

Abbildung 6 zeigt dazu die Definitionen, die hier verwendet werden (Entropie einer Wahrscheinlichkeitsverteilung beziehungsweise Zufallsvariable, gemeinsame Entropie und bedingte Entropie).

Abbildung 6: Die Definitionen von Entropie, gemeinsamer Entropie und bedingter Entropie.

Die Entropie der Zufallsvariable X1

In die Berechnung der Entropie H[X₁] der Zufallsvariable X₁ gehen nur die Wahrscheinlichkeiten ein, mit der die Werte der Zufallsvariable angenommen werden, aber nicht die Werte der Zufallsvariable. Das heißt, dass man bei einer Verschiebung der Werte von X₁ das gleiche Resultat erhält. Erst wenn man – was weiter unten geschehen wird – die Entropie als Funktion des Erwartungswertes ausdrückt, wird diese Verschiebung relevant.

Bei der Verteilung der Werte von X₁ handelt es sich um eine geometrische Verteilung, für die die Entropie explizit berechnet werden kann. Abbildung 7 zeigt:

• Die Berechnung der Entropie H[X₁] aus der Definition der Entropie (siehe Gleichung (1 - 3)). In die Berechnung gehen die Formeln für die geometrische Reihe ein (siehe Abbildung 3, Gleichung (1)).
• Mit Hilfe der Rechenregeln für den Logarithmus kann die Entropie auf verschiedene Arten dargestellt werden (siehe Gleichung (4)).
• Da sich der Erwartungswert μ = E[X₁] eindeutig durch p ausdrücken lässt und umgekehrt, kann man die Entropie H[X₁] als Funktion von μ darstellen (Gleichung (5 - 6))

Abbildung 7: Die Berechnung der Entropie der Zufallsvariable X₁ in verschiedenen Darstellungen: Entweder als Funktion der Trefferwahrscheinlichkeit p oder als Funktion des Erwartungswertes μ = '''E'''[X₁].

Abbildung 8 zeigt die Entropie H[X₁] als Funktion der Trefferwahrscheinlichkeit (links) sowie ihre Ableitung nach p (rechts).

Abbildung 8: Die Entropie der Zufallsvariable X₁ als Funktion der Trefferwahrscheinlichkeit p sowie ihre Ableitung nach p.

Abbildung 9 zeigt (analog zu Abbildung 8) die Entropie H[X₁] als Funktion des Erwartungswertes μ = E[X₁] (links) sowie ihre Ableitung nach μ (rechts).

Abbildung 9: Die Entropie der Zufallsvariable X₁ als Funktion des Erwartungswertes μ = '''E'''[X₁] sowie ihre Ableitung nach μ.

Abbildung 10 zeigt die Funktionsterme für die Darstellungen von H[X₁], die Ableitungen und die relevanten Grenzwerte.

Abbildung 10: Eigenschaften der Entropie der Zufallsvariable X₁: Darstellung als Funktion der Trefferwahrscheinlichkeit p beziehungsweise des Erwartungswertes μ = '''E'''[X₁], Grenzwerte und Ableitungen.

Stellt man die Entropie H[X₁] wie in Gleichung (1) in Abbildung 10 dar, so erhält man zwei Summanden. In Abbildung 11 werden diese beiden Summanden (blau und grün) zusammen mit der Entropie (rot) als Funktion von p dargestellt.

Abbildung 11: Die Entropie der Zufallsvariable X₁ als Funktion der Trefferwahrscheinlichkeit p (rot) und ihre Zerlegung in zwei Anteile (blau und grün).

Aufgaben:

1. Die Berechnungen in Abbildungen 10 sind lückenhaft und zeigen oftmals nur die Ergebnisse. Ergänzen Sie die fehlenden Berechnungen.

2. Diskutieren Sie, welche Eigenschaften der Entropie man aus den Diagrammen mit den unterschiedlichen geometrischen Verteilungen in Abbildung 4 (zumindest qualitativ) ablesen kann.

Die gemeinsame Entropie der Zufallsvariablen X1 und X2

Die gemeinsame Entropie H(X₁, X₂) der Zufallsvariablen X₁ und X₂ wird aus der gemeinsamen Verteilung berechnet (siehe Gleichung (1) in Abbildung 12). Aufgrund der Unabhängigkeit der Zufallsvariablen X₁ und X₂ faktorisiert die Wahrscheinlichkeit:

P(X₁ = n, X₂ = m) = P(X₁ = n)·P(X₂ = m).

Und da die Verteilungen von X₁ und X₂ identisch sind, addieren sich die Entropien:

H(X₁, X₂) = H[X₁] + H[X₂] = 2·H[X₁].

Die ausführliche Rechnung ist in Abbildung 12, Gleichung (3 - 7) gezeigt.

Somit können alle Eigenschaften der gemeinsamen Entropie H(X₁, X₂) aus der Entropie H[X₁] abgelesen werden.

Abbildung 12: Die Berechnung der gemeinsamen Entropie der Zufallsvariablen X₁ und X₂.

Die Entropie der Zufallsvariable S2

Die Zufallsvariable S₂ beschreibt die Anzahl der Nieten bis zum zweiten Treffer. Ihre Verteilung wurde oben diskutiert und ist zusammen mit ihrem Erwartungswert in Abbildung 13, Gleichung (1), nochmals gezeigt.

Die Berechnung der Entropie H[S₂] erfolgt in ähnlichen Schritten wie die Berechnung von H[X₁]; die Gleichungen (2 - 7) in Abbildung 13 zeigen die Vorgehensweise:

• Da die Wahrscheinlichkeit P(S₂ = n) aus drei Faktoren besteht, wird der natürliche Logarithmus ln P(S₂ = n) durch drei Summanden dargestellt (Gleichung (2) und (3)).
• Für die Entropie H[S₂] entstehen somit drei Summanden, die mit H₁, H₂ und H₃ bezeichnet werden (Gleichung (4)).
• Diese drei Summanden werden als Funktion der Trefferwahrscheinlichkeit p dargestellt.
• Für H₁ ergibt sich eine unendliche Summe, die nicht explizit berechnet werden kann (Gleichung (5)). Für die Abbildungen 14 und 15 wird die Summe näherungsweise berechnet.
• Die unendlichen Summen, die bei der Berechnung von H₂(p) und H₃(p) entstehen, können mit Hilfe der Normierung der Wahrscheinlichkeiten beziehungsweise dem Erwartungswert explizit berechnet werden (Gleichung (6) und (7)).
• Das Endergebnis für die Entropie H[S₂] ist dann in Gleichung (8) dargestellt (hier wurde q nicht durch 1 - p ausgedrückt, um die Ähnlichkeit mit den Termen bei der Berechnung von H[X₁] zu betonen).
• Man erkennt, dass die Summe H₂(p) + H₃(p) mit der gemeinsamen Entropie der Zufallsvariablen X₁ und X₂ übereinstimmt (Gleichung (9)), wodurch sich die Entropie H[S₂] wie in Gleichung (10) darstellen lässt.

Abbildung 13: Die Berechnung der Entropie der Zufallsvariable S₂, die als Summe von drei Termen H₁, H₂ und H₃ geschrieben wird und ihr Zusammenhang mit der gemeinsamen Entropie H(X₁, X₂).

In den Abbildungen 14 und 15 wird versucht die Berechnungen aus Abbildung 13 graphisch darzustellen. Dazu werden die relevanten Funktionen in ihrer Abhängigkeit von der Trefferwahrscheinlichkeit p dargestellt.

In Abbildung 14:

• Rot: Die gemeinsame Entropie H(X₁, X₂). Sie ergibt sich aus der Entropie H[X₁] (siehe Abbildung 8 links und Abbildung 11), indem man sie um den Faktor 2 streckt. Die gemeinsame Entropie H(X₁, X₂) setzt sich wie H[X₁] aus zwei Anteilen zusammen (siehe Gleichung (1) in Abbildung 10):
• Blau: Die Funktion -2·ln p.
• Grün: Die Funktion (-2q·ln q) / p (siehe erster Summand in Gleichung (1) in Abbildung 10).

In Abbildung 15:

• Türkisfarben: Die Entropie H[S₂] der Zufallsvariable S₂ = X₁ + X₂. Sie lässt sich ausdrücken durch H[S₂] = H(X₁, X₂) + H₁(p).
• Rot: Nochmals die gemeinsame Entropie H(X₁, X₂).
• Orange: Die Funktion H₁(p) nach Gleichung (5) in Abbildung 13.

Abbildung 14: Die gemeinsame Entropie der Zufallsvariablen X₁ und X₂ (rot) für verschiedene Werte der Trefferwahrscheinlichkeit p und die beiden Bestandteile -2·ln p (blau) und (-2q·ln q) / p (grün).

Abbildung 15: Die Entropie der Zufallsvariable S₂ (türkisfarben) für verschiedene Werte der Trefferwahrscheinlichkeit p, die man als Summe des roten und des orangefarbenen Graphen darstellen kann. (Rot: Gemeinsame Entropie H(X₁, X₂). Orange: Die unendliche Summe H₁(p) nach Gleichung (5) in Abbildung 13.

Aufgabe:

Diskutieren Sie, welche Eigenschaften der Entropie H[S₂] man aus den Diagrammen in Abbildung 5 ablesen kann.

Verallgemeinerung

Die bisherigen Überlegungen haben sich auf die spezielle Zufallsvariable S₂ bezogen, die aus der Summe von zwei geometrisch verteilten, unabhängigen Zufallsvariablen X₁ und X₂ entsteht. An Abbildung 15 und in den Gleichungen (5) und (10) in Abbildung 13 kann man erkennen, dass die Entropie von S₂ kleiner oder gleich der gemeinsamen Entropie von X₁ und X₂ ist (denn die Funktion H₁(p) kann nicht positiv werden):

H[S₂] ≤ H(X₁, X₂) = H(X₁) + H(X₂).

(Die zweite Gleichheit gilt wegen der Unabhängigkeit der Zufallsvariablen X₁ und X₂.)

Im Folgenden soll skizziert werden, wie man zeigt, dass diese Aussage nicht von der speziellen Wahl der geometrischen Verteilung abhängt, sondern für jede Summe von zwei unabhängigen Zufallsvariablen gilt.

Dazu zeigt Abbildung 16 ein anderes Beispiel, das helfen soll den Zusammenhang zwischen der Entropie einer Summe S₂ = X₁ + X₂ und der gemeinsamen Entropie H(X₁, X₂) besser zu verstehen: Aufgetragen sind die 36 Ergebnisse beim zweimaligen Werfen eines Würfels. Bildet man die Paare (x₁, x₂) umkehrbar eindeutig auf die Werte einer Zufallsvariable Z₂ ab, etwa indem man bildet:

z₂ = x₁ + 6·(x₂ - 1),

so nimmt die Zufallsvariable Z₂ die Werte 1, 2, ..., 36 an. Und die Entropien H(X₁, X₂) und H[Z₂] stimmen überein.

Durch die Bildung der Summe S₂ = X₁ + X₂ entsteht eine Zufallsvariable, die gegenüber Z₂ vergröbert ist. Das soll heißen, dass mehrere Ergebnisse von Z₂ zu einem Ergebnis von S₂ zusammengefasst werden, nämlich jeweils die Ergebnisse, die sich in Abbildung 16 auf einer Nebendiagonale befinden (eingetragen sind die Nebendiagonalen zu S₂ = 4 und S₂ = 7 in blau beziehungsweise grün).

Abbildung 16: Darstellung der Ergebnisse für das Zufallsexperiment "Werfen von 2 Würfeln". Jeweils auf den Nebendiagonalen liegen Punkte mit gleicher Augensumme s₂ = x₁ + x₂; hier für s₂ = 4 (blau) und s₂ = 7 (grün).

Wenn also gezeigt werden soll, dass

H[S₂] ≤ H(X₁, X₂)

für unabhängige Zufallsvariablen X₁ und X₂, so reicht es zu zeigen, dass die Entropie einer Zufallsvariable beim Übergang zu einer vergröberten Zufallsvariable nur abnehmen kann. Die entsprechende Überlegung ist in Abbildung 17 gezeigt:

• Man geht von einer Zufallsvariable X aus, die die Werte 0, 1, ..., N annehmen kann (links oben).
• Man bildet die denkbar einfachste Vergröberung zu einer Zufallsvariable Y: Wenn X die Werte 0 oder 1 annimmt, dann nimmt Y den Wert 1 an. Die zugehörigen Wahrscheinlichkeiten werden addiert. Alle anderen Werte und Wahrscheinlichkeiten bleiben unverändert (siehe Gleichung (1) rechts).
• Für die Zufallsvariablen X und Y werden die Entropien berechnet.
• Die Behauptung, dass die vergröberte Zufallsvariable eine kleinere Entropie besitzt ist in diesem speziellen Fall gleichwertig zu Gleichung (2).

Abbildung 17: Änderung der Entropie einer Zufallsvariable bei Vergröberung. Dargestellt wird der einfachste Fall einer Vergröberung: zwei Werte einer Zufallsvariable X werden zu einem Wert der Zufallsvariable Y verschmolzen.

Gleichung (2) in Abbildung 17 ist ein Spezialfall der sogenannten Log-Summen-Ungleichung, die in Abbildung 18, Gleichung (2), gezeigt ist. Der Beweis der Log-Summen-Ungleichung beruht auf der Jensenschen Ungleichung (siehe Gleichung (3) sowie ihre ausführliche Diskussion in Eigenschaften von konvexen Funktionen und die Jensensche Ungleichung). Um die Log-Summen-Ungleichung zu beweisen, muss man für die Werte der λ_i und x_i in Gleichung (3) spezielle Werte wählen. Die Vorgehensweise ist in den Gleichungen (4 - 6) gezeigt.

Insgesamt erkannt man, dass de Log-Summen-Ungleichung auf der Konvexität der Funktion f(x) = x·ln x beruht. Und somit ist auch die die Behauptung

H[S₂] ≤ H(X₁, X₂)

letztlich darauf zurückgeführt, dass die Funktion f(x) = x·ln x eine konvexe Funktion ist. Diese Funktion f(x) wird verwendet, um die Wahrscheinlichkeiten P(X = x) der Werte x einer Zufallsvariable X zu gewichten, wenn die Entropie H[X] einer Zufallsvariable X berechnet wird.

Abbildung 18: Formulierung und Beweis der Log-Summen-Ungleichung.

Aufgaben:

1. Im Beweis in Abbildung 18 wird nicht auf die Grenzfälle eingegangen, wenn einige der Zahlen a_i beziehungsweise b_i gleich null sind. Wie muss man den Beweis dann ergänzen?

2. Man kann die Aussage der Log-Summen-Ungleichung sogar noch verschärfen: Die Gleichheit in (2) von Abbildung 18 gilt genau dann, wenn alle Quotienten a_i/b_i den gleichen Wert annehmen, also a_i/b_i = const. Beweisen Sie diese Verschärfung der Log-Summen-Ungleichung.