Informationstheorie/Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(40 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 6: Zeile 6:
 
}}
 
}}
  
Im Mittelpunkt dieses dritten Kapitels steht die ''Transinformation'' $I(X; Y)$ zwischen zwei Zufallsgrößen $X$ und $Y$, wofür auch andere Begriffe wie ''Mutual Information'' oder ''gegenseitige Entropie'' üblich sind. Bei statistischer Abhängigkeit ist $I(X; Y)$ kleiner als die Einzelentropien $H(X)$ bzw. $H(Y)$. Beispielsweise wird die Unsicherheit hinsichtlich der Zufallsgröße $X$  ⇒  Entropie $H(X)$ durch die Kenntnis von $Y$ vermindert, und zwar um den Betrag $H(X\hspace{0.03cm}|\hspace{0.03cm}Y)$  ⇒  bedingte Entropie von $X$, falls $Y$ bekannt ist. Der verbleibende Rest ist die Transinformation $I(X; Y)$. Gleichzeitig gilt aber auch $I(X; Y) = H(Y) - H(Y\hspace{0.03cm}|\hspace{0.03cm}X)$. Das Semikolon weist auf die Gleichberechtigung der beiden betrachteten Zufallsgrößen $X$ und $Y$ hin.
+
== # ÜBERBLICK ZUM DRITTEN HAUPTKAPITEL # ==
 +
<br>
 +
Im Mittelpunkt dieses dritten Hauptkapitels steht die&nbsp; '''Transinformation'''&nbsp; $I(X; Y)$&nbsp; zwischen zwei Zufallsgrößen&nbsp; $X$&nbsp; und $Y$,&nbsp; wofür auch andere Begriffe wie&nbsp; &bdquo;Mutual Information&rdquo;&nbsp; oder&nbsp; &bdquo;gegenseitige Entropie&rdquo;&nbsp; üblich sind.&nbsp; Bei statistischer Abhängigkeit ist&nbsp; $I(X; Y)$&nbsp; kleiner als die Einzelentropien&nbsp; $H(X)$&nbsp; bzw.&nbsp; $H(Y)$.&nbsp;  
  
 +
Beispielsweise wird die Unsicherheit hinsichtlich der Zufallsgröße&nbsp; $X$&nbsp;  &nbsp; ⇒  &nbsp; Entropie&nbsp; $H(X)$&nbsp; durch die Kenntnis von&nbsp; $Y$&nbsp; vermindert, und zwar um den Betrag&nbsp; $H(X\hspace{0.03cm}|\hspace{0.03cm}Y)$  &nbsp; ⇒  &nbsp;  bedingte Entropie von&nbsp; $X$,&nbsp; falls&nbsp; $Y$&nbsp; bekannt ist.&nbsp; Der verbleibende Rest ist die Transinformation&nbsp;
 +
:$$I(X; Y)= H(X) - H(X\hspace{0.03cm}|\hspace{0.03cm}Y).$$
  
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch &bdquo;Wertdiskrete Informationstheorie&rdquo; des Praktikums „Simulation Digitaler Übertragungssysteme ”. Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
+
Gleichzeitig gilt aber auch:&nbsp;
 +
:$$I(X; Y) = H(Y) - H(Y\hspace{0.03cm}|\hspace{0.03cm}X).$$
 +
Das Semikolon weist auf die Gleichberechtigung der beiden betrachteten Zufallsgrößen&nbsp; $X$&nbsp; und&nbsp; $Y$&nbsp; hin.
 +
 
 +
Im Einzelnen werden im dritten Hauptkapitel behandelt:
 +
 
 +
:*Der Zusammenhang zwischen Wahrscheinlichkeit und Entropie bei&nbsp; &raquo;2D–Zufallsgrößen&laquo;,
 +
:*die Berechnung der&nbsp; &raquo;relativen Entropie&laquo;, auch als&nbsp; &raquo;Kullback–Leibler–Distanz&laquo;&nbsp; bekannt,
 +
:*die Definition der&nbsp; &raquo;Verbundentropie&laquo;&nbsp; $H(XY)$&nbsp; und der&nbsp; &raquo;bedingten Entropien&laquo;&nbsp; $H(X\hspace{0.03cm}|\hspace{0.03cm}Y)$&nbsp; bzw.&nbsp; $H(Y\hspace{0.03cm}|\hspace{0.03cm}X)$,
 +
:*die Transinformation&nbsp; $I(X; Y)$&nbsp; zwischen zwei Zufallsgrößen&nbsp; (englisch:&nbsp; &raquo;Mutual Information&laquo;),
 +
:*die&nbsp; &raquo;Informationstheorie der Digitalsignalübertragung&laquo;&nbsp; und das dazugehörige Modell,
 +
:* die Definition und Bedeutung der&nbsp; &raquo;Kanalkapazität&laquo;&nbsp; und deren Zusammenhang mit der Transinformation,
 +
:*die Kapazitätsberechnung für&nbsp; &raquo;digitale gedächtnislose Kanäle&laquo;&nbsp; wie BSC, BEC und BSEC,
 +
:*das&nbsp; &raquo;Kanalcodierungstheorem&laquo;, eines der Highlights der Shannonschen Informationstheorie.
 +
 
 +
 
 +
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch &bdquo;Wertdiskrete Informationstheorie&rdquo; des Praktikums „Simulation Digitaler Übertragungssysteme ”.&nbsp; Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
 +
 
 +
