Quelltext der Seite Bedingte Entropie

In der [[Informationstheorie]] ist die '''bedingte Entropie''' ein Maß für die „Ungewissheit“ über den Wert einer [[Zufallsvariable]]n <math>X</math>, welche verbleibt, nachdem das Ergebnis einer anderen Zufallsvariable <math>Y</math> bekannt wird. Die bedingte Entropie wird <math>H(X|Y)</math> geschrieben und hat einen Wert zwischen 0 und <math>H(X)</math>, der ursprünglichen [[Entropie (Informationstheorie)|Entropie]] von <math>X</math>. Sie wird in der gleichen Maßeinheit wie die Entropie gemessen.

Speziell hat sie den Wert 0, wenn aus <math>Y</math> der Wert von <math>X</math> funktional bestimmt werden kann, und den Wert <math>H(X)</math>, wenn <math>X</math> und <math>Y</math> [[Stochastisch unabhängige Zufallsvariablen|stochastisch unabhängig]] sind.

== Definition ==
Seien <math>X</math> eine diskrete Zufallsvariable und <math>M</math> ihr [[Wertevorrat]], das heißt <math>M</math> ist eine [[Abzählbarkeit|höchstens abzählbare]] Menge mit <math>P(X \in M)=1</math>. Dann ist die [[Entropie (Informationstheorie)|Entropie]] von <math>X</math> durch
:<math>H(X) := -\sum_{x\in M}P(X=x)\,\log_b P(X=x)</math>
definiert, wobei für <math>b</math> typischerweise die Werte 2 ([[Bit]]) oder e ([[Natürliche Informationseinheit|Nat]]) für die entsprechenden Einheiten angenommen werden.
Ist für ein <math>x' \in M</math> die Wahrscheinlichkeit <math>P(X = x')</math> gleich <math>0</math>, so wird per Konvention <math>P(X=x')\,\log_b P(X=x') = 0</math> gesetzt, der entsprechende Term geht also nicht in die Summe ein.

Es sei nun <math>A</math> ein Ereignis mit <math>P(A)>0</math>. Dann definiert man die bedingte Entropie von <math>X</math> gegeben <math>A</math> durch Ersetzen der Wahrscheinlichkeit durch die [[bedingte Wahrscheinlichkeit]], d.&nbsp;h.
:<math>H(X|A) := -\sum_{x\in M}P(X=x|A)\,\log_b P(X=x|A)</math>.

Jetzt sei <math>Y</math> eine diskrete Zufallsvariable mit Wertevorrat <math>L</math>. Dann ist die bedingte Entropie von <math>X</math> gegeben <math>Y</math> definiert als gewichtetes Mittel der bedingten Entropien von <math>X</math> gegeben den Ereignissen <math>Y=y</math> für <math>y\in L</math>, d.&nbsp;h.
:<math>H(X|Y) := \sum_{y\in L:P(Y=y)>0}P(Y=y)\,H(X|Y=y)</math>.

Auf höherer Abstraktionsebene handelt es sich bei <math>H(X|A)</math> um den bedingten Erwartungswert der [[Informationsgehalt|Informationsfunktion]] <math>I_{X|A}(x) := -\log_b P(X=x|A)</math> gegeben <math>A</math> und bei
<math>H(X|Y)</math> um den Erwartungswert der Funktion <math> I_{X|Y}(x,y) := -\log_b P(X=x|Y=y) </math>.

== Eigenschaften ==
[[Datei:Entroy XY.png|mini|370px|Ein gedächtnisloser [[Übertragungskanal|Kanal]] verbindet zwei Quellen. Die [[Transinformation]] I(x;y) ist diejenige Information, die von X gesendet und auch von Y empfangen wurde.]]

Eine einfache Rechnung zeigt
:<math>H(X|Y) = H(X,Y) - H(Y)</math>,
also ist die Unsicherheit von <math>X</math> gegeben <math>Y</math> gleich der Unsicherheit von <math>X</math> und <math>Y</math> abzüglich der Unsicherheit von <math>Y</math>.

Es ist <math>H(X|Y) \leq H(X)</math> mit Gleichheit genau dann, wenn <math>X</math> und <math>Y</math> stochastisch unabhängig sind. Dies folgt aus der Tatsache, dass <math>H(X,Y) = H(X) + H(Y)</math> genau dann gilt, wenn <math>X</math> und <math>Y</math> stochastisch unabhängig sind. Außerdem bedeutet es, dass <math>H(Y) = H(Y|X)</math> ist, also die komplette empfangene Information nur Fehlinformation ist. Analog geht die komplette Information von der Quelle X verloren, so dass dann auch keine [[Transinformation]] vorhanden ist.

