Information Theory/Some Preliminary Remarks on Two-Dimensional Random Variables

1. Information Theory
2. Information zwischen zwei wertdiskreten Zufallsgrößen
3. Some Preliminary Remarks on Two-Dimensional Random Variables

• Previous page
• Next page

• Previous page
• Next page

Einführungsbeispiel zur statistischen Abhängigkeit von Zufallsgrößen

Wir gehen vom Experiment „Würfeln mit zwei Würfeln” aus, wobei beide Würfel unterscheidbar sind. Die untere Tabelle zeigt als Ergebnis die ersten $N$ = 18 Wurfpaare dieses exemplarischen Zufallsexperiments:

• In Zeile 2 sind die Augenzahlen des roten Würfels ( $R$ ) angegeben. Der Mittelwert dieser begrenzten Folge $〈R_1, ... , R_{18}〉$ ist mit 3.39 etwas kleiner als der Erwartungswert E[R] = 3.5.
• Die Zeile 3 zeigt die Augenzahlen des blauen Würfels ( $B$ ). Die Folge $〈B_1, ... , B_{18}〉$ hat mit 3.61 einen etwas größeren Mittelwert als die unbegrenzte Folge ⇒ $\text{E}[B]$ = 3.5.
• Zeile 4 beinhaltet die Summe $S_ν = R_ν + B_ν$. Der Mittelwert der Folge $〈S_1, ... , S_{18}〉$ ist 3.39 + 3.61 = 7. Dieser ist hier (zufällig) gleich dem Erwartungswert $\text{E}[S] = \text{E}[R] + \text{E}[B]$.

Hinweis: Entsprechend der auf der nachfolgenden Seite erklärten Nomenklatur sind hier $R_ν$, $B_ν$ und $S_ν$ als Zufallsgrößen zu verstehen. Die Zufallsgröße $R_3$ = {1, 2, 3, 4, 5, 6} gibt beispielsweise die Augenzahl des roten Würfels beim dritten Wurf als Wahrscheinlichkeitsereignis an. Die Angabe „ $R_3$ = 6” sagt aus, dass bei der dokumentierten Realisierung der rote Würfel im dritten Wurf eine „6” gezeigt hat.

Nun stellt sich die Frage, zwischen welchen Zufallsgrößen es statistische Abhängigkeiten gibt:

• Setzt man faire Würfel voraus, so bestehen zwischen den Folgen $〈R〉$ und $〈B〉$ – ob begrenzt oder unbegrenzt – keine statistischen Bindungen: Auch wenn man $R_ν$ kennt, sind für $B_ν$ weiterhin alle möglichen Augenzahlen 1, ... , 6 gleichwahrscheinlich.
• Kennt man aber $S_ν$, so sind sowohl Aussagen über $R_ν$ als auch über $B_ν$ möglich. Aus $S_{11}$ = 12 (siehe obige Tabelle) folgt direkt $R_{11}$ = $B_{11}$ = 6 und die Summe $S_{15}$ = 2 zweier Würfel ist nur mit zwei Einsen möglich. Solche Abhängigkeiten bezeichnet man als deterministisch.
• Aus $S_7$ = 10 lassen sich zumindest Bereiche für $R_7$ und $B_7$ angeben: $R_7$ ≥ 4, $B_7$ ≥ 4. Möglich sind dann nur die drei Wertepaare ( $R_7$ = 4 ) ∩ ( $B_7$ = 6 ), ( $R_7$ = 5 ) ∩ ( $B_7$ = 5 ) sowie ( $R_7$ = 6 ) ∩ ( $B_7$ = 4 ). Hier besteht zwar kein deterministischer Zusammenhang zwischen den Zufallsgrößen $S_ν$ und $R_ν$ (bzw. $B_ν$), aber eine so genannte statistische Abhängigkeit.
• Solche statistische Abhängigkeiten gibt es für alle $S_ν$ ∈ {3, 4, 5, 6, 8, 9, 10, 11}. Ist dagegen die Summe $S_ν$ = 7, so kann daraus nicht auf $R_ν$ und $B_ν$ zurückgeschlossen werden. Für beide Würfel sind dann alle möglichen Augenzahlen (1, ... , 6) gleichwahrscheinlich. In diesem Fall bestehen auch keine statistischen Bindungen zwischen $S_ν$ und $R_ν$ bzw. $S_ν$ und $B_ν$.