*dem Windows-Programm&nbsp; [http://www.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip WDIT] &nbsp; &rArr; &nbsp; Link verweist auf die ZIP-Version des Programms; und
 +
*der zugehörigen&nbsp; [http://www.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Praktikumsanleitung]&nbsp;  &nbsp; &rArr; &nbsp; Link verweist auf die PDF-Version.
  
*dem Windows-Programm [http://www.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip WDIT] &nbsp;&rArr;&nbsp; Link verweist auf die ZIP-Version des Programms; und
 
*der zugehörigen [http://www.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Praktikumsanleitung]  &nbsp;&rArr;&nbsp; Link verweist auf die PDF-Version.
 
  
  
Der erste Abschnitt &bdquo;Allgemeine Beschreibung&rdquo; ist wie folgt gegliedert:
 
  
  
 
==Einführungsbeispiel zur statistischen Abhängigkeit von Zufallsgrößen ==  
 
==Einführungsbeispiel zur statistischen Abhängigkeit von Zufallsgrößen ==  
Wir gehen vom Experiment „Würfeln mit zwei Würfeln” aus, wobei beide Würfel (an der Farbe) unterscheidbar sind. Die untere Tabelle zeigt als Ergebnis die ersten $N = 18$ Wurfpaare dieses exemplarischen Zufallsexperiments.
+
<br>
 +
[[Datei:P_ID2741__Inf_T_3_1_S1_neu.png|right|frame|Ergebnisprotokoll unseres Zufallsexperiments „Würfeln mit zwei Würfeln”]]
 +
{{GraueBox|TEXT=
 +
$\text{Beispiel 1:}$&nbsp; Wir gehen vom Experiment „Würfeln mit zwei Würfeln” aus, wobei beide Würfel an der Farbe unterscheidbar sind.&nbsp;
 +
Die Tabelle zeigt als Ergebnis die ersten&nbsp; $N = 18$&nbsp; Wurfpaare dieses exemplarischen Zufallsexperiments.
 +
 
 +
 
  
[[Datei:P_ID2741__Inf_T_3_1_S1_neu.png|Ergebnisprotokoll unseres Zufallsexperiments „Würfeln mit zwei Würfeln”]]
 
  
''Hinweis'': Entsprechend der im [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Voraussetzungen_und_Nomenklatur|nachfolgendem Abschnitt]]  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.
+
Entsprechend der im&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Voraussetzungen_und_Nomenklatur|folgenden Abschnitt]]&nbsp; erklärten Nomenklatur sind hier&nbsp; $R_ν$,&nbsp; $B_ν$&nbsp; und&nbsp; $S_ν$&nbsp; als Zufallsgrößen zu verstehen:
 +
<br clear=all>
 +
*Die Zufallsgröße&nbsp; $R_3 \in  \{1, \ 2, \ 3, \ 4, \ 5, \ 6\}$&nbsp; gibt beispielsweise die Augenzahl des roten Würfels beim dritten Wurf als Wahrscheinlichkeitsereignis an.&nbsp; Die Angabe&nbsp; $R_3 = 6$&nbsp; sagt aus, dass bei der dokumentierten Realisierung der rote Würfel im dritten Wurf eine „6” gezeigt hat.
  
*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 ${\rm E}[R] = 3.5$.
+
*In Zeile 2 sind die Augenzahlen des roten Würfels&nbsp; $(R)$&nbsp; angegeben.&nbsp; Der Mittelwert dieser begrenzten Folge&nbsp; $〈R_1$, ... , $R_{18}〉$&nbsp; ist mit&nbsp; $3.39$&nbsp; etwas kleiner als der Erwartungswert&nbsp; ${\rm E}\big[R\big] = 3.5$.&nbsp;
*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  &nbsp; ⇒ &nbsp; ${\rm E}[B] = 3.5$.
+
*Die Zeile 3 zeigt die Augenzahlen des blauen Würfels&nbsp; $(B)$.&nbsp; Die Folge&nbsp; $〈B_1$, ... , $B_{18}〉$&nbsp; hat hierbei mit&nbsp; $3.61$&nbsp; einen etwas größeren Mittelwert als die unbegrenzte Folge  &nbsp; ⇒ &nbsp; ${\rm E}\big[B\big] = 3.5$.&nbsp;
*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]$.
+
*Die Zeile 4 beinhaltet die Summe&nbsp; $S_ν = R_ν + B_ν$.&nbsp; Der Mittelwert der Folge&nbsp; $〈S_1$, ... , $S_{18}〉$&nbsp; ist&nbsp; $3.39 + 3.61 = 7$.&nbsp; Dieser ist in diesem Beispiel (zufällig) gleich dem Erwartungswert&nbsp; $\text{E}\big[S\big] = \text{E}\big[R\big] + \text{E}\big[B\big]$.
  
  
 
Nun stellt sich die Frage, zwischen welchen Zufallsgrößen es statistische Abhängigkeiten gibt:
 
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.
+
*Setzt man faire Würfel voraus, so bestehen zwischen den Folgen&nbsp; $〈 R\hspace{0.05cm} 〉$&nbsp; und&nbsp; $〈B \hspace{0.05cm}〉$&nbsp; – ob begrenzt oder unbegrenzt – keine statistischen Bindungen: &nbsp; Auch wenn man&nbsp; $R_ν$&nbsp; kennt, sind für&nbsp; $B_ν$&nbsp; weiterhin alle möglichen Augenzahlen&nbsp; $1$, ... , $6$&nbsp; 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''.
+
*Kennt man aber&nbsp; $S_ν$, so sind sowohl Aussagen über&nbsp; $R_ν$&nbsp; als auch über&nbsp; $B_ν$&nbsp; möglich.&nbsp; Aus&nbsp; $S_{11} = 12$&nbsp; folgt direkt&nbsp; $R_{11} = B_{11} = 6$&nbsp; und die Summe&nbsp; $S_{15} = 2$&nbsp; zweier Würfel ist nur mit zwei Einsen möglich.&nbsp; Solche Abhängigkeiten bezeichnet man als&nbsp; &raquo;deterministisch&laquo;.
*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 [[Stochastische_Signaltheorie/Statistische_Abhängigkeit_und_Unabhängigkeit#Allgemeine_Definition_von_statistischer_Abh.C3.A4ngigkeit|statistische Abhängigkeit]].
+
*Aus&nbsp; $S_7 = 10$&nbsp; lassen sich zumindest Bereiche für&nbsp; $R_7$&nbsp; und&nbsp; $B_7$&nbsp; angeben: &nbsp; $R_7 ≥ 4, \ B_7 ≥ 4$.&nbsp; Möglich sind dann nur die drei Wertepaare&nbsp; $(R_7 = 4) ∩ (B_7 = 6)$,&nbsp; $(R_7 = 5) ∩ (B_7 = 5)$&nbsp; sowie&nbsp; $(R_7 = 6) ∩ (B_7 = 4)$.&nbsp; Hier besteht kein deterministischer Zusammenhang zwischen den Zufallsgrößen&nbsp; $S_ν$&nbsp; und&nbsp; $R_ν$&nbsp; $($bzw.&nbsp; $B_ν)$, sondern vielmehr eine so genannte&nbsp; [[Stochastische_Signaltheorie/Statistische_Abhängigkeit_und_Unabhängigkeit#Allgemeine_Definition_von_statistischer_Abh.C3.A4ngigkeit|&raquo;statistische Abhängigkeit&laquo;]].
*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. zwischen $S_ν$ und $B_ν$.
+
*Solche statistische Abhängigkeiten gibt es für&nbsp; $S_ν ∈ \{3, \ 4, \ 5, \ 6, \ 8, \ 9, \ 10, \ 11\}$.&nbsp; Ist dagegen die Summe&nbsp; $S_ν = 7$, so kann man daraus nicht auf&nbsp; $R_ν$&nbsp; und&nbsp; $B_ν$&nbsp; zurückgeschließen.&nbsp; Für beide Würfel sind dann alle möglichen Augenzahlen&nbsp; $1$, ... , $6$&nbsp; gleichwahrscheinlich.&nbsp; In diesem Fall bestehen auch&nbsp;  &raquo;keine statistischen Bindungen&laquo;&nbsp; zwischen&nbsp; $S_ν$&nbsp; und&nbsp; $R_ν$&nbsp; bzw. zwischen&nbsp; $S_ν$&nbsp; und&nbsp; $B_ν$.}}
 
   
 
   
  
== Voraussetzungen und Nomenklatur ==
+
== Voraussetzungen und Nomenklatur ==
Wir betrachten im gesamten Kapitel  wertdiskrete Zufallsgrößen der Form $X = \{ x_1, x_2, \hspace{0.05cm}... \hspace{0.15cm}, x_{\mu},\hspace{0.05cm}$ ... $\hspace{0.15cm}, x_M \} \hspace{0.05cm},$ und verwenden folgende Nomenklatur:
+
<br>
*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.
+
Wir betrachten im gesamten Kapitel  wertdiskrete Zufallsgrößen der Form&nbsp; $X = \{ x_1, \ x_2, \hspace{0.05cm}$ ... $\hspace{0.05cm},\ x_{\mu},\hspace{0.05cm}$ ... $\hspace{0.05cm},\ x_M \} \hspace{0.05cm},$&nbsp; und verwenden folgende Nomenklatur:
*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 selbst wird stets mit einem Großbuchstaben bezeichnet.&nbsp; Der Kleinbuchstabe&nbsp; $x$&nbsp; weist auf eine mögliche Realisierung der Zufallsgröße&nbsp; $X$&nbsp; hin.
 +
*Alle Realisierungen&nbsp; $x_μ$&nbsp; $($mit&nbsp; $μ = 1$, ... , $M)$&nbsp; sind reellwertig.&nbsp; $M$&nbsp; gibt den Symbolumfang&nbsp; (englisch:&nbsp; &raquo;symbol set size&laquo;)&nbsp; von&nbsp; $X$&nbsp; an.&nbsp; Anstelle von&nbsp; $M$&nbsp; verwenden wir manchmal auch&nbsp; $|X|$.
 +
[[Datei:P_ID2743__Inf_T_3_1_S2.png|right|frame|Zusammenhang zwischen dem Wahrscheinlichkeitsraum&nbsp; ${\it \Omega}$&nbsp; und der Zufallsgröße&nbsp; $X$]]
 +
<br>Die Zufallsgröße&nbsp; $X$&nbsp; kann zum Beispiel durch die Transformation&nbsp; ${\it \Omega} → X$&nbsp; entstanden sein, wobei&nbsp; ${\it \Omega}$&nbsp; für den&nbsp;  &raquo;Wahrscheinlichkeitsraum eines Zufallsexperiments&laquo;&nbsp; steht.&nbsp;
  
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:
+
Die Grafik verdeutlicht eine solche Transformation:
 
   
 
   
 
:$${\it \Omega} = \{ \omega_1, \omega_2, \omega_3, ... \hspace{0.15cm} \}  
 
:$${\it \Omega} = \{ \omega_1, \omega_2, \omega_3, ... \hspace{0.15cm} \}  
 
\hspace{0.25cm} \longmapsto \hspace{0.25cm}
 
\hspace{0.25cm} \longmapsto \hspace{0.25cm}
X = \{ x_1, x_2, x_3, x_4\}
+
X = \{ x_1, \ x_2, \ x_3, \ x_4\}
 
\subset \cal{R}\hspace{0.05cm}.$$
 
\subset \cal{R}\hspace{0.05cm}.$$
  
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$.  
+
*Jedes Zufallsereignis&nbsp; $ω_i ∈ {\it \Omega}$&nbsp; wird eindeutig einem reellen Zahlenwert&nbsp; $x_μ ∈ X ⊂ \cal{R}$&nbsp; zugeordnet.  
 
+
*Im Beispiel gilt für die Laufvariable&nbsp; $1 ≤ μ ≤ 4$ &nbsp; &rArr; &nbsp;  der Symbolumfang beträgt&nbsp; $M = |X| = 4$.  
:[[Datei:P_ID2743__Inf_T_3_1_S2.png|Zusammenhang zwischen Wahrscheinlichkeitsraum und Zufallsgröße]]
+
*Die Abbildung ist aber nicht&nbsp;  &raquo;eineindeutig&laquo;: &nbsp; 
 
+
::Die Realisierung&nbsp; $x_3 ∈ X$&nbsp; könnte sich im Beispiel aus dem Elementarereignis&nbsp; $ω_4$&nbsp; ergeben haben, aber auch aus&nbsp; $ω_6$&nbsp; $($oder aus einigen anderen der unendlich vielen, in der Grafik nicht eingezeichneten Elementarereignisse&nbsp; $ω_i)$.
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$).
+
<br clear=all>
 
+
{{BlaueBox|TEXT=
Oft verzichtet man auf die Indizierung sowohl der Elementarereignisse $ω_i$ als auch der Realisierungen $x_μ$. Damit ergeben sich beispielsweise folgende Kurzschreibweisen:
+
$\text{Vereinbarung:}$&nbsp; Oft verzichtet man auf die Indizierung sowohl der Elementarereignisse&nbsp; $ω_i$&nbsp; als auch der Realisierungen&nbsp; $x_μ$.&nbsp; Damit ergeben sich beispielsweise folgende Kurzschreibweisen:
 
   
 
   
 
:$$ \{ X = x  \}
 
:$$ \{ X = x  \}
Zeile 66: Zeile 96:
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Mit dieser Vereinbarung gilt für die Wahrscheinlichkeiten der diskreten Zufallsgröße $X$:
+
Mit dieser Vereinbarung gilt für die Wahrscheinlichkeiten der diskreten Zufallsgröße&nbsp; $X$:
 
   
 
   
:$${\rm Pr}( X = x_{\mu})  = \hspace{-0.2cm} \sum_{\omega \hspace{0.1cm} \in  \{ X = x_{\mu} \}}
+
:$${\rm Pr}( X = x_{\mu})  = \hspace{-0.2cm} \sum_{\omega \hspace{0.1cm} \in  \{ X = x_{\mu} \} }
 
  \hspace{-0.2cm}{\rm Pr} \left ( \{ \omega \} \right )
 
  \hspace{-0.2cm}{\rm Pr} \left ( \{ \omega \} \right )
\hspace{0.05cm}.$$
+
\hspace{0.05cm}.$$}}
  
  
==Wahrscheinlichkeitsfunktion und Wahrscheinlichkeitsdichtefunktion==
+
==Wahrscheinlichkeitsfunktion und Wahrscheinlichkeitsdichtefunktion==  
{{BlaueBox|
+
<br>
TEXT='''Definition''':&nbsp; Fasst man die $M$ Wahrscheinlichkeiten einer diskreten Zufallsgröße $X$ &nbsp; ⇒ &nbsp; ${\rm Pr}( X = x_{\mu})$ ähnlich wie bei einem Vektor zusammen, so kommt man zur '''Wahrscheinlichkeitsfunktion''' (englisch: ''Probability Mass Function'', PMF):
+
{{BlaueBox|TEXT=
 +
$\text{Definition:}$ &nbsp; Fasst man die&nbsp; $M$&nbsp; Wahrscheinlichkeiten einer diskreten Zufallsgröße&nbsp; $X$ &nbsp; ⇒ &nbsp; ${\rm Pr}( X = x_{\mu})$ ähnlich wie bei einem Vektor zusammen, so kommt man zur&nbsp; '''Wahrscheinlichkeitsfunktion'''&nbsp; $($englisch:&nbsp; "Probability Mass Function",&nbsp; $\rm PMF)$:
 
   
 
   
:$$P_X(X) = \big [ \hspace{0.02cm} P_X(x_1), P_X(x_2), \hspace{0.05cm}... \hspace{0.15cm}, P_X(x_{\mu}),\hspace{0.05cm} ...\hspace{0.15cm}, P_X(x_M) \hspace{0.02cm} \big ] \hspace{0.05cm}.$$
+
:$$P_X(X) = \big [ \hspace{0.02cm} P_X(x_1), P_X(x_2), \hspace{0.05cm}\text{...} \hspace{0.15cm}, P_X(x_{\mu}),\hspace{0.05cm} \text{...}\hspace{0.15cm}, P_X(x_M) \hspace{0.02cm} \big ] \hspace{0.05cm}.$$
  
Das $μ$–te Element dieses „Vektors” gibt dabei die folgende Wahrscheinlichkeit $P_X(x_{\mu}) =  {\rm Pr}( X = x_{\mu}) $ an.}}
+
Das&nbsp; $μ$–te Element dieses „Vektors” gibt dabei die Wahrscheinlichkeit&nbsp; $P_X(x_{\mu}) =  {\rm Pr}( X = x_{\mu}) $&nbsp; an.}}
  
  
Im Buch&bdquo;Stochastische Signaltheorie&rdquo; haben wir mit der [[Stochastische_Signaltheorie/Wahrscheinlichkeitsdichtefunktion_(WDF)#Definition_der_Wahrscheinlichkeitsdichtefunktion|Wahrscheinlichkeitsdichtefunktion]] (WDF, englisch: ''Probability Density Function'', PDF) eine ähnliche Beschreibungsgröße definiert und diese mit $f_X(x)$ bezeichnet.
+
Im Buch&bdquo;Stochastische Signaltheorie&rdquo; haben wir mit der&nbsp; [[Stochastische_Signaltheorie/Wahrscheinlichkeitsdichtefunktion_(WDF)#Definition_der_Wahrscheinlichkeitsdichtefunktion|Wahrscheinlichkeitsdichtefunktion]]&nbsp; $\rm (WDF$, englisch:&nbsp; "Probability Density Function",&nbsp; $\rm PDF)$&nbsp; eine ähnliche Beschreibungsgröße definiert und diese mit&nbsp; $f_X(x)$&nbsp; bezeichnet.&nbsp; Zu beachten ist aber:
Zu beachten ist aber:
+
*Die PDF eignet sich eher zur Charakterisierung kontinuierlicher Zufallsgrößen, wie zum Beispiel bei einer&nbsp; [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen|Gaußverteilung]]&nbsp; oder einer [[Stochastische_Signaltheorie/Gleichverteilte_Zufallsgrößen|Gleichverteilung]].&nbsp; Erst durch die&nbsp; [[Stochastische_Signaltheorie/Wahrscheinlichkeitsdichtefunktion#WDF-Definition_f.C3.BCr_diskrete_Zufallsgr.C3.B6.C3.9Fen|Verwendung von Diracfunktionen]]&nbsp; wird die PDF auch für diskrete Zufallsgrößen anwendbar.
*Die PDF eignet sich eher zur Charakterisierung kontinuierlicher Zufallsgrößen, wie zum Beispiel bei einer [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen|Gaußverteilung]] oder einer [[Stochastische_Signaltheorie/Gleichverteilte_Zufallsgrößen|Gleichverteilung]]. Erst durch die [[Stochastische_Signaltheorie/Wahrscheinlichkeitsdichtefunktion#WDF-Definition_f.C3.BCr_diskrete_Zufallsgr.C3.B6.C3.9Fen|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.&nbsp; Für die in diesem Kapitel betrachtete wertdiskrete Informationstheorie ist die PMF allerdings ausreichend.
*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 die PMF allerdings ausreichend.
 
  
  
{{GraueBox|
+
{{GraueBox|TEXT=
TEXT='''Beispiel 1''':&nbsp; Wir betrachten eine Wahrscheinlichkeitsdichtefunktion (abgekürzt WDF bzw. PDF) ohne großen Praxisbezug:
+
$\text{Beispiel 2:}$&nbsp; Wir betrachten eine Wahrscheinlichkeitsdichtefunktion&nbsp; (abgekürzt WDF bzw. PDF)&nbsp; ohne großen Praxisbezug:
 
   
 
   
:$$f_X(x) = 0.2 \cdot (x+2) + 0.3 \cdot (x-1.5)+0.5 \cdot (x-{\rm \pi}) \hspace{0.05cm}. $$
+
:$$f_X(x) = 0.2 \cdot \delta(x+2) + 0.3 \cdot \delta(x - 1.5)+0.5 \cdot \delta(x - {\rm \pi}) \hspace{0.05cm}. $$
  
Für die diskrete Zufallsgröße gilt somit $x ∈ X = \{–2, +1.5, +\pi \} $ ⇒ Symbolumfang $M = \vert X \vert = 3$, und die Wahrscheinlichkeitsfunktion (PMF) lautet:
+
Für die diskrete Zufallsgröße gilt somit&nbsp; $x ∈ X = \{–2,\ +1.5,\ +\pi \} $ &nbsp; &nbsp; Symbolumfang&nbsp; $M = \vert X \vert = 3$,&nbsp; und die Wahrscheinlichkeitsfunktion (PMF) lautet:
 
   
 
   
 
:$$P_X(X) = \big [ \hspace{0.1cm}0.2\hspace{0.05cm}, 0.3\hspace{0.05cm}, 0.5 \hspace{0.1cm} \big] \hspace{0.05cm}. $$
 
:$$P_X(X) = \big [ \hspace{0.1cm}0.2\hspace{0.05cm}, 0.3\hspace{0.05cm}, 0.5 \hspace{0.1cm} \big] \hspace{0.05cm}. $$
  
 
Man erkennt:
 
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&nbsp; $\rm PMF$&nbsp; liefert nur Informationen über die Wahrscheinlichkeiten&nbsp; $\text{Pr}(x_1)$,&nbsp; $\text{Pr}(x_2)$&nbsp; und&nbsp; $\text{Pr}(x_3)$.  
*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. }}
+
*Aus der&nbsp; $\rm PDF$&nbsp; sind dagegen auch die möglichen Realisierungen&nbsp; $x_1$,&nbsp; $x_2$&nbsp; und&nbsp; $x_3$&nbsp; der Zufallsgröße&nbsp; $X$&nbsp; ablesbar.
 +
*Die einzige Voraussetzung für die Zufallsgröße ist, dass sie reellwertig ist.  
 +
*Die möglichen Werte&nbsp; $x_μ$&nbsp; müssen weder positiv, ganzzahlig, äquidistant noch rational sein. }}
 
   
 
   
  
 
==Wahrscheinlichkeitsfunktion und Entropie==
 
==Wahrscheinlichkeitsfunktion und Entropie==
 +
<br>
 +
In der wertdiskreten Informationstheorie genügt im Gegensatz zu übertragungstechnischen Problemen schon die Kenntnis der Wahrscheinlichkeitsfunktion&nbsp; $P_X(X)$,&nbsp; zum Beispiel zur&nbsp; [[Informationstheorie/Gedächtnislose_Nachrichtenquellen#Informationsgehalt_und_Entropie|Entropieberechnung]].
  
In der wertdiskreten Informationstheorie genügt im Gegensatz zu übertragungstechnischen Problemen schon die Kenntnis der Wahrscheinlichkeitsfunktion $P_X(X)$, zum Beispiel zur Berechnung der [[Informationstheorie/Gedächtnislose_Nachrichtenquellen#Informationsgehalt_und_Entropie|Entropie]].
+
{{BlaueBox|TEXT=
 
+
$\text{Definition:}$&nbsp; Die&nbsp; $\rm Entropie$&nbsp; einer diskreten Zufallsgröße&nbsp; $X$&nbsp; – also deren Unsicherheit für einen Beobachter – kann man mit der Wahrscheinlichkeitsfunktion&nbsp; $P_X(X)$&nbsp; wie folgt darstellen:
{{BlaueBox|
 
TEXT='''Definition''':&nbsp; 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:
 
 
   
 
   
:$$H(X) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{1}{P_X(X)}\right ] \hspace{0.05cm}=\hspace{0.05cm}  
+
:$$H(X) = {\rm E} \big [ {\rm log} \hspace{0.1cm} \frac{1}{P_X(X)}\big ] \hspace{0.05cm}=\hspace{0.05cm}  
-{\rm E} \left [ {\rm log} \hspace{0.1cm} {P_X(X)}\right ] \hspace{0.05cm}=\hspace{0.05cm}  \sum_{\mu = 1}^{M}  
+
  - {\rm E} \big [ {\rm log} \hspace{0.1cm} {P_X(X)}\big ] \hspace{0.05cm}=\hspace{0.05cm}  \sum_{\mu = 1}^{M}  
 
  P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{1}{P_X(x_{\mu})} \hspace{0.05cm}=\hspace{0.05cm}  - \sum_{\mu = 1}^{M}  
 
  P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{1}{P_X(x_{\mu})} \hspace{0.05cm}=\hspace{0.05cm}  - \sum_{\mu = 1}^{M}  
 
  P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} {P_X(x_{\mu})} \hspace{0.05cm}.$$
 
  P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} {P_X(x_{\mu})} \hspace{0.05cm}.$$
  
Verwendet man den Logarithmus zur Basis 2, also $\log_2$ (...) &nbsp;  ⇒ &nbsp; ''Logarithmus dualis'', so wird der Zahlenwert mit der Pseudo–Einheit „bit” versehen. $\rm E[$...$]$ gibt den ''Erwartungswert'' an. }}
+
Verwendet man den Logarithmus zur Basis&nbsp; $2$, also&nbsp; $\log_2$ (...) &nbsp;  ⇒ &nbsp; &bdquo;Logarithmus dualis&rdquo;, so wird der Zahlenwert mit der Pseudo–Einheit „bit” versehen.&nbsp; $\rm E\big[$...$\big]$ gibt den Erwartungswert an. }}
  
  
 
Beispielsweise erhält man
 
Beispielsweise erhält man
*für $P_X(X) = \big [\hspace{0.02cm}0.2, 0.3, 0.5 \hspace{0.02cm}\big ]$:
+
*für&nbsp; $P_X(X) = \big [\hspace{0.02cm}0.2, \ 0.3, \ 0.5 \hspace{0.02cm}\big ]$:  
 
+
::$$H(X) = 0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} +
:$$H(X) = 0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} +
 
 
0.3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.3}
 
0.3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.3}
 
+0.5 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.5}
 
+0.5 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.5}
 
\approx 1.485\,{\rm bit}\hspace{0.05cm},$$  
 
\approx 1.485\,{\rm bit}\hspace{0.05cm},$$  
  
*für $P_X(X) = \big [\hspace{0.02cm}1/3, 1/3, 1/3\hspace{0.02cm}\big ]$:
+
*für&nbsp; $P_X(X) = \big [\hspace{0.02cm}1/3, \ 1/3, \ 1/3\hspace{0.02cm}\big ]$:
 
   
 
   
:$$H(X) = 3 \cdot 1/3 \cdot {\rm log}_2 \hspace{0.1cm} (3) = {\rm log}_2 \hspace{0.1cm} (3)
+
::$$H(X) = 3 \cdot 1/3 \cdot {\rm log}_2 \hspace{0.1cm} (3) = {\rm log}_2 \hspace{0.1cm} (3)
 
\approx 1.585\,{\rm bit}\hspace{0.05cm}.$$
 
\approx 1.585\,{\rm bit}\hspace{0.05cm}.$$
  
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 [Meck]<ref>Mecking, M.: Information Theory. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, Technische Universität München, 2009.</ref>:
+
Das zweite Beispiel liefert das Maximum der Entropiefunktion für den Symbolumfang&nbsp; $M = 3$.  
 +
 
 +
{{BlaueBox|TEXT=
 +
$\text{Herleitung:}$&nbsp;
 +
Für ein allgemeines&nbsp; $M$&nbsp; lässt sich dieses Ergebnis beispielsweise wie folgt herleiten – siehe&nbsp;  [Meck]<ref>Mecking, M.: Information Theory. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, Technische Universität München, 2009.</ref>:
 
   
 
   
:$$H(X) = -{\rm E} \left [ {\rm log} \hspace{0.1cm} {P_X(X)}\right ] \hspace{0.2cm} \le \hspace{0.2cm}- {\rm log} \left [ {\rm E} \hspace{0.1cm} \left [{P_X(X)}\right ] \right ] \hspace{0.05cm}.$$
+
:$$H(X) = -{\rm E} \big [ {\rm log} \hspace{0.1cm} {P_X(X)}\big ] \hspace{0.2cm} \le \hspace{0.2cm}- {\rm log} \big [ {\rm E} \hspace{0.1cm} \left [{P_X(X)}\right ] \big ] \hspace{0.05cm}.$$
  
Diese Abschätzung (Jensens's Ungleichung) ist zulässig, da der Logarithmus eine konkave Funktion ist. Entsprechend [[Aufgaben:3.2_Erwartungswertberechnungen|Aufgabe 3.2]] gilt:
+
Diese Abschätzung&nbsp;  $($'''Jensens's Ungleichung'''$)$&nbsp; ist zulässig, da der Logarithmus eine konkave Funktion ist.&nbsp; Entsprechend der&nbsp; [[Aufgaben:3.2_Erwartungswertberechnungen|Aufgabe 3.2]]&nbsp; gilt:
  
$$-{\rm E} \left [  {P_X(X)}\right ] \hspace{0.1cm} \le \hspace{0.1cm} M \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
+
:$$- {\rm E} \big [  {P_X(X)}\big ] \hspace{0.1cm} \le \hspace{0.1cm} M \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
H(X) \le {\rm log} \hspace{0.1cm} (M)  \hspace{0.05cm}.$$
 
H(X) \le {\rm log} \hspace{0.1cm} (M)  \hspace{0.05cm}.$$
 
   
 
   
Das Gleichheitszeichen ergibt sich nach der oberen Rechnung für gleiche Wahrscheinlichkeiten, also für $P_X(x_μ) = {1}/{M}$ für alle $μ$. In der [[Aufgaben:3.3_Entropie_von_Ternärgrößen|Aufgabe 3.3]] soll der gleiche Sachverhalt unter Verwendung der Abschätzung
+
Das Gleichheitszeichen ergibt sich nach der oberen Rechnung für gleiche Wahrscheinlichkeiten, also für&nbsp; $P_X(x_μ) = {1}/{M}$&nbsp; für alle&nbsp; $μ$.&nbsp; In der&nbsp; [[Aufgaben:3.3_Entropie_von_Ternärgrößen|Aufgabe 3.3]]&nbsp; soll der gleiche Sachverhalt unter Verwendung der Abschätzung
 
   
 
   
$${\rm ln} \hspace{0.1cm} (x)  \le x-1$$
+
:$${\rm ln} \hspace{0.1cm} (x)  \le x-1$$
 +
 
 +
nachgewiesen werden.&nbsp; Das Gleichheitszeichen gilt hier nur für&nbsp; $x = 1$.}}
  
nachgewiesen werden. Das Gleichheitszeichen gilt hier nur für $x = 1$.
 
  
Ist eine der $M$ Wahrscheinlichkeiten $P_X(x_μ)$ der Wahrscheinlichkeitsfunktion gleich 0, so lässt sich für die Entropie eine engere Schranke angeben:
+
Ist eine der&nbsp; $M$&nbsp; Wahrscheinlichkeiten&nbsp; $P_X(x_μ)$&nbsp; der Wahrscheinlichkeitsfunktion gleich Null, so lässt sich für die Entropie eine engere Schranke angeben:
 
    
 
    
 
:$$H(X) \le {\rm log} \hspace{0.1cm} (M-1)  \hspace{0.05cm}.$$
 
:$$H(X) \le {\rm log} \hspace{0.1cm} (M-1)  \hspace{0.05cm}.$$
  
 +
{{BlaueBox|TEXT=
 +
$\text{Vereinbarung:}$&nbsp; Im folgenden Beispiel und auf den nächsten Seiten verwenden wir die folgende Nomenklatur:
 +
*Die Entropie&nbsp; $H(X)$&nbsp; bezieht sich stets auf die tatsächliche Wahrscheinlichkeitsfunktion&nbsp; $P_X(X)$&nbsp; der diskreten Zufallsgröße.&nbsp; Experimentell erhält man diese Größen erst nach&nbsp; $N → ∞$&nbsp; Versuchen.
 +
*Ermittelt man die Wahrscheinlichkeitsfunktion aus einer endlichen Zufallsfolge, so bezeichnen wir diese  Wahrscheinlichkeitsfunktion mit&nbsp; $Q_X(X)$&nbsp; und die daraus resultierende Entropie versehen wir mit dem Zusatz&nbsp; „$N =$ ...”.
 +
*Diese Entropie–Näherung basiert nicht auf Wahrscheinlichkeiten, sondern auf&nbsp; [[Stochastische_Signaltheorie/Wahrscheinlichkeit_und_relative_Häufigkeit#Bernoullisches_Gesetz_der_gro.C3.9Fen_Zahlen|relativen Häufigkeiten]].&nbsp; Erst für&nbsp; $N → ∞$&nbsp; stimmt die Näherung mit&nbsp; $H(X)$&nbsp; überein.}}
  
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 [[Stochastische_Signaltheorie/Wahrscheinlichkeit_und_relative_Häufigkeit#Bernoullisches_Gesetz_der_gro.C3.9Fen_Zahlen|relativen Häufigkeiten]]. Erst für $N → ∞$ stimmt diese Näherung mit $H(X)$ überein.
 
  
 +
[[Datei:P_ID2744__Inf_T_3_1_S3_neu.png|right|frame|Wahrscheinlichkeitsfunktionen unseres Würfelexperiments]]
 +
{{GraueBox|TEXT=
 +
$\text{Beispiel 3:}$&nbsp; Wir kommen auf unser&nbsp; &bdquo;Würfel–Experiment&rdquo;&nbsp; zurück.
  
{{GraueBox|
+
*Die Tabelle zeigt die Wahrscheinlichkeitsfunktionen&nbsp; $P_R(R)$&nbsp; und&nbsp; $P_B(B)$&nbsp; für den roten und den blauen Würfel sowie die Näherungen&nbsp; $Q_R(R)$&nbsp; und&nbsp; $Q_B(B)$,&nbsp; jeweils basierend auf dem Zufallsexperiment mit&nbsp; $N = 18$&nbsp; Würfen.&nbsp;
TEXT='''Beispiel 2''':&nbsp; Wir kommen auf unser ''Würfel–Experiment'' zurück. Die folgende 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 [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Einf.C3.BChrungsbeispiel_zur_statistischen_Abh.C3.A4ngigkeit_von_Zufallsgr.C3.B6.C3.9Fen|beispielhaften Zufallsfolgen]] vom Beginn dieses Kapitels.
+
*Die relativen Häufigkeiten&nbsp; $Q_R(R)$&nbsp; und&nbsp; $Q_B(B)$&nbsp; ergeben sich aus den&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Einf.C3.BChrungsbeispiel_zur_statistischen_Abh.C3.A4ngigkeit_von_Zufallsgr.C3.B6.C3.9Fen|beispielhaften Zufallsfolgen]]&nbsp; von&nbsp; $\text{Beispiel 1}$.
  
[[Datei:P_ID2744__Inf_T_3_1_S3_neu.png|Wahrscheinlichkeitsfunktionen unseres Würfelexperiments]]
 
  
Für die Zufallsgröße $R$ gilt mit dem ''Logarithmus dualis'' (zur Basis 2):
+
Für die Zufallsgröße&nbsp; $R$&nbsp; gilt mit dem Logarithmus zur Basis&nbsp; $2$:
 
    
 
    
:$$H(R) = H(R) \big \vert_{N \hspace{0.05cm}\rightarrow \hspace{0.05cm}\infty} = \sum_{\mu = 1}^{6} 1/6 \cdot {\rm log}_2 \hspace{0.1cm} (6) = {\rm log}_2 \hspace{0.1cm} (6) = 2.585\,{\rm bit} \hspace{0.05cm},$$
+
:$$H(R) = H(R) \big \vert_{N \hspace{0.05cm}\rightarrow \hspace{0.05cm}\infty} = \sum_{\mu = 1}^{6} 1/6 \cdot {\rm log}_2 \hspace{0.1cm} (6) = {\rm log}_2 \hspace{0.1cm} (6) = 2.585\ {\rm bit} \hspace{0.05cm},$$
  
:$$H(R) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 2 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{2} \hspace{0.1cm} +\hspace{0.1cm} 2 \cdot \frac{3}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{3} \hspace{0.1cm} +\hspace{0.1cm}  2 \cdot \frac{4}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{4} \hspace{0.1cm}= 2.530\,{\rm bit} \hspace{0.05cm}.$$
+
:$$H(R) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 2 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{2} \hspace{0.1cm} +\hspace{0.1cm} 2 \cdot \frac{3}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{3} \hspace{0.1cm} +\hspace{0.1cm}  2 \cdot \frac{4}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{4} \hspace{0.1cm}= 2.530\ {\rm bit} \hspace{0.05cm}.$$
  
Der blaue Würfel hat natürlich die gleiche Entropie: $H(B) = H(R) = 2.585\, \rm 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 Gleichverteilung $P_B(B)$ weniger abweicht als $Q_R(R)$ von $P_R(R)$.
+
Der blaue Würfel hat natürlich die gleiche Entropie:&nbsp; $H(B) = H(R) = 2.585\ \rm bit$.&nbsp; Hier erhält man für die auf&nbsp; $N = 18$&nbsp; basierende Näherung einen etwas größeren Wert, da nach obiger Tabelle&nbsp; $Q_B(B)$&nbsp; von der diskreten Gleichverteilung&nbsp; $P_B(B)$&nbsp; weniger abweicht&nbsp; als $Q_R(R)$&nbsp; von&nbsp; $P_R(R)$.
 
   
 
   
:$$H(B) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 1 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{2} \hspace{0.1cm} +\hspace{0.1cm} 4 \cdot \frac{3}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{3} \hspace{0.1cm} +\hspace{0.1cm}  1 \cdot \frac{4}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{4} \hspace{0.1cm}= 2.558\,{\rm bit} \hspace{0.05cm}.$$
+
:$$H(B) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 1 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{2} \hspace{0.1cm} +\hspace{0.1cm} 4 \cdot \frac{3}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{3} \hspace{0.1cm} +\hspace{0.1cm}  1 \cdot \frac{4}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{4} \hspace{0.1cm}= 2.558\ {\rm bit} \hspace{0.05cm}.$$
  
Man erkennt aus den angegebenen Zahlenwerten, dass trotz des eigentlich viel zu kleinen Experimentenparameters $N$ die Verfälschungen hinsichtlich der Entropie nicht sehr groß sind.
+
Man erkennt aus den angegebenen Zahlenwerten, dass trotz des eigentlich viel zu kleinen Experimentenparameters&nbsp; $N$&nbsp; die Verfälschungen hinsichtlich der Entropie nicht sehr groß sind.
  
Es soll nochmals erwähnt werden, dass bei endlichem $N$ stets gilt:
+
Es soll nochmals erwähnt werden, dass bei endlichem&nbsp; $N$&nbsp; stets gilt:
 
   
 
   
 
:$$ H(R) \big \vert_{N } < H(R) =  {\rm log}_2 \hspace{0.1cm} (6) \hspace{0.05cm}, \hspace{0.5cm}
 
:$$ H(R) \big \vert_{N } < H(R) =  {\rm log}_2 \hspace{0.1cm} (6) \hspace{0.05cm}, \hspace{0.5cm}
Zeile 179: Zeile 218:
  
  
==Relative Entropie – Kullback–Leibler–Distanz ==  
+
==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 folgende informationstheoretische Größe:  
+
<br>  
 +
Wir betrachten zwei Wahrscheinlichkeitsfunktionen&nbsp; $P_X(·)$&nbsp; und&nbsp; $P_Y(·)$&nbsp; über dem gleichen Alphabet&nbsp; $X = \{ x_1, \ x_2$, ... ,&nbsp; $x_M \}$,&nbsp; und definieren nun folgende Größe:  
  
{{BlaueBox|TEXT='''Definition''':&nbsp; Die '''relative Entropie''' (englisch: ''Informational Divergence'') zwischen den durch $P_X(·)$ und $P_Y(·)$ definierten Zufallsgrößen ist durch folgende Gleichung gegeben:
+
{{BlaueBox|TEXT=
 +
$\text{Definition:}$&nbsp; Die&nbsp; '''relative Entropie'''&nbsp; (englisch:&nbsp; "Informational Divergence")&nbsp; zwischen den durch&nbsp; $P_X(·)$&nbsp; und&nbsp; $P_Y(·)$&nbsp; definierten Zufallsgrößen ist wie folgt gegeben:
 
   
 
   
 
:$$D(P_X \hspace{0.05cm} \vert \vert  \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{M}  
 
:$$D(P_X \hspace{0.05cm} \vert \vert  \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{M}  
 
  P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_X(x_{\mu})}{P_Y(x_{\mu})} \hspace{0.05cm}.$$
 
  P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_X(x_{\mu})}{P_Y(x_{\mu})} \hspace{0.05cm}.$$
  
Man bezeichnet $D(P_X \vert \vert P_Y)$ auch als die '''Kullback–Leibler–Distanz''' (oder kurz ''KL–Distanz''). Diese liefert ein Maß für die „Ähnlichkeit” zwischen den beiden Wahrscheinlichkeitsfunktionen $P_X(·)$ und $P_Y(·)$.
+
Man bezeichnet&nbsp; $D(P_X \vert \vert P_Y)$&nbsp; auch als die&nbsp; '''Kullback–Leibler–Distanz'''&nbsp; (oder kurz:&nbsp; '''KL–Distanz''').  
 +
*Diese liefert ein Maß für die „Ähnlichkeit” zwischen den beiden Wahrscheinlichkeitsfunktionen&nbsp; $P_X(·)$&nbsp; und&nbsp; $P_Y(·)$.
  
Bei Verwendung des Logarithmus zur Basis 2 ist wieder die Pseudo–Einheit „bit” hinzuzufügen. }}
+
*Bei Verwendung des Logarithmus zur Basis&nbsp; $2$&nbsp; ist wieder die Pseudo–Einheit „bit” hinzuzufügen. }}
  
  
Zeile 197: Zeile 239:
 
  P_Y(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_Y(x_{\mu})}{P_X(x_{\mu})} \hspace{0.05cm}.$$
 
  P_Y(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_Y(x_{\mu})}{P_X(x_{\mu})} \hspace{0.05cm}.$$
  
Gegenüber der ersten Variante wird nun 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.
+
Gegenüber der ersten Variante wird nun jede Funktion&nbsp; $P_X(·)$&nbsp; durch&nbsp; $P_Y(·)$&nbsp; ersetzt und umgekehrt.&nbsp; Da sich im allgemeinen&nbsp; $D(P_X || P_Y)$&nbsp; und&nbsp; $D(P_Y || P_X)$&nbsp; unterscheiden, ist der Begriff „Distanz” eigentlich irreführend.&nbsp; Wir wollen es aber bei dieser Namensgebung belassen.
  
 
Wertet man die beiden obigen Gleichungen aus, so erkennt man folgende Eigenschaften:
 
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)$.
+
*Liegt die gleiche Verteilung vor  &nbsp; ⇒  &nbsp; $P_Y(·) ≡ P_X(·)$,&nbsp; so ist&nbsp; $D(P_X || P_Y) = 0$.&nbsp; In allen anderen Fällen ist&nbsp; $D(P_X || P_Y) > 0$.&nbsp; Gleiches gilt für die Variante&nbsp; $D(P_Y || P_X)$.
*Gilt $P_X(x_μ) ≠ 0$ und $P_Y(x_μ) = 0$ (hierfür genügt ein einziges und beliebiges $μ$), so ergibt sich für die Kullback–Leibler–Distanz $D(P_X || P_Y)$ ein unendlich großer Wert.
+
*Gilt&nbsp; $P_X(x_μ) ≠ 0$&nbsp; und&nbsp; $P_Y(x_μ) = 0$&nbsp; $($hierfür genügt ein einziges und beliebiges&nbsp; )$, so ergibt sich für die Kullback–Leibler–Distanz&nbsp; $D(P_X || P_Y)$&nbsp; ein unendlich großer Wert.&nbsp; In diesem Fall ist&nbsp; $D(P_Y || P_X)$&nbsp; nicht notwendigerweise ebenfalls unendlich.  
*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.
+
*Diese Aussage macht nochmals deutlich, dass im allgemeinen&nbsp; $D(P_X || P_Y)$&nbsp; ungleich&nbsp; $D(P_Y || P_X)$&nbsp; sein wird.
 +
 
  
Anschließend Seite werden diese beiden Definitionen an unserem Standardbeispiel ''Würfel–Experiment'' verdeutlicht. Gleichzeitig verweisen wir auf folgende Aufgaben:  
+
Anschließend werden diese beiden Definitionen an unserem Standardbeispiel&nbsp; &bdquo;Würfel–Experiment&rdquo;&nbsp; verdeutlicht.&nbsp; Gleichzeitig verweisen wir auf folgende Aufgaben:  
*[[Aufgaben:3.5_Kullback-Leibler-Distanz_%26_Binominalverteilung|Aufgabe 3.5: Kullback–Leibler–Distanz & Binomialverteilung]]
+
*[[Aufgabe_3.5:_Kullback-Leibler-Distanz_%26_Binominalverteilung|Aufgabe 3.5: Kullback–Leibler–Distanz & Binomialverteilung]]
 
*[[Aufgaben:3.5Z_Nochmals_Kullback-Leibler-Distanz|Aufgabe 3.5Z: Nochmals Kullback–Leibler–Distanz]]
 
*[[Aufgaben:3.5Z_Nochmals_Kullback-Leibler-Distanz|Aufgabe 3.5Z: Nochmals Kullback–Leibler–Distanz]]
 
*[[Aufgaben:3.6_Partitionierungsungleichung|A3.6: Partitionierungsungleichung]]
 
*[[Aufgaben:3.6_Partitionierungsungleichung|A3.6: Partitionierungsungleichung]]
  
  
{{GraueBox|
+
[[Datei:P_ID2745__Inf_T_3_1_S3_neu.png|right|frame|Wahrscheinlichkeitsfunktionen unseres Würfelexperiments]]
TEXT='''Beispiel 3''':&nbsp; Für das Würfel–Experiment haben wir die Wahrscheinlichkeitsfunktionen $P_R(·)$, $P_B(·)$ und deren Näherungen $Q_R(·)$, $Q_B(·)$ definiert.  
+
 
*Die Zufallsgröße $R$ mit PMF  $P_R(·)$ gibt die Augenzahl des roten Würfels an und $B$  mit PMF  $P_B(·)$ die Augenzahl des blauen Würfels.  
+
{{GraueBox|TEXT=
*Die Näherungen $Q_R(·)$ und $Q_B(·)$ ergeben sich aus dem früher beschriebenen Experiment mit lediglich $N = 18$ Doppelwürfen.
+
$\text{Beispiel 4:}$&nbsp; Für das Würfel–Experiment haben wir im&nbsp; $\text{Beispiel 3}$&nbsp; die Wahrscheinlichkeitsfunktionen&nbsp; $P_R(·)$&nbsp; und&nbsp; $P_B(·)$&nbsp; sowie deren Näherungen&nbsp; $Q_R(·)$&nbsp; und&nbsp; $Q_B(·)$&nbsp; definiert.  
 +
*Die Zufallsgröße&nbsp; $R$&nbsp; mit PMF&nbsp; $P_R(·)$&nbsp; gibt die Augenzahl des roten Würfels an und&nbsp; $B$&nbsp; mit PMF&nbsp; $P_B(·)$&nbsp; die des blauen.  
 +
*$Q_R(·)$&nbsp; und&nbsp; $Q_B(·)$&nbsp; ergeben sich aus dem früher beschriebenen Experiment mit&nbsp;  $N = 18$&nbsp; Doppelwürfen&nbsp; &rArr; &nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Einf.C3.BChrungsbeispiel_zur_statistischen_Abh.C3.A4ngigkeit_von_Zufallsgr.C3.B6.C3.9Fen|$\text{Beispiel 1}$]] .
  
[[Datei:P_ID2745__Inf_T_3_1_S3_neu.png|Wahrscheinlichkeitsfunktionen unseres Würfelexperiments]]
 
  
 
Dann gilt:
 
Dann gilt:
*Da die Wahrscheinlichkeitsfunktionen $P_R(·)$ und $P_B(·)$ identisch sind, erhält man für die oben definierten Kullback–Leibler–Distanzen $D(P_R \vert \vert P_B)$ und $D(P_B \vert \vert P_R)$ jeweils den Wert $0$.
+
*Da&nbsp; $P_R(·)$&nbsp; und&nbsp; $P_B(·)$&nbsp; identisch sind, erhält man für die oben definierten Kullback–Leibler–Distanzen&nbsp; $D(P_R \vert \vert P_B)$&nbsp; und&nbsp; $D(P_B \vert \vert P_R)$&nbsp; jeweils den Wert Null.
*Der Vergleich von $P_R(·)$, $Q_R(·)$ ergibt für die erste Variante der Kullback–Leibler–Distanz:
+
*Der Vergleich von&nbsp; $P_R(·)$&nbsp; und&nbsp;  $Q_R(·)$&nbsp; ergibt für die erste Variante der Kullback–Leibler–Distanz:
 
   
 
   
 
:$$\begin{align*}D(P_R \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_R) & =   
 
:$$\begin{align*}D(P_R \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_R) & =   
Zeile 230: Zeile 274:
 
2 \cdot  {\rm log}_2 \hspace{0.1cm}  \frac{1/6}{4/18} \hspace{0.1cm}  
 
2 \cdot  {\rm log}_2 \hspace{0.1cm}  \frac{1/6}{4/18} \hspace{0.1cm}  
 
  \right  ] =  1/6 \cdot \big [  
 
  \right  ] =  1/6 \cdot \big [  
2 \cdot  0.585 + 2 \cdot  0 - 2 \cdot  0.415 \big ] \approx 0.0570\,{\rm bit} \hspace{0.05cm}.\end{align*}$$
+
2 \cdot  0.585 + 2 \cdot  0 - 2 \cdot  0.415 \big ] \approx 0.0570\ {\rm bit} \hspace{0.05cm}.\end{align*}$$
  
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.
+
:Hierbei wurde bei der vorzunehmenden Erwartungswertbildung die Tatsache ausgenutzt, dass wegen&nbsp; $P_R(r_1) = $ &nbsp;...&nbsp; $ = P_R(r_6)$&nbsp; der Faktor&nbsp; $1/6$&nbsp; ausgeklammert werden kann.&nbsp; Da hier der Logarithmus zur Basis&nbsp;$ 2$&nbsp; 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 die zweite Variante der Kullback–Leibler–Distanz ergibt sich ein etwas anderer Wert:
 
   
 
   
$$\begin{align*}D(Q_R \hspace{0.05cm}\vert \vert \hspace{0.05cm} P_R)  & =   
+
:$$\begin{align*}D(Q_R \hspace{0.05cm}\vert \vert \hspace{0.05cm} P_R)  & =   
 
{\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{Q_R(\cdot)}{P_R(\cdot)}\right ]
 
{\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{Q_R(\cdot)}{P_R(\cdot)}\right ]
 
\hspace{0.1cm} = \sum_{\mu = 1}^{6}  
 
\hspace{0.1cm} = \sum_{\mu = 1}^{6}  
Zeile 242: Zeile 286:
 
2 \cdot \frac{3}{18} \cdot {\rm log}_2 \hspace{0.1cm}  \frac{3/18}{1/6} \hspace{0.1cm} +
 
2 \cdot \frac{3}{18} \cdot {\rm log}_2 \hspace{0.1cm}  \frac{3/18}{1/6} \hspace{0.1cm} +
 
2 \cdot \frac{4}{18} \cdot {\rm log}_2 \hspace{0.1cm}  \frac{4/18}{1/6}   
 
2 \cdot \frac{4}{18} \cdot {\rm log}_2 \hspace{0.1cm}  \frac{4/18}{1/6}   
   =\\
+
   \approx 0.0544\ {\rm bit} \hspace{0.05cm}.\end{align*}$$
& =  \hspace{-0.15cm} 
 
4/18 \cdot  (-0.585) + 3/18 \cdot  0 +8/18 \cdot 0.415  \approx 0.0544\,{\rm bit} \hspace{0.05cm}.\end{align*}$$
 
  
*Für den blauen Würfel erhält man $D(P_B \vert \vert Q_B) ≈ 0.0283 \ \rm bit$ und $D(Q_B \vert \vert P_B) ≈ 0.0271 \ \rm bit$, also etwas kleinere Kullback–Leibler–Distanzen, da sich die Approximation $Q_B(·)$ von $P_B(·)$ weniger unterscheidet als $Q_R(·)$ von $P_R(·)$.
+
*Für den blauen Würfel erhält man&nbsp; $D(P_B \vert \vert Q_B) ≈ 0.0283 \ \rm bit$&nbsp; und&nbsp; $D(Q_B \vert \vert P_B) ≈ 0.0271 \ \rm bit$, also etwas kleinere Kullback–Leibler–Distanzen, da sich die Approximation&nbsp; $Q_B(·)$&nbsp; von&nbsp; $P_B(·)$&nbsp; weniger unterscheidet als&nbsp; $Q_R(·)$&nbsp; von&nbsp; $P_R(·)$.
*Vergleicht man die Häufigkeiten $Q_R(·)$ und $Q_B(·)$, so erhält man $D(Q_R \vert \vert Q_B) ≈ 0.0597 \ \rm bit$ und $D(Q_B \vert \vert Q_R) ≈ 0.0608 \ \rm 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(·)$.}}
+
*Vergleicht man die Häufigkeiten&nbsp; $Q_R(·)$&nbsp; und&nbsp; $Q_B(·)$, so erhält man&nbsp; $D(Q_R \vert \vert Q_B) ≈ 0.0597 \ \rm bit$&nbsp; und&nbsp; $D(Q_B \vert \vert Q_R) ≈ 0.0608 \ \rm bit$.&nbsp; Hier sind die Distanzen am größten, da die Unterschiede zwischen&nbsp; $Q_B(·)$&nbsp; und&nbsp; $Q_R(·)$&nbsp; größer sind als zwischen&nbsp; $Q_R(·)$&nbsp; und&nbsp; $P_R(·)$&nbsp; oder zwischen&nbsp; $Q_B(·)$&nbsp; und&nbsp; $P_B(·)$.}}
  
 
   
 
   
==Verbundwahrscheinlichkeit und Verbundentropie  ==
+
==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.
+
<br>
Die Wahrscheinlichkeitsfunktion hat somit eine $K × M$–Matrixform mit den Elementen
+
Für den Rest dieses dritten Kapitels betrachten wir stets zwei diskrete Zufallsgrößen&nbsp; $X = \{ x_1, \ x_2$, ... ,&nbsp; $x_M \}$&nbsp; und&nbsp; $Y = \{ y_1, \ y_2$, ... ,&nbsp; $y_K \}$, deren Wertebereiche nicht notwendigerweise übereinstimmen müssen.&nbsp; Das heißt: &nbsp; $K ≠ M$ $($in anderer Notation:&nbsp; $|Y| ≠ |X|)$&nbsp; ist durchaus erlaubt.
 +
 
 +
Die Wahrscheinlichkeitsfunktion hat somit eine&nbsp; $K×M$–Matrixform mit den Elementen
 
   
 
   
$$P_{XY}(X = x_{\mu}\hspace{0.05cm}, Y = y_{\kappa}) = {\rm Pr} \big [( X = x_{\mu})\hspace{0.05cm}\cap \hspace{0.05cm} (Y = y_{\kappa}) \big ] \hspace{0.05cm}.$$
+
:$$P_{XY}(X = x_{\mu}\hspace{0.05cm}, \ Y = y_{\kappa}) = {\rm Pr} \big [( X = x_{\mu})\hspace{0.05cm}\cap \hspace{0.05cm} (Y = y_{\kappa}) \big ] \hspace{0.05cm}.$$
  
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.
+
Als Kurzschreibweise verwenden wir&nbsp; $P_{XY}(X, Y)$.&nbsp; Die neue Zufallsgröße&nbsp; $XY$&nbsp; beinhaltet sowohl die Eigenschaften von&nbsp; $X$&nbsp; als auch diejenigen von&nbsp; $Y$.
  
{{Definition}}
+
{{BlaueBox|TEXT=
Die '''Verbundentropie''' (englisch: ''Joint Entropy'') lässt sich als ein Erwartungswert mit der 2D–Wahrscheinlichkeitsfunktion $P_{XY}(X, Y)$ wie folgt darstellen:
+
$\text{Definition:}$&nbsp; Die&nbsp; '''Verbundentropie'''&nbsp; (englisch:&nbsp; "Joint Entropy")&nbsp; lässt sich mit der 2D–Wahrscheinlichkeitsfunktion&nbsp; $P_{XY}(X, Y)$&nbsp; als Erwartungswert wie folgt darstellen:
 
   
 
   
$$H(XY) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{1}{P_{XY}(X, Y)}\right ] = \sum_{\mu = 1}^{M}  \hspace{0.1cm} \sum_{\kappa = 1}^{K} \hspace{0.1cm}
+
:$$H(XY) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{1}{P_{XY}(X, Y)}\right ] = \sum_{\mu = 1}^{M}  \hspace{0.1cm} \sum_{\kappa = 1}^{K} \hspace{0.1cm}
  P_{XY}(x_{\mu}\hspace{0.05cm}, y_{\kappa}) \cdot {\rm log} \hspace{0.1cm} \frac{1}{P_{XY}(x_{\mu}\hspace{0.05cm}, y_{\kappa})} \hspace{0.05cm}.$$
+
  P_{XY}(x_{\mu}\hspace{0.05cm}, y_{\kappa}) \cdot {\rm log} \hspace{0.1cm} \frac{1}{P_{XY}(x_{\mu}\hspace{0.05cm}, y_{\kappa})} \hspace{0.05cm}.$$  
  
{{end}}
+
Im Folgenden verwenden wir durchgehend den Logarithmus zur Basis&nbsp; $2$  &nbsp; ⇒  &nbsp; $\log(x) → \log_2(x)$.&nbsp; Der Zahlenwert ist somit mit der Pseudo–Einheit „bit” zu versehen.
  
 +
Allgemein kann für die Verbundentropie die folgende&nbsp; '''obere Schranke'''&nbsp; angegegeben werden:
 +
 +
:$$H(XY) \le H(X) + H(Y)  \hspace{0.05cm}.$$}}
  
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:
 
 
$$H(XY) \le H(X) + H(Y)  \hspace{0.05cm}.$$
 
  
 
Diese Ungleichung drückt folgenden Sachverhalt aus:
 
Diese Ungleichung drückt folgenden Sachverhalt aus:
*Das Gleichheitszeichen gilt nur für den Sonderfall statistisch unabhängiger Zufallsgrößen, wie im Beispiel C im nächsten Abschnitt anhand der Zufallsgrößen $R$ und $B$ demonstriert wird. Hierbei bezeichnen $R$ und $B$ die Augenzahlen eines roten und eines blauen Würfels.
+
*Das Gleichheitszeichen gilt nur für den Sonderfall statistisch unabhängiger Zufallsgrößen, wie im folgenden&nbsp; $\text{Beispiel 5}$&nbsp; anhand der Zufallsgrößen&nbsp; $R$&nbsp; und&nbsp; $B$&nbsp; demonstriert wird.&nbsp; Hierbei bezeichnen&nbsp; $R$&nbsp; und&nbsp; $B$&nbsp; wieder die Augenzahlen des roten bzw.  des 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)$.
+
:$$H(RB) = H(R) + H(B).$$
 +
*Gibt es dagegen wie im&nbsp; $\text{Beispiel 6}$&nbsp; statistische Abhängigkeiten zwischen den Zufallsgrößen&nbsp; $R$&nbsp; und&nbsp; $S = R + B$, so gilt in obiger Gleichung das „<”–Zeichen: &nbsp;
 +
:$$H(RS) < H(R) + H(S).$$
  
 +
In diesen Beispielen wird auch gezeigt, in wie weit sich die Verbundentropien&nbsp; $H(RB)$&nbsp; und&nbsp; $H(RS)$&nbsp; ändern, wenn man beim Würfel–Experiment nicht unendlich viele Wurfpaare ermittelt, sondern lediglich&nbsp; $N = 18$.
  
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.
+
[[Datei:P_ID2747__Inf_T_3_1_S5a.png|right|frame|2D–PMF&nbsp; $P_{RB}$&nbsp; und Näherung&nbsp; $Q_{RB}$]]
 +
{{GraueBox|TEXT=
 +
$\text{Beispiel 5:}$&nbsp; Wir kommen wieder auf das&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Einf.C3.BChrungsbeispiel_zur_statistischen_Abh.C3.A4ngigkeit_von_Zufallsgr.C3.B6.C3.9Fen|Würfel–Experiment]]&nbsp; zurück:
  
 +
Die Zufallsgrößen sind die Augenzahlen des
 +
*roten Würfels &nbsp; &rArr; &nbsp; $R = \{1, \ 2,\ 3,\ 4,\ 5,\ 6\}$,
 +
*blauen Würfels:&nbsp; &rArr; &nbsp; $B = \{1,\ 2,\ 3,\ 4,\ 5,\ 6\}$.
  
{{Beispiel}}
 
Wir kommen wieder auf das [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Einf.C3.BChrungsbeispiel_zur_statistischen_Abh.C3.A4ngigkeit_von_Zufallsgr.C3.B6.C3.9Fen|Würfel–Experiment]] zurück: Die Zufallsgrößen sind die Augenzahlen des roten und des blauen Würfels: $R$ = {1, 2, 3, 4, 5, 6}, $B$ = {1, 2, 3, 4, 5, 6}.
 
  
[[Datei:P_ID2747__Inf_T_3_1_S5a.png|2D–PMF <i>P<sub>RB</sub></i> und Näherung <i>Q<sub>RB</sub></i>]]
+
Die linke Grafik zeigt die Wahrscheinlichkeiten&nbsp;
 +
:$$P_{RB}(r_\mu,\ b_\kappa ) ={\rm Pr}\big [(R=r_\mu) \hspace{0.05cm}\cap \hspace{0.05cm} (B=b_\kappa)\big],$$
 +
die für alle&nbsp; $μ = 1$, ... , $6$&nbsp; und für alle&nbsp; $κ = 1$, ... , $6$&nbsp; gleichermaßen den Wert&nbsp; $1/36$&nbsp; ergeben.
  
Die linke Grafik zeigt die Wahrscheinlichkeiten $P_{RB}(·)$, die sich für alle $μ$ = 1, ... , 6 und für alle $κ$ = 1, ... , 6 gleichermaßen zu 1/36 ergeben. Damit erhält man für die Verbundentropie:
+
Damit erhält man für die Verbundentropie:
 
   
 
   
$$H(RB) = H(RB) \big |_{N \hspace{0.05cm}\rightarrow \hspace{0.05cm}\infty} =  {\rm log}_2 \hspace{0.1cm} (36) = 5.170\,{\rm bit} \hspace{0.05cm}.$$
+
:$$H(RB) = H(RB) \big \vert_{N \hspace{0.05cm}\rightarrow \hspace{0.05cm}\infty} =  {\rm log}_2 \hspace{0.1cm} (36) = 5.170\ {\rm bit} \hspace{0.05cm}.$$
 +
 
 +
Man erkennt aus der linken Grafik und der hier angegebenen Gleichung:
 +
*Da&nbsp; $R$&nbsp; und&nbsp; $B$&nbsp; statistisch voneinander unabhängig sind, gilt
 +
:$$P_{RB}(R, B) = P_R(R) · P_B(B).$$
 +
*Die Verbundentropie ist die Summe der beiden Einzelentropien: &nbsp;
 +
:$$H(RB) = H(R) + H(B).$$
  
Man erkennt aus obiger Grafik und der hier angegebenen Gleichung:
+
Die rechte Grafik zeigt die angenäherte 2D&ndash;PMF&nbsp; $Q_{RB}(·)$, basierend auf den nur&nbsp; $N = 18$&nbsp; Wurfpaaren unseres Experiments.&nbsp; Hier ergibt sich keine quadratische Form der Verbundwahrscheinlichkeit&nbsp; $Q_{RB}(·)$, und die daraus abgeleitete Verbundentropie ist deutlich kleiner als&nbsp; $H(RB)$:
*Da $R$ und $B$ statistisch voneinander unabhängig sind, gilt $P_{RB}(R, B)$ = $P_R(R) · P_B(B)$.
 
*Die Verbundentropie ist die Summe der beiden Einzelentropien: $H(RB) = H(R) + H(B)$.
 
Die rechte Grafik zeigt die angenäherte 2D–Wahrscheinlichkeitsfunktion $Q_{RB}(·)$, basierend auf den nur $N$ = 18 Wurfpaaren unseres Experiments:
 
*Hier ergibt sich keine quadratische Form der Verbundwahrscheinlichkeit $Q_{RB}(·)$, und die daraus abgeleitete Verbundentropie ist deutlich kleiner als $H(RB)$:
 
 
   
 
   
$$H(RB) \big |_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 16 \cdot \frac{1}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{1} \hspace{0.1cm} +\hspace{0.1cm} 1 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{2} \hspace{0.1cm}= 4.059\,{\rm bit} \hspace{0.05cm}.$$
+
:$$H(RB) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 16 \cdot \frac{1}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{1} \hspace{0.1cm} +\hspace{0.1cm} 1 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm}  \frac{18}{2} \hspace{0.1cm}= 4.059\ {\rm bit} \hspace{0.05cm}.$$}}
 +
 
  
{{end}}
+
[[Datei:P_ID2748__Inf_T_3_1_S5b_neu.png|right|frame|2D–PMF&nbsp; $P_{RS}$&nbsp; und Näherung&nbsp; $Q_{RS}$]]
 +
{{GraueBox|TEXT=
 +
$\text{Beispiel 6:}$&nbsp; Beim Würfel–Experiment haben wir neben den Größen&nbsp; $R$&nbsp; (roter Würfel) und&nbsp; $B$&nbsp; (blauer Würfel) auch die Summe&nbsp; $S = R + B$&nbsp; betrachtet.&nbsp;
  
 +
Die linke Grafik zeigt, dass man die 2D&ndash;Wahrscheinlichkeitsfunktion&nbsp; $P_{RS}(·)$&nbsp; nicht als Produkt von&nbsp; $P_R(·)$&nbsp; und&nbsp; $P_S(·)$&nbsp; schreiben kann.
  
{{Beispiel}}
+
Mit den Wahrscheinlichkeitsfunktionen
Bei unserem Würfel–Experiment haben wir neben den beiden Zufallsgrößen $R$ (roter Würfel) und $B$ (blauer Würfel) auch die Summe $S$ = $R + B$ betrachtet. Die linke Grafik zeigt, dass $P_{RS}(·)$ nicht als Produkt von $P_R(·)$ und $P_S(·)$ geschrieben werden kann. Mit den Wahrscheinlichkeitsfunktionen
 
 
   
 
   
$$\begin{align*}P_R(R) \hspace{-0.15cm} & = \hspace{-0.15cm} \left [ \hspace{0.1cm} 1/6\hspace{0.05cm}, 1/6\hspace{0.05cm}, 1/6\hspace{0.05cm}, 1/6\hspace{0.05cm}, 1/6\hspace{0.05cm}, 1/6 \hspace{0.1cm} \right ] \hspace{0.05cm},\\
+
:$$P_R(R) = 1/6 \cdot \big [ 1,\ 1,\ 1,\ 1,\ 1,\ 1 \big ],$$
P_S(S) \hspace{-0.15cm} & = \hspace{-0.15cm} \left [ \hspace{0.1cm}  1/36\hspace{0.05cm},2/36\hspace{0.05cm}, 3/36\hspace{0.05cm}, 4/36\hspace{0.05cm}, 5/36\hspace{0.05cm}, 6/36\hspace{0.05cm}, 5/36\hspace{0.05cm}, 4/36\hspace{0.05cm}, 3/36\hspace{0.05cm}, 2/36\hspace{0.05cm}, 1/36\hspace{0.1cm} \right ] \hspace{0.05cm} \end{align*}$$
+
:$$P_S(S)=1/36 \cdot \big [ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 5,\ 4,\ 3,\ 2,\ 1 \big ] $$
  
 
erhält man für die Entropien:
 
erhält man für die Entropien:
 +
 +
:$$H(RS) = {\rm log}_2 \hspace{0.1cm} (36) \approx 5.170\hspace{0.15cm} {\rm bit} ,$$
 +
:$$H(R) = {\rm log}_2 \hspace{0.1cm} (6) \approx 2.585\hspace{0.15cm} {\rm bit},$$
 +
$$H(S) = 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm}\frac{1}{36} \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2 \hspace{0.05cm}  \frac{36}{1} \hspace{0.05cm} + 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{2}{36} \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2 \hspace{0.05cm}  \frac{36}{2} \hspace{0.05cm} + 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{3}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{3} \hspace{0.05cm} + $$
 
   
 
   
$$\begin{align*}H(R) \hspace{-0.15cm} & =  \hspace{-0.15cm}  {\rm log}_2 \hspace{0.1cm} (6) \approx 2.585\,{\rm bit} \hspace{0.05cm},\\
+
::$$+ 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{4}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{4} \hspace{0.05cm} +2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{5}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{5}
H(S) \hspace{-0.15cm} & = & \hspace{-0.15cm}  2 \cdot \frac{1}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{1} \hspace{0.05cm} + 2 \cdot \frac{2}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{2} \hspace{0.05cm} + 2 \cdot \frac{3}{36} \cdot {\rm log}_2 \hspace{0.05cm} \frac{36}{3} \hspace{0.05cm} + 2 \cdot \frac{4}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{4} \hspace{0.05cm} +\\
+
+ 1 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{6}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{6}  $$
& + \hspace{-0.15cm} 2 \cdot \frac{5}{36} \cdot {\rm log}_2 \hspace{0.05cm} \frac{36}{5}
 
+ 1 \cdot \frac{6}{36} \cdot {\rm log}_2 \hspace{0.05cm}  \frac{36}{6} \approx 3.274\,{\rm bit} \hspace{0.05cm},
 
\\
 
H(RS) \hspace{-0.15cm} & = \hspace{-0.15cm}  {\rm log}_2 \hspace{0.1cm} (36) \approx 5.170\,{\rm bit} \hspace{0.05cm}.\end{align*}$$
 
  
[[Datei:P_ID2748__Inf_T_3_1_S5b_neu.png|2D–PMF <i>P<sub>RS</sub></i> und Näherung <i>Q<sub>RS</sub></i>]]
+
:$$\Rightarrow \hspace{0.3cm} H(S) \approx 3.274\hspace{0.15cm} {\rm bit} . $$
 +
<br clear=all>
 +
*Der Vergleich mit dem&nbsp; $\text{Beispiel 5}$&nbsp; zeigt, dass&nbsp; $H(RS) =H(RB)$&nbsp; ist.&nbsp; Der Grund hierfür ist, dass bei Kenntnis von&nbsp; $R$&nbsp; die Zufallsgrößen&nbsp; $B$&nbsp; und&nbsp; $S$&nbsp; genau die gleichen Informationen liefern.
  
Aus diesen Zahlenwerten erkennt man:
+
*Aufgrund der statistischen Abhängigkeit zwischen dem roten Würfel und der Summe ist die Verbundentropie&nbsp; $H(RS) ≈ 5.170 \hspace{0.15cm} \rm bit$&nbsp; kleiner als die Summe&nbsp; $H(R) + H(S) ≈ 5.877 \hspace{0.15cm} \rm bit.$
*Aufgrund der statistischen Abhängigkeit zwischen dem roten Würfel und der Summe ist die Verbundentropie $H(RS)$ ≈ 5.170 bit kleiner als $H(R)$ + $H(S)$ ≈ 5.877 bit.
 
*Der Vergleich mit Beispiel C zeigt, dass $H(RS)$ gleich $H(RB)$ ist. Der Grund ist, dass bei Kenntnis von $R$ die Zufallsgrößen $B$ und $S$ genau die gleichen Informationen liefern.
 
  
Rechts dargestellt ist der Fall, dass die 2D–PMF aus nur $N$ = 18 Wurfpaaren empirisch ermittelt wurde $Q_{RS}(·)$. Obwohl sich aufgrund des sehr kleinen $N$–Wertes ein völlig anderes Bild ergibt, liefert die Näherung für $H(RS)$ den exakt gleichen Wert wie die Näherung für $H(RB)$:
+
<br clear=all>
 +
Rechts dargestellt ist der Fall, dass die 2D–PMF&nbsp; $Q_{RS}(·)$&nbsp; empirisch ermittelt wurde&nbsp; $(N = 18)$.&nbsp; Obwohl sich aufgrund des sehr kleinen&nbsp; $N$–Wertes ein völlig anderes Bild ergibt, liefert die Näherung für&nbsp; $H(RS)$&nbsp; den exakt gleichen Wert wie die Näherung für&nbsp; $H(RB)$&nbsp; im $\text{Beispiel 5}$:
 
   
 
   
$$H(RS) \big |_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = H(RB) \big |_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 4.059\,{\rm bit} \hspace{0.05cm}.$$
+
:$$H(RS) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = H(RB) \big \vert_{N \hspace{0.05cm} =  \hspace{0.05cm}18} = 4.059\hspace{0.15cm}{\rm bit} .$$}}
  