Außerdem gilt
:<math>H(X|Y) \geq 0</math>,
mit Gleichheit genau dann, wenn <math>X</math> funktional von <math>Y</math> abhängt, d.&nbsp;h. <math>X=f(Y)</math> für eine [[Funktion (Mathematik)|Funktion]] <math>f</math>.

== Blockentropie ==
Übertragen auf eine multivariate Zufallsvariable <math>X</math> der Länge <math>k</math>, als Darstellung für einen <math>k</math>-Block von Symbolen <math>(x_1,\dots,x_k)</math>, lässt sich die bedingte Entropie <math>h_k</math> definieren als die Unsicherheit eines Symbols <math>x_{k+1}</math> (nach einem bestimmten vorgegebenen <math>k</math>-Block):
:<math>h_k := H_{k+1} - H_k</math> mit <math>h_0 := H_1</math>,
wobei <math>H_i</math> die [[Blockentropie]] bezeichnet. Für die bedingte Entropie <math>h_1</math>, also die Unsicherheit eines Symbols nach einem <math>1</math>-Block, folgt:
:<math>h_1 = H_2 - H_1 = H(X) + H(Y|X) - H(X) = H(Y|X)</math>

Die Definitionen der Blockentropie und der bedingten Entropie sind im Grenzübergang gleichwertig, vgl. [[Quellentropie]].

In engem Zusammenhang zur bedingten Entropie steht auch die [[Transinformation]], die die Stärke des statistischen Zusammenhangs zweier Zufallsgrößen angibt.

== Beispiel ==
Sei ''X'' eine Quelle, die periodisch die Zeichen ''...00100010001000100010...'' sendet.

Nun soll unter Berücksichtigung vorangegangener Zeichen die bedingte Entropie des aktuell zu beobachtenden Zeichens berechnet werden.

=== Keine berücksichtigten Zeichen ===
{| class="wikitable" style="width:100%;"
|width="600"|
:<math>p_0 = P(X=0)= \textstyle \frac{3}{4} </math>
:<math>p_1 = P(X=1)= \textstyle \frac{1}{4} </math>

:<math>H(X) = H(p_0,p_1)= - \textstyle \frac{3}{4} \sdot \log_2{ ( \textstyle \frac{3}{4} )} - \textstyle \frac{1}{4} \sdot \log_2{ (\textstyle \frac{1}{4})} = 0{,}811\,bit</math>
Die Berechnung erfolgt nach der Definition der [[Entropie (Informationstheorie)|Entropie]].
|
Wahrscheinlichkeitstabelle:

{| class="wikitable"
|
|'''x=0'''
|'''x=1'''
|-
|'''P(X=x)'''
|align="center"|<math>\textstyle \frac{3}{4}</math>
|align="center"|<math>\textstyle \frac{1}{4}</math>
|}
|}