Voraussetzungen und Nomenklatur

Im gesamten Kapitel 3 betrachten wir wertdiskrete Zufallsgrößen der Form

und verwenden folgende Nomenklatur:

• Die Zufallsgröße selbst wird stets mit einem Großbuchstaben bezeichnet, und der Kleinbuchstabe $x$ weist auf eine mögliche Realisierung der Zufallsgröße $X$ hin.
• Alle Realisierungen $x_μ$ (mit $μ$ = 1, ... , $M$) sind reellwertig. $M$ gibt den Symbolumfang (englisch: Symbol Set Size) von $X$ an. Anstelle von $M$ verwenden wir manchmal auch $|X|$.

Die Zufallsgröße $X$ kann zum Beispiel durch die Transformation $\Omega → X$ entstanden sein, wobei $\Omega$ für den Wahrscheinlichkeitsraum eines Zufallsexperiments steht. Die nachfolgende Grafik verdeutlicht eine solche Transformation:

Jedes Zufallsereignis $ω_i ∈ Ω$ wird eindeutig einem reellen Zahlenwert $x_μ ∈ X ⊂ ℝ$ zugeordnet. Im betrachteten Beispiel gilt für die Laufvariable 1 ≤ $μ$ ≤ 4, das heißt, der Symbolumfang beträgt $M$ = $|X|$ = 4. Die Abbildung ist aber nicht eineindeutig: Die Realisierung $x_3 ∈ X$ könnte sich im Beispiel aus dem Elementarereignis $ω_4$ ergeben haben, aber auch aus $ω_6$ (oder aus einem anderen der unendlich vielen, in der Grafik nicht eingezeichneten Elementarereignisse $ω_i$).

Oft verzichtet man auf die Indizierung sowohl der Elementarereignisse $ω_i$ als auch der Realisierungen $x_μ$. Damit ergeben sich beispielsweise folgende Kurzschreibweisen:

Mit dieser Vereinbarung gilt für die Wahrscheinlichkeiten der diskreten Zufallsgröße:

Wahrscheinlichkeitsfunktion und Wahrscheinlichkeitsdichtefunktion

Fasst man die $M$ Wahrscheinlichkeiten einer diskreten Zufallsgröße $X$ ⇒ Pr( $X$ = $x_μ$ ) ähnlich wie bei einem Vektor zusammen, so kommt man zur Wahrscheinlichkeitsfunktion (englisch: Probability Mass Function, PMF):

Das $μ$–te Element dieses „Vektors” gibt dabei die folgende Wahrscheinlichkeit an:

Im Buch „Stochastische Signaltheorie” haben wir mit der Wahrscheinlichkeitsdichtefunktion (WDF, englisch: Probability Density Function, PDF) eine ähnliche Beschreibungsgröße definiert und diese mit $f_X(x)$ bezeichnet. Zu beachten ist aber:

• Die PDF eignet sich eher zur Charakterisierung kontinuierlicher Zufallsgrößen, wie zum Beispiel bei einer Gaußverteilung oder einer Gleichverteilung. Erst durch die Verwendung von Diracfunktionen wird die PDF auch für diskrete Zufallsgrößen anwendbar.
• Die PMF liefert weniger Information über die Zufallsgröße als die PDF und kann zudem nur für diskrete Größen angegeben werden. Für die wertdiskrete Informationstheorie ist sie ausreichend.

Wir betrachten eine Wahrscheinlichkeitsdichtefunktion (abgekürzt WDF bzw. PDF) ohne großen Praxisbezug:

Für die diskrete Zufallsgröße gilt somit $x ∈ X$ = {–2, +1.5, +π} ⇒ Symbolumfang $M$ = $|X|$ = 3, und die Wahrscheinlichkeitsfunktion (PMF) lautet:

Man erkennt:

• Die PMF liefert nur Informationen über die Wahrscheinlichkeiten $\text{Pr}(x_1)$, $\text{Pr}(x_2)$, $\text{Pr}(x_3)$. Aus der PDF sind dagegen auch die möglichen Realisierungen $x_1$, $x_2$, $x_3$ der Zufallsgröße $X$ ablesbar.
• Die einzige Voraussetzung für die Zufallsgröße ist, dass sie reellwertig ist. Die möglichen Werte $x_μ$ müssen weder positiv, ganzzahlig, äquidistant noch rational sein.

Wahrscheinlichkeitsfunktion und Entropie

In der wertdiskreten Informationstheorie genügt im Gegensatz zu übertragungstechnischen Problemen schon die Kenntnis der Wahrscheinlichkeitsfunktion PX(X), zum Beispiel zur Berechnung der Entropie.

Die Entropie einer diskreten Zufallsgröße $X$ – also deren Unsicherheit für einen Beobachter – kann man mit der Wahrscheinlichkeitsfunktion $P_X(X)$ wie folgt darstellen:

Verwendet man den Logarithmus zur Basis 2, also $\log_2$ (...) = ld (...) ⇒ Logarithmus dualis, so wird der Zahlenwert mit der Pseudo–Einheit „bit” versehen. E[...] gibt den Erwartungswert an.

Beispielsweise erhält man

• für PX(X) = [0.2, 0.3, 0.5]:

• für PX(X) = [1/3, 1/3, 1/3]:

Das zweite Beispiel liefert das Maximum der Entropiefunktion für den Symbolumfang $M$ = 3. Für ein allgemeines $M$ lässt sich dieses Ergebnis beispielsweise wie folgt herleiten – siehe :