{{end}}
 
 
   
 
   
  
 
==Aufgaben zum Kapitel==
 
==Aufgaben zum Kapitel==
 +
<br>
 +
[[Aufgaben:3.1 Wahrscheinlichkeiten beim Würfeln|Aufgabe 3.1: Wahrscheinlichkeiten beim Würfeln]]
 +
 +
[[Aufgaben:3.1Z Karten ziehen|Zusatzaufgabe 3.1Z: Karten ziehen]]
 +
 +
[[Aufgaben:3.2 Erwartungswertberechnungen|Aufgabe 3.2: Erwartungswertberechnungen]]
 +
 +
[[Aufgaben:3.2Z 2D–Wahrscheinlichkeitsfunktion|Aufgabe 3.2Z: 2D–Wahrscheinlichkeitsfunktion]]
 +
 +
[[Aufgaben:3.3 Entropie von Ternärgrößen|Aufgabe 3.3: Entropie von Ternärgrößen]]
 +
 +
[[Aufgaben:3.4 Entropie für verschiedene Wahrscheinlichkeiten|Aufgabe 3.4: Entropie für verschiedene Wahrscheinlichkeiten]]
  
[[Aufgaben:1.1 Wetterentropie|Aufgabe 1.1: &nbsp; Wetterentropie]]
+
[[Aufgabe 3.5: Kullback-Leibler-Distanz & Binominalverteilung|Aufgabe 3.5: Kullback-Leibler-Distanz & Binominalverteilung]]
  