=== Ein berücksichtigtes Zeichen === 
{| class="wikitable" style="width:100%;"
|width="600"|
Sei nun X:=x<sub>t</sub> und Y:=x<sub>t-1</sub>.
Es ergeben sich folgende Wahrscheinlichkeiten:
:<math>P(X=0|Y=0) = \textstyle \frac{2}{3} \qquad P(X=1|Y=0) = \textstyle \frac{1}{3}</math>
:<math>P(X=0|Y=1) = 1 \qquad P(X=1|Y=1) = 0 </math>

:<math>H(X|Y) = \sum_{y \in Y}^{} \sum_{x \in X}^{} P(Y=y) \sdot H(X = x|Y = y) </math>
:<math>\qquad = \sum_{y \in Y}^{} P(Y=y) \sdot H(X|Y=y)</math>
:<math>\qquad = P(Y=0) \sdot H(X|Y=0) + P(Y=1) \sdot H(X|Y=1) </math>
:<math>\qquad = \textstyle \frac{3}{4} \sdot
\begin{matrix}
   \underbrace{H(X|Y=0)} \\
   {}^{\rm H(\;P(X=0|Y=0)\;,\;P(X=1|Y=0)\;) }\\[-4.5ex]
\end{matrix}
 + \textstyle \frac{1}{4} \sdot
\begin{matrix}
   \underbrace{H(X|Y=1)} \\
   {}^{\rm H(\;P(X=0|Y=1)\;,\;P(X=1|Y=1)\;) }\\[-4.5ex]
\end{matrix}
</math>

:<math>
\qquad = \textstyle \frac{3}{4} \sdot H (\textstyle \frac{2}{3},\textstyle \frac{1}{3} ) +
\begin{matrix}
  \textstyle \frac{1}{4} \sdot \underbrace{ H(1,0)} \\
  {}^{\rm = 0}\\[-4.5ex]
\end{matrix}
 =0{,}689 \, bit
</math>
|
Wahrscheinlichkeitstabellen:
{|
|width="200"|
{| class="wikitable"
|<nowiki>P(X|Y)</nowiki>
|'''x=0'''
|'''x=1'''
|-
|'''y=0'''
|align="center"|<math>\textstyle \frac{2}{3}</math>
|align="center"|<math>\textstyle \frac{1}{3}</math>
|-
|'''y=1'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|}
Wobei gilt: <br />
<math>P(X|Y) = P( X=x | Y=y )</math><br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>= P( x_t=x | x_{t-1}=y )</math>
|valign="top"|
{| class="wikitable"
|
|'''y=0'''
|'''y=1'''
|-
|<math>P(Y=y)</math>
|align="center"|<math>\textstyle \frac{3}{4}</math>
|align="center"|<math>\textstyle \frac{1}{4}</math>
|}
|}
|}

=== Zwei berücksichtigte Zeichen ===
{| class="wikitable" style="width:100%;"
|width="600"|
Sei X:=x<sub>t</sub> und Y:=(x<sub>t-2</sub>, x<sub>t-1</sub>).
Es ergeben sich folgende Wahrscheinlichkeiten:

:<math>P(X=0|Y=(0,0)) = \textstyle \frac{1}{2} \qquad P(X=1|Y=(0,0)) = \textstyle \frac{1}{2} </math>
:<math>P(X=0|Y=(0,1)) = 1 \qquad P(X=1|Y=(0,1)) = 0 </math>
:<math>P(X=0|Y=(1,0)) = 1 \qquad P(X=1|Y=(1,0)) = 0 </math>
: Y=(1,1) kommt in der Quelle nie vor, braucht also nicht betrachtet zu werden.

:<math> H(X|Y) = \sum_{y \in Y}^{} P(Y=y) \sdot H(X|Y=y)</math>
:<math> = \textstyle \frac{1}{2} \sdot H(X|Y=(0,0)) + \textstyle \frac{1}{4} \sdot H(X|Y=(0,1)) + \textstyle \frac{1}{4} \sdot H(X|Y=(1,0)) </math>
:<math> = \textstyle \frac{1}{2} \sdot H(\textstyle \frac{1}{2}|\textstyle \frac{1}{2}) +
\begin{matrix}
  \underbrace{\textstyle \frac{1}{4} \sdot H(1,0)} \\
  {}^{\rm = 0}\\[-4.5ex]
\end{matrix}
+
\begin{matrix}
  \underbrace{\textstyle \frac{1}{4} \sdot H(0|1)} \\
  {}^{\rm = 0}\\[-4.5ex]
\end{matrix}
 </math>
:<math> = \textstyle \frac{1}{2} \, bit</math>
|
Wahrscheinlichkeitstabellen:
{|
|
{| class="wikitable"
|<nowiki>P(X|Y)</nowiki>
|'''X=0'''
|'''X=1'''
|-
|'''y=(0,0)'''
|align="center"|<math>\textstyle \frac{1}{2}</math>
|align="center"|<math>\textstyle \frac{1}{2}</math>
|-
|'''y=(0,1)'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|-
|'''y=(1,0)'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|-
|'''y=(1,1)'''
|align="center"|<math>\textstyle -</math>
|align="center"|<math>\textstyle -</math>
|}
Wobei gilt: <math>P(X|Y)</math><br /><math>=P( x_t \mid (x_{t-2},x_{t-1}) )</math>
|valign="top"|
{| class="wikitable"
|
|'''y=(0,0)'''
|'''y=(0,1)'''
|'''y=(1,0)'''
|'''y=(1,1)'''
|-
|'''P(Y=y)'''
|align="center"|<math>\textstyle \frac{1}{2}</math>
|align="center"|<math>\textstyle \frac{1}{4}</math>
|align="center"|<math>\textstyle \frac{1}{4}</math>
|align="center"|<math>\textstyle 0</math>
|}
Wobei gilt: <br /><math>P(Y)=P(y_t,y_{t-1})</math>
|}
|}

=== Drei berücksichtigte Zeichen ===
{| class="wikitable" style="width:100%;"
|valign="top"|
:<math>H(X|Y) = 0 \,</math>

Sind bereits drei nacheinander folgende Zeichen bekannt, so ist damit auch das folgende Zeichen determiniert (denn die Quelle verhält sich ja periodisch). Somit erhält man keine neue Information über das nächste Zeichen. Demnach muss die Entropie null sein.
Dies kann man auch an der Wahrscheinlichkeitstabelle ablesen:
{|
|width="120"|
{| class="wikitable"
|<nowiki>P(X|Y)</nowiki>
|'''X=0'''
|'''X=1'''
|-
|'''y=(0,0,0)'''
|align="center"|<math>\textstyle 0</math>
|align="center"|<math>\textstyle 1</math>
|-
|'''y=(0,0,1)'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|-
|'''y=(0,1,0)'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|-
|'''y=(0,1,1)'''
|align="center"|<math>\textstyle -</math>
|align="center"|<math>\textstyle -</math>
|-
|'''y=(1,0,0)'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|-
|'''y=(1,0,1)'''
|align="center"|<math>\textstyle -</math>
|align="center"|<math>\textstyle -</math>
|-
|'''y=(1,1,0)'''
|align="center"|<math>\textstyle -</math>
|align="center"|<math>\textstyle -</math>
|-
|'''y=(1,1,1)'''
|align="center"|<math>\textstyle -</math>
|align="center"|<math>\textstyle -</math>
|}
|valign="top"|
Wobei gilt: <br />
<math>P(X|Y)=P( X=x | Y=y )</math><br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>=P( X=x_t | Y=(x_{t-3}, x_{t-2}, x_{t-1}) )</math>

Unmögliche Ereignisse werden hier mit "-" gekennzeichnet, z.&nbsp;B. bei y=(1,0,1). Diese Ausgabe wird die gegebene Quelle nie liefern, da nach einer Eins immer drei Nullen folgen.

Man sieht, dass in der Tabelle keine anderen Wahrscheinlichkeiten auftreten als 0 oder 1. Da nach der Definition der Entropie gilt
<math>H(0,1) = H(1,0) = 0</math>, muss schließlich die Entropie <math>H(X|Y) = 0</math> sein.
|}
|}