Diese Abschätzung (Jensens's Ungleichung) ist zulässig, da der Logarithmus eine konkave Funktion ist. Entsprechend Aufgabe A3.2 gilt:

Das Gleichheitszeichen ergibt sich nach der oberen Rechnung für gleiche Wahrscheinlichkeiten, also für $P_X(x_μ)$ = $\frac{1}{M} für alle $μ$. In der Aufgabe A3.3 soll der gleiche Sachverhalt unter Verwendung der Abschätzung nachgewiesen werden. Das Gleichheitszeichen gilt nur für $x$ = 1. Ist eine der M Wahrscheinlichkeiten $P_X(x_μ)$ der Wahrscheinlichkeitsfunktion $P_X(X)$ gleich 0 ist, so lässt sich für die Entropie eine engere Schranke angeben: Für das folgende Beispiel und die nächsten Seiten vereinbaren wir die folgende Nomenklatur: *Die Entropie $H(X)$ bezieht sich stets auf die tatsächliche Wahrscheinlichkeitsfunktion $P_X(X)$ der diskreten Zufallsgröße. Experimentell erhält man diese Größen erst nach $N → ∞$ Versuchen. *Ermittelt man die Wahrscheinlichkeitsfunktion aus einer endlichen Zufallsfolge, so bezeichnen wir diese mit $Q_X(X)$ und die daraus resultierende Entropie versehen wir mit dem Zusatz „ $N$ = ...”. *Diese Entropie–Näherung basiert nicht auf Wahrscheinlichkeiten, sondern nur auf den relativen Häufigkeiten. Erst für $N → ∞$ stimmt diese Näherung mit $H(X)$ überein. <div class="example"> Kommen wir auf unser Würfel–Experiment zurück. Die nachfolgende Tabelle zeigt die Wahrscheinlichkeitsfunktionen $P_R(R)$ und $P_B(B)$ für den roten und den blauen Würfel sowie die Näherungen $Q_R(R)$ und $Q_B(B)$, jeweils basierend auf dem Zufallsexperiment mit $N$ = 18 Würfen. Die relativen Häufigkeiten $Q_R(R)$ und $Q_B(B)$ ergeben sich aus den beispielhaften Zufallsfolgen vom Beginn dieses Kapitels. Für die Zufallsgröße $R$ gilt mit dem Logarithmus dualis (zur Basis 2): Der blaue Würfel hat natürlich die gleiche Entropie: $H(B)$ = $H(R)$ = 2.585 bit. Hier erhält man für die auf $N$ = 18 basierende Näherung einen etwas größeren Wert, da nach obiger Tabelle $Q_B(B)$ von der diskreten ( $M$=6 )–Gleichverteilung $P_B(B)$ weniger abweicht als $Q_R(R)$ von $P_R(R)$. Man erkennt aus den angegebenen Zahlenwerten, dass trotz des eigentlich viel zu kleinen Experimentparameters $N$ die Verfälschungen hinsichtlich der Entropie nicht sehr groß sind. Es soll nochmals erwähnt werden, dass bei endlichem $N$ stets gilt: =='"`UNIQ--h-4--QINU`"'Relative Entropie – Kullback–Leibler–Distanz == Wir betrachten die beiden Wahrscheinlichkeitsfunktionen $P_X(·)$ und $P_Y(·)$ über dem gleichen Alphabet $X$ = { $x_1$, $x_2$, ... , $x_M$ }, und definieren nun die '''relative Entropie''' (englisch: ''Informational Divergence'') zwischen diesen: Bei Verwendung des Logarithmus zur Basis 2 ist wieder die Pseudo–Einheit „bit” hinzuzufügen. Man bezeichnet D(PX || PY) auch als die '''Kullback–Leibler–Distanz''' (kurz KL–Distanz). Diese liefert ein Maß für die „Ähnlichkeit” zwischen den beiden Wahrscheinlichkeitsfunktionen $P_X(·)$ und $P_Y(·)$: In ähnlicher Weise lässt sich auch eine zweite Variante der Kullback–Leibler–Distanz angeben: Gegenüber der ersten Variante ist jede Funktion $P_X(·)$ durch $P_Y(·)$ ersetzt und umgekehrt. Da sich im allgemeinen $D(P_X || P_Y)$ und $D(P_Y || P_X)$ unterscheiden, ist der Begriff „Distanz” eigentlich irreführend. Wir wollen es aber bei dieser Namensgebung belassen. Wertet man die beiden obigen Gleichungen aus, so erkennt man folgende Eigenschaften: *Liegt genau die gleiche Verteilung vor ⇒ $P_Y(·) ≡ P_X(·)$, so ist $D(P_X || P_Y)$ = 0. In allen anderen Fällen ist $D(P_X || P_Y)$ > 0. Gleiches gilt für die zweite Variante $D(P_Y || P_X)$. *Gilt $P_X(x_μ)$ ≠ 0 und $P_Y(x_μ)$ = 0 (es genügt ein einziges und ein beliebiges $μ$), so ergibt sich für die Kullback–Leibler–Distanz $D(P_X || P_Y)$ ein unendlich großer Wert. *In diesem Fall ist $D(P_Y || P_X)$ nicht notwendigerweise ebenfalls unendlich. Diese Aussage macht nochmals deutlich, dass im allgemeinen $D(P_X || P_Y)$ ungleich $D(P_Y || P_X)$ sein wird. Auf der nächsten Seite werden diese beiden Definitionen an unserem Standardbeispiel ''Würfel–Experiment'' verdeutlicht. Gleichzeitig verweisen wir auf folgende Aufgaben: A3.4: Kullback–Leibler–Distanz zur Binomialverteilung Z3.4: Nochmals Kullback–Leibler–Distanz A3.5: Partitionierungsungleichung <div class="example"> Für unser Würfel–Experiment haben wir folgende Wahrscheinlichkeitsfunktionen $P_R(·)$ und $P_B(·)$ sowie deren Näherungen $Q_R(·)$ und $Q_B(·)$ definiert. Die Zufallsgröße $R$ bezeichnet hierbei die Augenzahl des roten Würfels und $B$ die Augenzahl des blauen Würfels. Die Näherungen $Q_R(·)$ und $Q_B(·)$ ergeben sich aus dem früher beschriebenen Experiment mit lediglich $N$ = 18 Doppelwürfen. *Da die Wahrscheinlichkeitsfunktionen $P_R(·)$ und $P_B(·)$ identisch sind, erhält man für die oben definierten Kullback–Leibler–Distanzen $D(P_R || P_B)$ und $D(P_B || P_R)$ jeweils 0. *Der Vergleich von $P_R(·)$, $Q_R(·)$ ergibt für die erste Variante der Kullback–Leibler–Distanz Hierbei wurde bei der vorzunehmenden Erwartungswertbildung die Tatsache ausgenutzt, dass wegen $P_R(r_1)$ = ... = $P_R(r_6)$ der Faktor 1/6 ausgeklammert werden kann. Da hier der Logarithmus zur Basis 2 verwendet wurde, ist die Pseudo–Einheit „bit” angefügt. *Für die zweite Variante der Kullback–Leibler–Distanz ergibt sich ein etwas anderer Wert: *Für den blauen Würfel erhält man $D(P_B || Q_B)$ ≈ 0.0283 bit und $D(Q_B || P_B)$ ≈ 0.0271 bit, also etwas kleinere KL–Distanzen, da sich die Approximation $Q_B(·)$ von $P_B(·)$ weniger unterscheidet als $Q_R(·)$ von $P_R(·)$. *Vergleicht man die Häufigkeiten $Q_R(·)$ und $Q_B(·)$, so erhält man $D(Q_R || Q_B)$ ≈ 0.0597 bit und $D(Q_B || Q_R)$ ≈ 0.0608 bit. Hier sind die Distanzen am größten, da die Unterschiede zwischen $Q_B$ und $Q_R$ größer sind als zwischen $Q_R$ und $P_R $oder zwischen $Q_B$ und $P_B$. <div style="clear:both;"> </div> </div> =='"`UNIQ--h-5--QINU`"'Verbundwahrscheinlichkeit und Verbundentropie == Für den Rest von Kapitel 3 betrachten wir stets zwei diskrete Zufallsgrößen $X$ = { $x_1$, $x_2$, ... , $x_M$ } und $Y$ = { $y_1$, $y_2$, ... , $y_K$ }, deren Wertebereiche nicht notwendigerweise übereinstimmen müssen. Das heißt: $K ≠ M$ (in anderer Notation: $|Y| ≠ |X|$) ist durchaus erlaubt. Die Wahrscheinlichkeitsfunktion hat somit eine $K × M$–Matrixform mit den Elementen Als Kurzschreibweise verwenden wir $P_{XY}(X, Y)$, wobei $XY$ als neue Zufallsgröße zu interpretieren ist, die sowohl die Eigenschaften von $X$ als auch diejenigen von $Y$ beinhaltet. <div class="definition"> Die '''Verbundentropie''' (englisch: ''Joint Entropy'') lässt sich als ein Erwartungswert mit der 2D–Wahrscheinlichkeitsfunktion $P_{XY}(X, Y)$ wie folgt darstellen: Im Folgenden verwenden wir durchgehend den Logarithmus zur Basis 2 ⇒ $\log(x) → \log_2(x)$ = $\text{ld}(x)$ ⇒ Logarithmus dualis. Der Zahlenwert ist somit mit der Pseudo–Einheit „bit” zu versehen. Allgemein kann für die Verbundentropie die folgende '''obere Schranke''' angegegeben werden: Diese Ungleichung drückt folgenden Sachverhalt aus: *Das Gleichheitszeichen gilt nur für den Sonderfall statistisch unabhängiger Zufallsgrößen, wie im Beispiel C auf der nächsten Seite anhand der Zufallsgrößen $R$ und $B$ demonstriert wird. Hierbei bezeichnen $R$ und $B$ die Augenzahlen eines roten und eines blauen Würfels. *Gibt es dagegen statistische Abhängigkeiten wie im Beispiel D zwischen den Zufallsgrößen $R$ und $S$ = $R + B$, so gilt in obiger Gleichung das „<”–Zeichen: $H(RS) < H(R) + H(S)$. In den Beispielen wird auch gezeigt, in wie weit sich die Verbundentropien $H(RB)$ und $H(RS)$ ändern, wenn man beim Würfel–Experiment nicht unendlich viele Wurfpaare ermittelt, sondern lediglich $N$ = 18.