[[Aufgaben:1.1Z Binäre Entropiefunktion|Aufgabe 1.1Z: &nbsp; Binäre Entropiefunktion]]
+
[[Aufgaben:3.5Z Nochmals Kullback-Leibler-Distanz|Aufgabe 3.5Z: Nochmals Kullback-Leibler-Distanz]]
  
[[Aufgaben:1.2 Entropie von Ternärquellen|Aufgabe 1.2: &nbsp; Entropie von Ternärquellen]]
+
[[Aufgaben:3.6 Partitionierungsungleichung|Aufgabe 3.6: Partitionierungsungleichung]]
  
  

Aktuelle Version vom 16. Juli 2021, 13:30 Uhr

# ÜBERBLICK ZUM DRITTEN HAUPTKAPITEL #


Im Mittelpunkt dieses dritten Hauptkapitels steht die  Transinformation  $I(X; Y)$  zwischen zwei Zufallsgrößen  $X$  und $Y$,  wofür auch andere Begriffe wie  „Mutual Information”  oder  „gegenseitige Entropie”  üblich sind.  Bei statistischer Abhängigkeit ist  $I(X; Y)$  kleiner als die Einzelentropien  $H(X)$  bzw.  $H(Y)$. 

Beispielsweise wird die Unsicherheit hinsichtlich der Zufallsgröße  $X$    ⇒   Entropie  $H(X)$  durch die Kenntnis von  $Y$  vermindert, und zwar um den Betrag  $H(X\hspace{0.03cm}|\hspace{0.03cm}Y)$   ⇒   bedingte Entropie von  $X$,  falls  $Y$  bekannt ist.  Der verbleibende Rest ist die Transinformation 