'''Erläuterung zu den Wahrscheinlichkeitstabellen'''

Die Tabellen beziehen sich auf die obige Beispielzeichensequenz.
{|width="100%"
|valign="top"|
{| class="wikitable"
|<nowiki>P(X|Y)</nowiki>
|'''x=0'''
|'''x=1'''
|-
|'''y=0'''
|align="center"|<math>\textstyle \frac{2}{3}</math>
|align="center"|<math>\textstyle \frac{1}{3}</math>
|-
|'''y=1'''
|align="center"|<math>\textstyle 1</math>
|align="center"|<math>\textstyle 0</math>
|}
Wobei gilt: <br />
<math>P(X|Y) = P( X=x|Y=y ) = P( X=x_t|Y=x_{t-1} ) = p(x_{t}| x_{t-1})</math>

Hier betrachtet man ein Zeichen <math>X</math> unter der Bedingung des vorangegangenen Zeichens <math>Y</math>. Ist beispielsweise ein Zeichen <math>Y=1</math>, so lautet die Frage: Mit welcher Wahrscheinlichkeit ist das darauffolgende Zeichen <math>X=0</math> bzw. <math>X=1</math>? Für <math>Y=1</math> ist das nächste Zeichen <math>X</math> immer <math>0</math>. Somit ist <math>P(X=0|Y=1) = 1</math>. Außerdem folgt daraus, dass <math>P(X=1|Y=1) = 0</math> ist, da die Zeilensumme immer Eins ist.
|width="45"|
|valign="top" width="45%" |
{| class="wikitable"
|P(X)
|'''x<sub>t</sub>=0'''
|'''x<sub>t</sub>=1'''
|-
|'''x<sub>t-1</sub>=0'''
|align="center"|<math>\textstyle \frac{1}{2}</math>
|align="center"|<math>\textstyle \frac{1}{4}</math>
|-
|'''x<sub>t-1</sub>=1'''
|align="center"|<math>\textstyle \frac{1}{4}</math>
|align="center"|<math>\textstyle 0</math>
|}
Wobei gilt: <br /><math>P(X)=P(X=(x_t,x_{t-1}))=P(p(x_t),p(x_{t-1}))
=p(x_t, x_{t-1})</math>

Hier betrachtet man die Auftrittshäufigkeit einer Zeichenkombination. Man kann aus der Tabelle lesen, dass die Buchstabenkombinationen (0,1) und (1,0) genauso häufig auftreten. Die Summe aller Matrixeinträge ergibt Eins.
|}