$$I(X; Y)= H(X) - H(X\hspace{0.03cm}|\hspace{0.03cm}Y).$$

Gleichzeitig gilt aber auch: 

$$I(X; Y) = H(Y) - H(Y\hspace{0.03cm}|\hspace{0.03cm}X).$$

Das Semikolon weist auf die Gleichberechtigung der beiden betrachteten Zufallsgrößen  $X$  und  $Y$  hin.

Im Einzelnen werden im dritten Hauptkapitel behandelt:

  • Der Zusammenhang zwischen Wahrscheinlichkeit und Entropie bei  »2D–Zufallsgrößen«,
  • die Berechnung der  »relativen Entropie«, auch als  »Kullback–Leibler–Distanz«  bekannt,
  • die Definition der  »Verbundentropie«  $H(XY)$  und der  »bedingten Entropien«  $H(X\hspace{0.03cm}|\hspace{0.03cm}Y)$  bzw.  $H(Y\hspace{0.03cm}|\hspace{0.03cm}X)$,
  • die Transinformation  $I(X; Y)$  zwischen zwei Zufallsgrößen  (englisch:  »Mutual Information«),
  • die  »Informationstheorie der Digitalsignalübertragung«  und das dazugehörige Modell,
  • die Definition und Bedeutung der  »Kanalkapazität«  und deren Zusammenhang mit der Transinformation,
  • die Kapazitätsberechnung für  »digitale gedächtnislose Kanäle«  wie BSC, BEC und BSEC,
  • das  »Kanalcodierungstheorem«, eines der Highlights der Shannonschen Informationstheorie.


Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch „Wertdiskrete Informationstheorie” des Praktikums „Simulation Digitaler Übertragungssysteme ”.  Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf

  • dem Windows-Programm  WDIT   ⇒   Link verweist auf die ZIP-Version des Programms; und
  • der zugehörigen  Praktikumsanleitung    ⇒   Link verweist auf die PDF-Version.



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