=== Entropie und Informationsgehalt ===

Die Entropie fällt bei diesem Beispiel umso stärker, je mehr Zeichen berücksichtigt werden (siehe auch: [[Markow-Prozess]]). Wenn die Anzahl der berücksichtigten Zeichen hinreichend groß gewählt wird, so konvergiert die Entropie gegen Null.

Möchte man den [[Informationsgehalt]] der gegebenen Zeichenfolge aus n=12 Zeichen berechnen, so erhält man nach Definition I<sub>ges</sub> = n⋅H(X|Y) bei...
:...keinem berücksichtigten Zeichen 9,39 bit Gesamtinformation. (Informationsgehalt statistisch unabhängiger Ereignisse)
:...einem berücksichtigten Zeichen 8,26 bit Gesamtinformation.
:...zwei berücksichtigten Zeichen 6 bit Gesamtinformation.
:...drei berücksichtigten Zeichen 0 bit Gesamtinformation.

==In dynamischen Systemen==

In glatten dynamischen Systemen spielt die bedingte Entropie eine zentrale Rolle beim Verständnis invarianten Maßen. Insbesondere bei partiell hyperbolischen Systemen quantifiziert die Entropie, bedingt auf stabile Blätter, die verbleibende Komplexität der Bahnen in instabilen Richtungen. Diese Struktur ist grundlegend für die Ledrappier–Young-Dimensionsformel, die die lokale Hausdorff-Dimension eines Maßes als Summe von Entropie-zu-Expansions-Verhältnissen ausdrückt. Eine moderne Darstellung unter Verwendung der Rokhlin-Disintegration bietet Alpay (2025).<ref name="Alpay2025">{{cite web |last=Alpay |first=Faruk |title=SRB Measures and the Ledrappier–Young Dimension Formula |language=en |year=2025 |url=https://doi.org/10.5281/zenodo.15353623 |website=Zenodo |access-date=2025-05-07}}</ref>

== Einzelnachweise ==
<references />

== Literatur ==
* Martin Werner: ''Information und Codierung.'' Grundlagen und Anwendungen, 2. Auflage, Vieweg+Teubner Verlag, Wiesbaden 2008, ISBN 978-3-8348-0232-3.
* Karl Steinbuch, Werner Rupprecht: ''Nachrichtentechnik.'' Eine einführende Darstellung, Springer Verlag, Berlin / Heidelberg 1967.
* R. Mathar: ''Informationstheorie.'' Diskrete Modelle und Verfahren, B.G. Teubner Verlag, Stuttgart 1996, ISBN 978-3-519-02574-0.

== Weblinks ==
* [https://www.math.uni-frankfurt.de/~ismi/wakolbinger/teaching/StofI1213/1213Vorlesung14_k.pdf Vorlesungsskript: ''Gemeinsame Entropie und bedingte Entropie''.] (abgerufen am 19. Januar 2018)
* [https://graphics.ethz.ch/teaching/former/infotheory0607/Downloads/slides4_1.pdf Bedingte Entropie] (abgerufen am 19. Januar 2018)
* [http://www.sfs.uni-tuebingen.de/~gjaeger/lehre/statist_ss02/5_07.pdf Statistische Methoden in der Sprachverarbeitung] (abgerufen am 19. Januar 2018)
* [https://www.cs.uni-potsdam.de/ti/lehre/06-Kryptographie/slides/slides-02.pdf Datensicherheit und Shannons Theorie] (abgerufen am 19. Januar 2018)
* [https://user.phil.hhu.de/~cwurm/wp-content/uploads/2017/07/skript-induktive-logik.pdf Wahrscheinlichkeit, Statistik, Induktion] (abgerufen am 19. Januar 2018)


[[Kategorie:Stochastik]]
[[Kategorie:Wahrscheinlichkeitsrechnung]]
[[Kategorie:Informationstheorie]]