Ergebnisprotokoll unseres Zufallsexperiments „Würfeln mit zwei Würfeln”

$\text{Beispiel 1:}$  Wir gehen vom Experiment „Würfeln mit zwei Würfeln” aus, wobei beide Würfel an der Farbe unterscheidbar sind.  Die Tabelle zeigt als Ergebnis die ersten  $N = 18$  Wurfpaare dieses exemplarischen Zufallsexperiments.



Entsprechend der im  folgenden Abschnitt  erklärten Nomenklatur sind hier  $R_ν$,  $B_ν$  und  $S_ν$  als Zufallsgrößen zu verstehen:

  • Die Zufallsgröße  $R_3 \in \{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.
  • 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  ${\rm E}\big[R\big] = 3.5$. 
  • Die Zeile 3 zeigt die Augenzahlen des blauen Würfels  $(B)$.  Die Folge  $〈B_1$, ... , $B_{18}〉$  hat hierbei mit  $3.61$  einen etwas größeren Mittelwert als die unbegrenzte Folge   ⇒   ${\rm E}\big[B\big] = 3.5$. 
  • Die Zeile 4 beinhaltet die Summe  $S_ν = R_ν + B_ν$.  Der Mittelwert der Folge  $〈S_1$, ... , $S_{18}〉$  ist  $3.39 + 3.61 = 7$.  Dieser ist in diesem Beispiel (zufällig) gleich dem Erwartungswert  $\text{E}\big[S\big] = \text{E}\big[R\big] + \text{E}\big[B\big]$.


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\hspace{0.05cm} 〉$  und  $〈B \hspace{0.05cm}〉$  – 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$  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 kein deterministischer Zusammenhang zwischen den Zufallsgrößen  $S_ν$  und  $R_ν$  $($bzw.  $B_ν)$, sondern vielmehr eine so genannte  »statistische Abhängigkeit«.
  • Solche statistische Abhängigkeiten gibt es für  $S_ν ∈ \{3, \ 4, \ 5, \ 6, \ 8, \ 9, \ 10, \ 11\}$.  Ist dagegen die Summe  $S_ν = 7$, so kann man daraus nicht auf  $R_ν$  und  $B_ν$  zurückgeschließen.  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. zwischen  $S_ν$  und  $B_ν$.


Voraussetzungen und Nomenklatur


Wir betrachten im gesamten Kapitel wertdiskrete Zufallsgrößen der Form  $X = \{ x_1, \ x_2, \hspace{0.05cm}$ ... $\hspace{0.05cm},\ x_{\mu},\hspace{0.05cm}$ ... $\hspace{0.05cm},\ x_M \} \hspace{0.05cm},$  und verwenden folgende Nomenklatur:

  • Die Zufallsgröße selbst wird stets mit einem Großbuchstaben bezeichnet.  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|$.
Zusammenhang zwischen dem Wahrscheinlichkeitsraum  ${\it \Omega}$  und der Zufallsgröße  $X$


Die Zufallsgröße  $X$  kann zum Beispiel durch die Transformation  ${\it \Omega} → X$  entstanden sein, wobei  ${\it \Omega}$  für den  »Wahrscheinlichkeitsraum eines Zufallsexperiments«  steht. 

Die Grafik verdeutlicht eine solche Transformation:

$${\it \Omega} = \{ \omega_1, \omega_2, \omega_3, ... \hspace{0.15cm} \} \hspace{0.25cm} \longmapsto \hspace{0.25cm} X = \{ x_1, \ x_2, \ x_3, \ x_4\} \subset \cal{R}\hspace{0.05cm}.$$
  • Jedes Zufallsereignis  $ω_i ∈ {\it \Omega}$  wird eindeutig einem reellen Zahlenwert  $x_μ ∈ X ⊂ \cal{R}$  zugeordnet.
  • Im Beispiel gilt für die Laufvariable  $1 ≤ μ ≤ 4$   ⇒   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 einigen anderen der unendlich vielen, in der Grafik nicht eingezeichneten Elementarereignisse  $ω_i)$.


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

$$ \{ X = x \} \hspace{0.05cm} \equiv \hspace{0.05cm} \{ \omega \in {\it \Omega} : \hspace{0.4cm} X(\omega) = x \} \hspace{0.05cm},$$
$$ \{ X \le x \} \hspace{0.05cm} \equiv \hspace{0.05cm} \{ \omega \in {\it \Omega} : \hspace{0.4cm} X(\omega) \le x \} \hspace{0.05cm}.$$

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

$${\rm Pr}( X = x_{\mu}) = \hspace{-0.2cm} \sum_{\omega \hspace{0.1cm} \in \{ X = x_{\mu} \} } \hspace{-0.2cm}{\rm Pr} \left ( \{ \omega \} \right ) \hspace{0.05cm}.$$


Wahrscheinlichkeitsfunktion und Wahrscheinlichkeitsdichtefunktion


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

$$P_X(X) = \big [ \hspace{0.02cm} P_X(x_1), P_X(x_2), \hspace{0.05cm}\text{...} \hspace{0.15cm}, P_X(x_{\mu}),\hspace{0.05cm} \text{...}\hspace{0.15cm}, P_X(x_M) \hspace{0.02cm} \big ] \hspace{0.05cm}.$$

Das  $μ$–te Element dieses „Vektors” gibt dabei die Wahrscheinlichkeit  $P_X(x_{\mu}) = {\rm Pr}( X = x_{\mu}) $  an.


Im Buch„Stochastische Signaltheorie” haben wir mit der  Wahrscheinlichkeitsdichtefunktion  $\rm (WDF$, englisch:  "Probability Density Function",  $\rm 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 in diesem Kapitel betrachtete wertdiskrete Informationstheorie ist die PMF allerdings ausreichend.


$\text{Beispiel 2:}$  Wir betrachten eine Wahrscheinlichkeitsdichtefunktion  (abgekürzt WDF bzw. PDF)  ohne großen Praxisbezug:

$$f_X(x) = 0.2 \cdot \delta(x+2) + 0.3 \cdot \delta(x - 1.5)+0.5 \cdot \delta(x - {\rm \pi}) \hspace{0.05cm}. $$

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

$$P_X(X) = \big [ \hspace{0.1cm}0.2\hspace{0.05cm}, 0.3\hspace{0.05cm}, 0.5 \hspace{0.1cm} \big] \hspace{0.05cm}. $$

Man erkennt:

  • Die  $\rm PMF$  liefert nur Informationen über die Wahrscheinlichkeiten  $\text{Pr}(x_1)$,  $\text{Pr}(x_2)$  und  $\text{Pr}(x_3)$.
  • Aus der  $\rm PDF$  sind dagegen auch die möglichen Realisierungen  $x_1$,  $x_2$  und  $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  $P_X(X)$,  zum Beispiel zur  Entropieberechnung.

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

$$H(X) = {\rm E} \big [ {\rm log} \hspace{0.1cm} \frac{1}{P_X(X)}\big ] \hspace{0.05cm}=\hspace{0.05cm} - {\rm E} \big [ {\rm log} \hspace{0.1cm} {P_X(X)}\big ] \hspace{0.05cm}=\hspace{0.05cm} \sum_{\mu = 1}^{M} P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{1}{P_X(x_{\mu})} \hspace{0.05cm}=\hspace{0.05cm} - \sum_{\mu = 1}^{M} P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} {P_X(x_{\mu})} \hspace{0.05cm}.$$

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


Beispielsweise erhält man

  • für  $P_X(X) = \big [\hspace{0.02cm}0.2, \ 0.3, \ 0.5 \hspace{0.02cm}\big ]$:
$$H(X) = 0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} + 0.3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.3} +0.5 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.5} \approx 1.485\,{\rm bit}\hspace{0.05cm},$$
  • für  $P_X(X) = \big [\hspace{0.02cm}1/3, \ 1/3, \ 1/3\hspace{0.02cm}\big ]$:
$$H(X) = 3 \cdot 1/3 \cdot {\rm log}_2 \hspace{0.1cm} (3) = {\rm log}_2 \hspace{0.1cm} (3) \approx 1.585\,{\rm bit}\hspace{0.05cm}.$$

Das zweite Beispiel liefert das Maximum der Entropiefunktion für den Symbolumfang  $M = 3$.

$\text{Herleitung:}$  Für ein allgemeines  $M$  lässt sich dieses Ergebnis beispielsweise wie folgt herleiten – siehe  [Meck][1]:

$$H(X) = -{\rm E} \big [ {\rm log} \hspace{0.1cm} {P_X(X)}\big ] \hspace{0.2cm} \le \hspace{0.2cm}- {\rm log} \big [ {\rm E} \hspace{0.1cm} \left [{P_X(X)}\right ] \big ] \hspace{0.05cm}.$$

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

$$- {\rm E} \big [ {P_X(X)}\big ] \hspace{0.1cm} \le \hspace{0.1cm} M \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H(X) \le {\rm log} \hspace{0.1cm} (M) \hspace{0.05cm}.$$

Das Gleichheitszeichen ergibt sich nach der oberen Rechnung für gleiche Wahrscheinlichkeiten, also für  $P_X(x_μ) = {1}/{M}$  für alle  $μ$.  In der  Aufgabe 3.3  soll der gleiche Sachverhalt unter Verwendung der Abschätzung

$${\rm ln} \hspace{0.1cm} (x) \le x-1$$

nachgewiesen werden.  Das Gleichheitszeichen gilt hier nur für  $x = 1$.


Ist eine der  $M$  Wahrscheinlichkeiten  $P_X(x_μ)$  der Wahrscheinlichkeitsfunktion gleich Null, so lässt sich für die Entropie eine engere Schranke angeben:

$$H(X) \le {\rm log} \hspace{0.1cm} (M-1) \hspace{0.05cm}.$$

$\text{Vereinbarung:}$  Im folgenden Beispiel und auf den nächsten Seiten verwenden 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 Wahrscheinlichkeitsfunktion mit  $Q_X(X)$  und die daraus resultierende Entropie versehen wir mit dem Zusatz  „$N =$ ...”.
  • Diese Entropie–Näherung basiert nicht auf Wahrscheinlichkeiten, sondern auf  relativen Häufigkeiten.  Erst für  $N → ∞$  stimmt die Näherung mit  $H(X)$  überein.


Wahrscheinlichkeitsfunktionen unseres Würfelexperiments

$\text{Beispiel 3:}$  Wir kommen auf unser  „Würfel–Experiment”  zurück.

  • Die 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  von  $\text{Beispiel 1}$.


Für die Zufallsgröße  $R$  gilt mit dem Logarithmus zur Basis  $2$:

$$H(R) = H(R) \big \vert_{N \hspace{0.05cm}\rightarrow \hspace{0.05cm}\infty} = \sum_{\mu = 1}^{6} 1/6 \cdot {\rm log}_2 \hspace{0.1cm} (6) = {\rm log}_2 \hspace{0.1cm} (6) = 2.585\ {\rm bit} \hspace{0.05cm},$$
$$H(R) \big \vert_{N \hspace{0.05cm} = \hspace{0.05cm}18} = 2 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{2} \hspace{0.1cm} +\hspace{0.1cm} 2 \cdot \frac{3}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{3} \hspace{0.1cm} +\hspace{0.1cm} 2 \cdot \frac{4}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{4} \hspace{0.1cm}= 2.530\ {\rm bit} \hspace{0.05cm}.$$

Der blaue Würfel hat natürlich die gleiche Entropie:  $H(B) = H(R) = 2.585\ \rm 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 Gleichverteilung  $P_B(B)$  weniger abweicht  als $Q_R(R)$  von  $P_R(R)$.

$$H(B) \big \vert_{N \hspace{0.05cm} = \hspace{0.05cm}18} = 1 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{2} \hspace{0.1cm} +\hspace{0.1cm} 4 \cdot \frac{3}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{3} \hspace{0.1cm} +\hspace{0.1cm} 1 \cdot \frac{4}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{4} \hspace{0.1cm}= 2.558\ {\rm bit} \hspace{0.05cm}.$$

Man erkennt aus den angegebenen Zahlenwerten, dass trotz des eigentlich viel zu kleinen Experimentenparameters  $N$  die Verfälschungen hinsichtlich der Entropie nicht sehr groß sind.

Es soll nochmals erwähnt werden, dass bei endlichem  $N$  stets gilt:

$$ H(R) \big \vert_{N } < H(R) = {\rm log}_2 \hspace{0.1cm} (6) \hspace{0.05cm}, \hspace{0.5cm} H(B) \big \vert_{N } < H(B) = {\rm log}_2 \hspace{0.1cm} (6)\hspace{0.05cm}.$$


Relative Entropie – Kullback–Leibler–Distanz


Wir betrachten zwei Wahrscheinlichkeitsfunktionen  $P_X(·)$  und  $P_Y(·)$  über dem gleichen Alphabet  $X = \{ x_1, \ x_2$, ... ,  $x_M \}$,  und definieren nun folgende Größe:

$\text{Definition:}$  Die  relative Entropie  (englisch:  "Informational Divergence")  zwischen den durch  $P_X(·)$  und  $P_Y(·)$  definierten Zufallsgrößen ist wie folgt gegeben:

$$D(P_X \hspace{0.05cm} \vert \vert \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{M} P_X(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_X(x_{\mu})}{P_Y(x_{\mu})} \hspace{0.05cm}.$$

Man bezeichnet  $D(P_X \vert \vert P_Y)$  auch als die  Kullback–Leibler–Distanz  (oder kurz:  KL–Distanz).

  • Diese liefert ein Maß für die „Ähnlichkeit” zwischen den beiden Wahrscheinlichkeitsfunktionen  $P_X(·)$  und  $P_Y(·)$.
  • Bei Verwendung des Logarithmus zur Basis  $2$  ist wieder die Pseudo–Einheit „bit” hinzuzufügen.


In ähnlicher Weise lässt sich auch eine zweite Variante der Kullback–Leibler–Distanz angeben:

$$D(P_Y \hspace{0.05cm} || \hspace{0.05cm}P_X) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{P_Y(X)}{P_X(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{M} P_Y(x_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_Y(x_{\mu})}{P_X(x_{\mu})} \hspace{0.05cm}.$$

Gegenüber der ersten Variante wird nun 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 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 Variante  $D(P_Y || P_X)$.
  • Gilt  $P_X(x_μ) ≠ 0$  und  $P_Y(x_μ) = 0$  $($hierfür genügt ein einziges und 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.


Anschließend werden diese beiden Definitionen an unserem Standardbeispiel  „Würfel–Experiment”  verdeutlicht.  Gleichzeitig verweisen wir auf folgende Aufgaben:


Wahrscheinlichkeitsfunktionen unseres Würfelexperiments

$\text{Beispiel 4:}$  Für das Würfel–Experiment haben wir im  $\text{Beispiel 3}$  die Wahrscheinlichkeitsfunktionen  $P_R(·)$  und  $P_B(·)$  sowie deren Näherungen  $Q_R(·)$  und  $Q_B(·)$  definiert.

  • Die Zufallsgröße  $R$  mit PMF  $P_R(·)$  gibt die Augenzahl des roten Würfels an und  $B$  mit PMF  $P_B(·)$  die des blauen.
  • $Q_R(·)$  und  $Q_B(·)$  ergeben sich aus dem früher beschriebenen Experiment mit  $N = 18$  Doppelwürfen  ⇒   $\text{Beispiel 1}$ .


Dann gilt:

  • Da  $P_R(·)$  und  $P_B(·)$  identisch sind, erhält man für die oben definierten Kullback–Leibler–Distanzen  $D(P_R \vert \vert P_B)$  und  $D(P_B \vert \vert P_R)$  jeweils den Wert Null.
  • Der Vergleich von  $P_R(·)$  und  $Q_R(·)$  ergibt für die erste Variante der Kullback–Leibler–Distanz:
$$\begin{align*}D(P_R \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_R) & = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_R(\cdot)}{Q_R(\cdot)}\right ] \hspace{0.1cm} = \sum_{\mu = 1}^{6} P_R(r_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{P_R(r_{\mu})}{Q_R(r_{\mu})} = \\ & = {1}/{6} \cdot \left [ 2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1/6}{2/18} \hspace{0.1cm} + 2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1/6}{3/18} \hspace{0.1cm} + 2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1/6}{4/18} \hspace{0.1cm} \right ] = 1/6 \cdot \big [ 2 \cdot 0.585 + 2 \cdot 0 - 2 \cdot 0.415 \big ] \approx 0.0570\ {\rm bit} \hspace{0.05cm}.\end{align*}$$
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:
$$\begin{align*}D(Q_R \hspace{0.05cm}\vert \vert \hspace{0.05cm} P_R) & = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{Q_R(\cdot)}{P_R(\cdot)}\right ] \hspace{0.1cm} = \sum_{\mu = 1}^{6} Q_R(r_{\mu}) \cdot {\rm log} \hspace{0.1cm} \frac{Q_R(r_{\mu})}{P_R(r_{\mu})} \hspace{0.05cm} = \\ & = 2 \cdot \frac{2}{18} \cdot {\rm log}_2 \hspace{0.1cm} \frac{2/18}{1/6} \hspace{0.1cm} + 2 \cdot \frac{3}{18} \cdot {\rm log}_2 \hspace{0.1cm} \frac{3/18}{1/6} \hspace{0.1cm} + 2 \cdot \frac{4}{18} \cdot {\rm log}_2 \hspace{0.1cm} \frac{4/18}{1/6} \approx 0.0544\ {\rm bit} \hspace{0.05cm}.\end{align*}$$
  • Für den blauen Würfel erhält man  $D(P_B \vert \vert Q_B) ≈ 0.0283 \ \rm bit$  und  $D(Q_B \vert \vert P_B) ≈ 0.0271 \ \rm bit$, also etwas kleinere Kullback–Leibler–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 \vert \vert Q_B) ≈ 0.0597 \ \rm bit$  und  $D(Q_B \vert \vert Q_R) ≈ 0.0608 \ \rm 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(·)$.


Verbundwahrscheinlichkeit und Verbundentropie


Für den Rest dieses dritten Kapitels 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

$$P_{XY}(X = x_{\mu}\hspace{0.05cm}, \ Y = y_{\kappa}) = {\rm Pr} \big [( X = x_{\mu})\hspace{0.05cm}\cap \hspace{0.05cm} (Y = y_{\kappa}) \big ] \hspace{0.05cm}.$$

Als Kurzschreibweise verwenden wir  $P_{XY}(X, Y)$.  Die neue Zufallsgröße  $XY$  beinhaltet sowohl die Eigenschaften von  $X$  als auch diejenigen von  $Y$.

$\text{Definition:}$  Die  Verbundentropie  (englisch:  "Joint Entropy")  lässt sich mit der 2D–Wahrscheinlichkeitsfunktion  $P_{XY}(X, Y)$  als Erwartungswert wie folgt darstellen:

$$H(XY) = {\rm E} \left [ {\rm log} \hspace{0.1cm} \frac{1}{P_{XY}(X, Y)}\right ] = \sum_{\mu = 1}^{M} \hspace{0.1cm} \sum_{\kappa = 1}^{K} \hspace{0.1cm} P_{XY}(x_{\mu}\hspace{0.05cm}, y_{\kappa}) \cdot {\rm log} \hspace{0.1cm} \frac{1}{P_{XY}(x_{\mu}\hspace{0.05cm}, y_{\kappa})} \hspace{0.05cm}.$$

Im Folgenden verwenden wir durchgehend den Logarithmus zur Basis  $2$   ⇒   $\log(x) → \log_2(x)$.  Der Zahlenwert ist somit mit der Pseudo–Einheit „bit” zu versehen.

Allgemein kann für die Verbundentropie die folgende  obere Schranke  angegegeben werden:

$$H(XY) \le H(X) + H(Y) \hspace{0.05cm}.$$


Diese Ungleichung drückt folgenden Sachverhalt aus:

  • Das Gleichheitszeichen gilt nur für den Sonderfall statistisch unabhängiger Zufallsgrößen, wie im folgenden  $\text{Beispiel 5}$  anhand der Zufallsgrößen  $R$  und  $B$  demonstriert wird.  Hierbei bezeichnen  $R$  und  $B$  wieder die Augenzahlen des roten bzw. des blauen Würfels:
$$H(RB) = H(R) + H(B).$$
  • Gibt es dagegen wie im  $\text{Beispiel 6}$  statistische Abhängigkeiten zwischen den Zufallsgrößen  $R$  und  $S = R + B$, so gilt in obiger Gleichung das „<”–Zeichen:  
$$H(RS) < H(R) + H(S).$$

In diesen 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$.

2D–PMF  $P_{RB}$  und Näherung  $Q_{RB}$

$\text{Beispiel 5:}$  Wir kommen wieder auf das  Würfel–Experiment  zurück:

Die Zufallsgrößen sind die Augenzahlen des

  • roten Würfels   ⇒   $R = \{1, \ 2,\ 3,\ 4,\ 5,\ 6\}$,
  • blauen Würfels:  ⇒   $B = \{1,\ 2,\ 3,\ 4,\ 5,\ 6\}$.


Die linke Grafik zeigt die Wahrscheinlichkeiten 

$$P_{RB}(r_\mu,\ b_\kappa ) ={\rm Pr}\big [(R=r_\mu) \hspace{0.05cm}\cap \hspace{0.05cm} (B=b_\kappa)\big],$$

die für alle  $μ = 1$, ... , $6$  und für alle  $κ = 1$, ... , $6$  gleichermaßen den Wert  $1/36$  ergeben.

Damit erhält man für die Verbundentropie:

$$H(RB) = H(RB) \big \vert_{N \hspace{0.05cm}\rightarrow \hspace{0.05cm}\infty} = {\rm log}_2 \hspace{0.1cm} (36) = 5.170\ {\rm bit} \hspace{0.05cm}.$$

Man erkennt aus der linken Grafik und der hier angegebenen Gleichung:

  • Da  $R$  und  $B$  statistisch voneinander unabhängig sind, gilt
$$P_{RB}(R, B) = P_R(R) · P_B(B).$$
  • Die Verbundentropie ist die Summe der beiden Einzelentropien:  
$$H(RB) = H(R) + H(B).$$

Die rechte Grafik zeigt die angenäherte 2D–PMF  $Q_{RB}(·)$, basierend auf den nur  $N = 18$  Wurfpaaren unseres Experiments.  Hier ergibt sich keine quadratische Form der Verbundwahrscheinlichkeit  $Q_{RB}(·)$, und die daraus abgeleitete Verbundentropie ist deutlich kleiner als  $H(RB)$:

$$H(RB) \big \vert_{N \hspace{0.05cm} = \hspace{0.05cm}18} = 16 \cdot \frac{1}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{1} \hspace{0.1cm} +\hspace{0.1cm} 1 \cdot \frac{2}{18}\cdot {\rm log}_2 \hspace{0.1cm} \frac{18}{2} \hspace{0.1cm}= 4.059\ {\rm bit} \hspace{0.05cm}.$$


2D–PMF  $P_{RS}$  und Näherung  $Q_{RS}$

$\text{Beispiel 6:}$  Beim Würfel–Experiment haben wir neben den Größen  $R$  (roter Würfel) und  $B$  (blauer Würfel) auch die Summe  $S = R + B$  betrachtet. 

Die linke Grafik zeigt, dass man die 2D–Wahrscheinlichkeitsfunktion  $P_{RS}(·)$  nicht als Produkt von  $P_R(·)$  und  $P_S(·)$  schreiben kann.

Mit den Wahrscheinlichkeitsfunktionen

$$P_R(R) = 1/6 \cdot \big [ 1,\ 1,\ 1,\ 1,\ 1,\ 1 \big ],$$
$$P_S(S)=1/36 \cdot \big [ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 5,\ 4,\ 3,\ 2,\ 1 \big ] $$

erhält man für die Entropien:

$$H(RS) = {\rm log}_2 \hspace{0.1cm} (36) \approx 5.170\hspace{0.15cm} {\rm bit} ,$$
$$H(R) = {\rm log}_2 \hspace{0.1cm} (6) \approx 2.585\hspace{0.15cm} {\rm bit},$$

$$H(S) = 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm}\frac{1}{36} \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2 \hspace{0.05cm} \frac{36}{1} \hspace{0.05cm} + 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{2}{36} \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2 \hspace{0.05cm} \frac{36}{2} \hspace{0.05cm} + 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{3}{36} \cdot {\rm log}_2 \hspace{0.05cm} \frac{36}{3} \hspace{0.05cm} + $$

$$+ 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{4}{36} \cdot {\rm log}_2 \hspace{0.05cm} \frac{36}{4} \hspace{0.05cm} +2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{5}{36} \cdot {\rm log}_2 \hspace{0.05cm} \frac{36}{5} + 1 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{6}{36} \cdot {\rm log}_2 \hspace{0.05cm} \frac{36}{6} $$
$$\Rightarrow \hspace{0.3cm} H(S) \approx 3.274\hspace{0.15cm} {\rm bit} . $$


  • Der Vergleich mit dem  $\text{Beispiel 5}$  zeigt, dass  $H(RS) =H(RB)$  ist.  Der Grund hierfür ist, dass bei Kenntnis von  $R$  die Zufallsgrößen  $B$  und  $S$  genau die gleichen Informationen liefern.
  • Aufgrund der statistischen Abhängigkeit zwischen dem roten Würfel und der Summe ist die Verbundentropie  $H(RS) ≈ 5.170 \hspace{0.15cm} \rm bit$  kleiner als die Summe  $H(R) + H(S) ≈ 5.877 \hspace{0.15cm} \rm bit.$


Rechts dargestellt ist der Fall, dass die 2D–PMF  $Q_{RS}(·)$  empirisch ermittelt wurde  $(N = 18)$.  Obwohl sich aufgrund des sehr kleinen  $N$–Wertes ein völlig anderes Bild ergibt, liefert die Näherung für  $H(RS)$  den exakt gleichen Wert wie die Näherung für  $H(RB)$  im $\text{Beispiel 5}$:

$$H(RS) \big \vert_{N \hspace{0.05cm} = \hspace{0.05cm}18} = H(RB) \big \vert_{N \hspace{0.05cm} = \hspace{0.05cm}18} = 4.059\hspace{0.15cm}{\rm bit} .$$


Aufgaben zum Kapitel


Aufgabe 3.1: Wahrscheinlichkeiten beim Würfeln

Zusatzaufgabe 3.1Z: Karten ziehen

Aufgabe 3.2: Erwartungswertberechnungen

Aufgabe 3.2Z: 2D–Wahrscheinlichkeitsfunktion

Aufgabe 3.3: Entropie von Ternärgrößen

Aufgabe 3.4: Entropie für verschiedene Wahrscheinlichkeiten

Aufgabe 3.5: Kullback-Leibler-Distanz & Binominalverteilung

Aufgabe 3.5Z: Nochmals Kullback-Leibler-Distanz

Aufgabe 3.6: Partitionierungsungleichung


Quellenverzeichnis

  1. Mecking, M.: Information Theory. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, Technische Universität München, 2009.