Aufgaben:Aufgabe 3.3: Entropie von Ternärgrößen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(12 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2754__Inf_A_3_3.png|right|]]
+
[[Datei:P_ID2754__Inf_A_3_3.png|right|frame|Vorgegebene Entropiefunktionen]]
Rechts sehen Sie die Entropiefunktionen <i>H</i><sub>R</sub>(<i>p</i>), <i>H</i><sub>B</sub>(<i>p</i>) und <i>H</i><sub>G</sub>(<i>p</i>), wobei &bdquo;R&rdquo; für &bdquo;Rot&rdquo; steht, usw. Für alle Zufallsgrößen lautet die Wahrscheinlichkeitsfunktion:
+
Rechts sehen Sie die Entropiefunktionen&nbsp; $H_{\rm R}(p)$,&nbsp; $H_{\rm B}(p)$&nbsp; und&nbsp; $H_{\rm G}(p)$, wobei&nbsp; $\rm R$&nbsp; für &bdquo;Rot&rdquo; steht,&nbsp; $\rm B$&nbsp; für &bdquo;Blau&rdquo; und&nbsp; $\rm G$&nbsp; für &bdquo;Grün&rdquo;.&nbsp; Die Wahrscheinlichkeitsfunktionen lauten für alle Zufallsgrößen:
:$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm}, p_2\hspace{0.05cm}, p_3\hspace{0.05cm}]\hspace{0.3cm}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} |X| = 3\hspace{0.05cm}.$$
+
:$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm},\ p_2\hspace{0.05cm},\ p_3\hspace{0.05cm}]\hspace{0.3cm}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} |X| = 3\hspace{0.05cm}.$$
Es gilt der Zusammenhang <i>p</i><sub>1</sub>&nbsp;=&nbsp;<i>p</i> und <i>p</i><sub>2</sub>&nbsp;= 1 &ndash;&nbsp;<i>p</i><sub>3</sub>&nbsp;&ndash;&nbsp;<i>p</i>.
+
Für den Fragebogen gilt der Zusammenhang&nbsp; $p_1 = p$&nbsp; und&nbsp; $p_2 = 1 - p_3- p$.
  
 
Die Wahrscheinlichkeitsfunktion einer Zufallsgröße
 
Die Wahrscheinlichkeitsfunktion einer Zufallsgröße
:$$X = \{\hspace{0.05cm}x_1\hspace{0.05cm}, \hspace{0.05cm} x_2\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm} ,\hspace{0.05cm} x_{\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.05cm} x_{M}\hspace{0.05cm}\}$$
+
:$$X = \big \{\hspace{0.05cm}x_1\hspace{0.05cm}, \hspace{0.15cm} x_2\hspace{0.05cm},\hspace{0.15cm} \text{...}\hspace{0.1cm} ,\hspace{0.15cm} x_{\mu}\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm} , \hspace{0.15cm} x_{M}\hspace{0.05cm}\big  \}$$
mit dem Symbolumfang |<i>X</i>|&nbsp;=&nbsp;<i>M</i> lautet allgemein:
+
mit dem Symbolumfang&nbsp; $|X| = M$&nbsp; lautet allgemein:
:$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm}, \hspace{0.05cm} p_2\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm} ,\hspace{0.05cm} p_{\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.05cm} p_{M}\hspace{0.05cm}]\hspace{0.05cm}.$$
+
:$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm}, \hspace{0.15cm} p_2\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm} ,\hspace{0.15cm} p_{\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.15cm} p_{M}\hspace{0.05cm}]\hspace{0.05cm}.$$
 
Die Entropie (Unsicherheit) dieser Zufallsgröße berechnet sich entsprechend der Gleichung
 
Die Entropie (Unsicherheit) dieser Zufallsgröße berechnet sich entsprechend der Gleichung
:$$H(X) = {\rm E} \left [{\rm log}_2 \hspace{0.1cm} {1}/{P_X(X)} \right ]\hspace{0.05cm},$$
+
:$$H(X) = {\rm E} \big [\log_2 \hspace{0.05cm} {1}/{P_X(X)} \big ]\hspace{0.05cm},$$
und liegt stets im Bereich 0 &#8804; <i>H</i>(<i>X</i>) &#8804; log<sub>2</Sub> |<i>X</i>|. Die untere Schranke <i>H</i>(<i>X</i>) = 0 ergibt sich, wenn eine beliebige Wahrscheinlichkeit <i>p<sub>&mu;</sub></i> = 1 ist und alle anderen 0 sind. Die obere Schranke soll hier wie in [Kra13] hergeleitet werden:
+
und liegt stets im Bereich&nbsp; $0 \le H(X) \le  \log_2 \hspace{0.05cm}  |X|$.  
  
:* Durch Erweiterung obiger Gleichung um |<i>X</i>| in Zähler und Nenner erhält man unter Verwendung von log<sub>2</sub>(<i>x</i>) = ln(<i>x</i>)/ln(2):
+
*Die untere Schranke&nbsp; $H(X) = 0$&nbsp; ergibt sich, wenn eine beliebige Wahrscheinlichkeit&nbsp; $p_\mu = 1$&nbsp; ist und alle anderen Null sind.
:$$H(X) = \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [{\rm ln} \hspace{0.1cm} \frac{1}{|X| \cdot P_X(X)} \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
+
 
:* Wie aus nachfolgender Grafik hervorgeht, gilt die Abschätzung ln(<i>x</i>) &#8804; <i>x</i> &ndash; 1 mit der Identität für <i>x</i>&nbsp;=&nbsp;1. Somit kann geschrieben werden:
+
*Die obere Schranke soll hier wie in der Vorlesung &bdquo;Information Theory&rdquo; von&nbsp; [[Biografien_und_Bibliografien/Lehrstuhlinhaber_des_LNT#Prof._Dr._sc._techn._Gerhard_Kramer_.28seit_2010.29|Gerhard Kramer]]&nbsp; an der TU München hergeleitet werden:
:$$H(X) \le \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [\frac{1}{|X| \cdot P_X(X)} -1 \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
+
[[Datei:P_ID2755__Inf_A_3_3_B_neu.png|right|frame|Obere Abschätzung für den natürlichen Logarithmus]]
[[Datei:P_ID2755__Inf_A_3_3_B_neu.png|right|]]
+
:* Durch Erweiterung obiger Gleichung um&nbsp; $|X|$&nbsp; in Zähler und Nenner erhält man unter Verwendung von&nbsp; $\log_2 \hspace{0.05cm}x= \ln(x)/\ln(2)$:
:* In Aufgabe A3.2 wurde für den Fall, dass <i>p<sub>&mu;</sub></i> &ne; 0 für alle <i>&mu;</i> gilt, der Erwartungswert E[1/<i>P<sub>X</sub></i>(<i>X</i>)] zu |<i>X</i>| berechnet. Damit verschwindet der erste Term und man erhält das bekannte Ergebnis:
+
::$$H(X) = \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [{\rm ln} \hspace{0.1cm} \frac{1}{|X| \cdot P_X(X)} \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
:$$H(X) \le {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
+
:* Wie aus nebenstehender Grafik hervorgeht, gilt die Abschätzung&nbsp; $\ln(x) \le x-1$&nbsp; mit der Identität für&nbsp; $x=1$.&nbsp; Somit kann geschrieben werden:
<b>Hinweis:</b> Die Aufgabe gehört zu Kapitel 3.1. Es wird auf die binäre Entropiefunktion Bezug genommen:
+
::$$H(X) \le \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [\frac{1}{|X| \cdot P_X(X)} -1 \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
:$$H_{{\rm bin}}(p) =  p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +  
+
:* In der&nbsp; [[Aufgaben:3.2_Erwartungswertberechnungen|Aufgabe 3.2]]&nbsp; wurde für den Fall&nbsp; $p_\mu \ne 0$&nbsp; für alle&nbsp; $\mu$&nbsp; der Erwartungswert&nbsp; ${\rm E} \big [\log_2 \hspace{0.05cm} {1}/{P_X(X)} \big ] =|X|$&nbsp; berechnet.&nbsp; Damit verschwindet der erste Term und man erhält das bekannte Ergebnis:
 +
::$$H(X) \le {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweise:''
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu den 2D-Zufallsgrößen]].
 +
*Insbesondere wird Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Wahrscheinlichkeitsfunktion_und_Entropie|Wahrscheinlichkeitsfunktion undEntropie]].
 +
*Ausgegangen wird hier von der gleichen Konstellation wie in der&nbsp; [[Aufgaben:Aufgabe_3.2:_Erwartungswertberechnungen|Aufgabe 3.2]].
 +
 +
*Die Gleichung der binären Entropiefunktion lautet:
 +
:$$H_{\rm bin}(p) =  p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +  
 
  (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$
 
  (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$
  
Zeile 31: Zeile 45:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Aussagen gelten für die rote Entropiefunktion <i>H</i><sub>R</sub>(<i>p</i>)?
+
{Welche Aussagen gelten für die rote Entropiefunktion&nbsp; $H_{\rm R}(p)$?
 
|type="[]"}
 
|type="[]"}
+ <i>H</i><sub>R</sub>(<i>p</i>) ergibt sich z.B. mit <i>p</i><sub>3</sub> = 0, <i>p</i><sub>1</sub> = <i>p</i>, <i>p</i><sub>2</sub> = 1 &ndash; <i>p</i>.
+
+ $H_{\rm R}(p)$&nbsp; ergibt sich zum Beispiel mit &nbsp;$p_1 = p$, &nbsp;$p_2 = 1- p$  &nbsp;und&nbsp; $p_3 = 0$.
+ <i>H</i><sub>R</sub>(<i>p</i>) ist identisch mit der binären Entropiefunktion <i>H</i><sub>bin</sub></i>(<i>p</i>).
+
+ $H_{\rm R}(p)$&nbsp; ist identisch mit der binären Entropiefunktion&nbsp; $H_{\rm bin}(p)$.
  
  
{Welche Eigenschaften weist die binäre Entropiefunktion auf?
+
{Welche Eigenschaften weist die binäre Entropiefunktion&nbsp; $H_{\rm bin}(p)$&nbsp; auf?
 
|type="[]"}
 
|type="[]"}
+ <i>H</i><sub>bin</sub></i>(<i>p</i>) ist konkav hinsichtlich des Parameters <i>p</i>.
+
+ $H_{\rm bin}(p)$&nbsp; ist konkav hinsichtlich des Parameters&nbsp; $p$.
- Es gilt Max[<i>H</i><sub>bin</sub></i>(<i>p</i>)] = 2 bit.
+
- Es gilt&nbsp; $\text {Max [H_{\rm bin}(p)] = 2$&nbsp; bit.
  
  
{Welche Aussagen gelten für die blaue Entropiefunktion <i>H</i><sub>B</sub>(<i>p</i>)?
+
{Welche Aussagen gelten für die blaue Entropiefunktion&nbsp; $H_{\rm B}(p)$?
 
|type="[]"}
 
|type="[]"}
+ <i>H</i><sub>B</sub>(<i>p</i>) ergibt sich z.B. mit <i>p</i><sub>3</sub> = 1/2, <i>p</i><sub>1</sub> = <i>p</i>, <i>p</i><sub>2</sub> = 1/2 &ndash; <i>p</i>.
+
+ $H_{\rm B}(p)$&nbsp; ergibt sich beispielsweise mit &nbsp;$p_1 = p$, &nbsp;$p_2 = 1/2- p$  &nbsp;und&nbsp; $p_3 = 1/2$.
+ Es gilt <i>H</i><sub>B</sub>(<i>p</i> = 0) = 1 bit.
+
+ Es gilt&nbsp; $H_{\rm B}(p = 0)= 1$&nbsp; bit.  
- Es gilt Max[<i>H</i><sub>B</sub>(<i>p</i>)] = log<sub>2</sub> (3) bit.
+
- Es gilt&nbsp; $\text {Max } [H_{\rm B}(p)] = \log_2 \hspace{0.1cm} (3)$&nbsp; bit.
  
  
{Welche Aussagen gelten für die grüne Entropiefunktion <i>H</i><sub>G</sub>(<i>p</i>)?
+
{Welche Aussagen gelten für die grüne Entropiefunktion&nbsp; $H_{\rm G}(p)$?
 
|type="[]"}
 
|type="[]"}
+ <i>H</i><sub>G</sub>(<i>p</i>) ergibt sich z.B. mit <i>p</i><sub>3</sub> = 1/3, <i>p</i><sub>1</sub> = <i>p</i>, <i>p</i><sub>2</sub> = 2/3 &ndash; <i>p</i>.
+
+ $H_{\rm G}(p)$&nbsp; ergibt sich beispielsweise mit &nbsp;$p_1 = p$, &nbsp;$p_2 = 2/3- p$  &nbsp;und&nbsp; $p_3 = 1/3$.
- Es gilt <i>H</i><sub>G</sub>(<i>p</i> = 0) = 1 bit.
+
- Es gilt&nbsp; $H_{\rm G}(p = 0)= 1$&nbsp; bit.
+ Es gilt Max[<i>H</i><sub>G</sub>(<i>p</i>)] = log<sub>2</sub> (3) bit.
+
+ Es gilt&nbsp; $\text {Max } [H_{\rm G}(p)] = \log_2 \hspace{0.1cm} (3)$ bit.
  
  
Zeile 62: Zeile 76:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;<u>Beide Aussagen sind richtig.</u> Setzt man <i>p</i><sub>3</sub> = 0 und formal <i>p</i><sub>1</sub> = <i>p</i> &nbsp;&#8658;&nbsp; <i>p</i><sub>2</sub> = 1 &ndash; <i>p</i>, so ergibt sich die binäre Entropiefunktion
+
'''(1)'''&nbsp; <u>Beide Aussagen sind richtig:</u>  
 +
*Setzt man &nbsp;$p_3 = 0$ und formal &nbsp;$p_1 = p$ &nbsp; &#8658; &nbsp; &nbsp;$p_2 = 1- p$, so ergibt sich die binäre Entropiefunktion
 
:$$H_{\rm bin}(p) =  p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +  
 
:$$H_{\rm bin}(p) =  p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +  
 
  (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$
 
  (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$
  
<b>2.</b>&nbsp;&nbsp;Man kann die binäre Entropiefunktion wegen log<sub>2</sub>(<i>x</i>) = ln(<i>x</i>)/ln(2) auch in die folgende Form bringen:
 
:$$H_{\rm bin}(p) = \frac{-1}{{\rm ln}(2)} \cdot \left [  p \cdot {\rm ln}(p)  +
 
(1-p) \cdot {\rm ln}(1-p) \right ] \hspace{0.05cm}.$$
 
Die erste Ableitung führt zum Ergebnis
 
:$$\frac {\rm dH_{\rm bin}(p)}{\rm dp} \hspace{0.15cm}  =  \hspace{0.15cm} \frac{-1}{{\rm ln}(2)} \cdot \left [  {\rm ln}(p)  + p \cdot \frac{1}{p} -
 
  {\rm ln}(1-p) - (1-p) \cdot \frac{1}{1-p} \right ] =\\
 
=  \hspace{0.15cm} \frac{1}{{\rm ln}(2)} \cdot \left [ {\rm ln}(1-p) - {\rm ln}(p)  \right ] = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{p} \hspace{0.05cm}.$$
 
Durch Nullsetzen dieser Ableitung erhält man den Abszissenwert <i>p</i> = 0.5, der zum Maximum der Entropiefunktion führt: <i>H</i><sub>bin</sub>(<i>p</i> = 0.5) = 1 bit &nbsp;&#8658;&nbsp; Lösungsvorschlag 2 ist falsch..
 
  
Durch nochmaliges Differenzieren erhält man für die zweite Ableitung:
+
'''(2)'''&nbsp; Richtig ist allein der <u>Lösungsvorschlag 1</u>:
:$$\frac {\rm d^2H_{\rm bin}(p)}{\rm dp^2} = \frac{1}{{\rm ln}(2)} \cdot \left
+
*Man kann die binäre Entropiefunktion wegen&nbsp; $\log(x) = \ln(x)/\ln(2)$&nbsp; auch in die folgende Form bringen:
 +
:$$H_{\rm bin}(p) = \frac{-1}{{\rm ln}(2)} \cdot \big [  p \cdot {\rm ln}(p)  +
 +
(1-p) \cdot {\rm ln}(1-p) \big ] \hspace{0.05cm}.$$
 +
*Die erste Ableitung führt zum Ergebnis
 +
:$$\frac {{\rm d}H_{\rm bin}(p)}{{\rm d}p} = \frac{-1}{{\rm ln}(2)} \cdot \big [  {\rm ln}(p)  + p \cdot \frac{1}{p} -
 +
  {\rm ln}(1-p) - (1-p) \cdot \frac{1}{1-p} \big ] =
 +
\frac{1}{{\rm ln}(2)} \cdot \big [ {\rm ln}(1-p) - {\rm ln}(p)  \big ] = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{p} \hspace{0.05cm}.$$
 +
*Durch Nullsetzen dieser Ableitung erhält man den Abszissenwert&nbsp; $p = 0.5$, der zum Maximum der Entropiefunktion führt: &nbsp; $H_{\rm bin}(p =0.5) = 1$ bit <br>&#8658; &nbsp; der Lösungsvorschlag 2 ist falsch.
 +
*Durch nochmaliges Differenzieren erhält man für die zweite Ableitung:
 +
:$$\frac {{\rm d}^2H_{\rm bin}(p)}{{\rm d}p^2} = \frac{1}{{\rm ln}(2)} \cdot \left
 
  [  \frac{-1}{1-p}  - \frac{1}{p}    \right ] =
 
  [  \frac{-1}{1-p}  - \frac{1}{p}    \right ] =
 
\frac{-1}{{\rm ln}(2) \cdot p \cdot (1-p)}  \hspace{0.05cm}.$$
 
\frac{-1}{{\rm ln}(2) \cdot p \cdot (1-p)}  \hspace{0.05cm}.$$
Diese Funktion ist im gesamten Definitionsgebiet 0 &#8804; <i>p</i> &#8804; 1 negativ &nbsp;&#8658;&nbsp; <i>H</i><sub>bin</sub>(<i>p</i>) ist konkav &nbsp;&#8658;&nbsp; Richtig ist dementsprechend (allein) der <u>Lösungsvorschlag 1</u>.
+
*Diese Funktion ist im gesamten Definitionsgebiet&nbsp; $0 &#8804; p &#8804; 1$&nbsp; negativ &nbsp; &#8658; &nbsp; $H_{\rm bin}(p)$ ist konkav &nbsp; &#8658; &nbsp; der Lösungsvorschlag 1 ist richtig.
  
<b>3.</b>&nbsp;&nbsp;Richtig sind hier die <u>Aussagen 1 und 2</u>:
 
  
:* Für <i>p</i> = 0 erhält man die Wahrscheinlichkeitsfunktion <i>P<sub>X</sub></i>(<i>X</i>) = [0, 1/2, 1/2] &nbsp;&#8658;&nbsp; <i>H</i>(<i>X</i>) = 1 bit.
 
  
:* Das Maximum unter der Voraussetzung <i>p</i><sub>3</sub> = 1/2 ergibt sich für <i>p</i><sub>1</sub> = <i>p</i><sub>2</sub> = 1/4:
+
[[Datei:P_ID2756__Inf_A_3_3_ML.png|right|frame|Drei Entropiefunktionen mit&nbsp; $M = 3$]]
:$$P_X(X) = [\hspace{0.05cm}1/4\hspace{0.05cm}, \hspace{0.05cm} 1/4\hspace{0.05cm},\hspace{0.05cm} 1/2 \hspace{0.05cm}]
+
'''(3)'''&nbsp; Richtig sind hier die <u>Aussagen 1 und 2</u>:
 +
* Für&nbsp; $p = 0$&nbsp; erhält man die Wahrscheinlichkeitsfunktion&nbsp; $P_X(X) = \big  [\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.15cm} 1/2\hspace{0.05cm},\hspace{0.15cm} 1/2 \hspace{0.05cm} \big ]$ &nbsp; &#8658; &nbsp; $H(X) = 1$&nbsp; bit.
 +
* Das Maximum unter der Voraussetzung&nbsp; $p_3 = 1/2$&nbsp; ergibt sich für&nbsp; $p_1 = p_2 = 1/4$:
 +
:$$P_X(X) = \big  [\hspace{0.05cm}1/4\hspace{0.05cm}, \hspace{0.05cm} 1/4\hspace{0.05cm},\hspace{0.05cm} 1/2 \hspace{0.05cm} \big ]
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
{\rm Max} [H_{\rm B}(p)] = 1.5\,{\rm bit}
+
{\rm Max} \ [H_{\rm B}(p)] = 1.5 \ \rm bit
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
[[Datei:P_ID2756__Inf_A_3_3_ML.png|right|]]
+
*In kompakter Form lässt sich&nbsp; $H_{\rm B}(p)$&nbsp; mit der Einschränkung&nbsp; $0 &#8804; p &#8804; 1/2$&nbsp; wie folgt darstellen:
In kompakter Form lässt sich <i>H</i><sub>B</sub>(<i>p</i>) mit der Einschränkung 0 &#8804; <i>p</i> &#8804; 1/2 wie folgt darstellen:
 
 
:$$H_{\rm B}(p) = 1.0\,{\rm bit} + {1}/{2} \cdot H_{\rm bin}(2p)  
 
:$$H_{\rm B}(p) = 1.0\,{\rm bit} + {1}/{2} \cdot H_{\rm bin}(2p)  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
<b>4.</b>&nbsp;&nbsp;Richtig sind die <u> erste und letzte Aussage</u>. Der grüne Kurvenzug beinhaltet mit <i>p</i> = 1/3 auch die Gleichverteilung aller Wahrscheinlichkeiten &#8658; Max[<i>H</i><sub>G</sub>(<i>p</i>)] = log<sub>2</sub> (3) bit. Allgemein lässt sich der gesamte Kurvenverlauf im Bereich 0 &#8804; <i>p</i> &#8804; 2/3 wie folgt ausdrücken:
+
 
 +
'''(4)'''&nbsp; Richtig sind hier die <u> erste und letzte Aussage</u>:
 +
* Der grüne Kurvenzug beinhaltet mit&nbsp; $p = 1/3$&nbsp; auch die Gleichverteilung aller Wahrscheinlichkeiten  
 +
:$$ {\rm Max} \ [H_{\rm G}(p)] = \log_2 (3)\ \text{bit}.$$
 +
*Allgemein lässt sich der gesamte Kurvenverlauf im Bereich&nbsp; $0 &#8804; p &#8804; 2/3$&nbsp; wie folgt ausdrücken:
 
:$$H_{\rm G}(p) = H_{\rm G}(p= 0) + {2}/{3} \cdot H_{\rm bin}(3p/2)  
 
:$$H_{\rm G}(p) = H_{\rm G}(p= 0) + {2}/{3} \cdot H_{\rm bin}(3p/2)  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Aus der Grafik auf der Angabenseite erkennt man auch, dass folgende Bedingung erfüllt sein muss:
+
*Aus der Grafik auf der Angabenseite erkennt man auch, dass folgende Bedingung erfüllt sein muss:
 
:$$H_{\rm G}(p = 0) + {2}/{3}= {\rm log}_2 \hspace{0.01cm} (3)
 
:$$H_{\rm G}(p = 0) + {2}/{3}= {\rm log}_2 \hspace{0.01cm} (3)
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
H_{\rm G}(p= 0) = 1.585 - 0.667 = 0.918 \,{\rm bit}
 
H_{\rm G}(p= 0) = 1.585 - 0.667 = 0.918 \,{\rm bit}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Der Lösungsvorschlag 2 ist hier somit falsch. Zum gleichen Ergebnis gelangt man über die Gleichung
+
*Der zweite Lösungsvorschlag ist somit falsch.&nbsp; Zum gleichen Ergebnis gelangt man über die Gleichung
 
:$$H_{\rm G}(p = 0) = {1}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3)
 
:$$H_{\rm G}(p = 0) = {1}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3)
 
+{2}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3/2) = {\rm log}_2 \hspace{0.01cm} (3) -2/3 \cdot  
 
+{2}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3/2) = {\rm log}_2 \hspace{0.01cm} (3) -2/3 \cdot  
 
{\rm log}_2 \hspace{0.01cm} (2)
 
{\rm log}_2 \hspace{0.01cm} (2)
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Die Grafik zeigt nochmals die Ausgangsgrafik, aber nun mit Bemaßungen.
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu Informationstheorie|^3.1 Vorbemerkungen zu 2D-Zufallsgrößen^]]
+
[[Category:Aufgaben zu Informationstheorie|^3.1 Allgemeines zu 2D-Zufallsgrößen^]]

Version vom 30. Januar 2020, 15:46 Uhr

Vorgegebene Entropiefunktionen

Rechts sehen Sie die Entropiefunktionen  $H_{\rm R}(p)$,  $H_{\rm B}(p)$  und  $H_{\rm G}(p)$, wobei  $\rm R$  für „Rot” steht,  $\rm B$  für „Blau” und  $\rm G$  für „Grün”.  Die Wahrscheinlichkeitsfunktionen lauten für alle Zufallsgrößen:

$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm},\ p_2\hspace{0.05cm},\ p_3\hspace{0.05cm}]\hspace{0.3cm}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} |X| = 3\hspace{0.05cm}.$$

Für den Fragebogen gilt der Zusammenhang  $p_1 = p$  und  $p_2 = 1 - p_3- p$.

Die Wahrscheinlichkeitsfunktion einer Zufallsgröße

$$X = \big \{\hspace{0.05cm}x_1\hspace{0.05cm}, \hspace{0.15cm} x_2\hspace{0.05cm},\hspace{0.15cm} \text{...}\hspace{0.1cm} ,\hspace{0.15cm} x_{\mu}\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm} , \hspace{0.15cm} x_{M}\hspace{0.05cm}\big \}$$

mit dem Symbolumfang  $|X| = M$  lautet allgemein:

$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm}, \hspace{0.15cm} p_2\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm} ,\hspace{0.15cm} p_{\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.15cm} p_{M}\hspace{0.05cm}]\hspace{0.05cm}.$$

Die Entropie (Unsicherheit) dieser Zufallsgröße berechnet sich entsprechend der Gleichung

$$H(X) = {\rm E} \big [\log_2 \hspace{0.05cm} {1}/{P_X(X)} \big ]\hspace{0.05cm},$$

und liegt stets im Bereich  $0 \le H(X) \le \log_2 \hspace{0.05cm} |X|$.

  • Die untere Schranke  $H(X) = 0$  ergibt sich, wenn eine beliebige Wahrscheinlichkeit  $p_\mu = 1$  ist und alle anderen Null sind.
  • Die obere Schranke soll hier wie in der Vorlesung „Information Theory” von  Gerhard Kramer  an der TU München hergeleitet werden:
Obere Abschätzung für den natürlichen Logarithmus
  • Durch Erweiterung obiger Gleichung um  $|X|$  in Zähler und Nenner erhält man unter Verwendung von  $\log_2 \hspace{0.05cm}x= \ln(x)/\ln(2)$:
$$H(X) = \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [{\rm ln} \hspace{0.1cm} \frac{1}{|X| \cdot P_X(X)} \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
  • Wie aus nebenstehender Grafik hervorgeht, gilt die Abschätzung  $\ln(x) \le x-1$  mit der Identität für  $x=1$.  Somit kann geschrieben werden:
$$H(X) \le \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [\frac{1}{|X| \cdot P_X(X)} -1 \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
  • In der  Aufgabe 3.2  wurde für den Fall  $p_\mu \ne 0$  für alle  $\mu$  der Erwartungswert  ${\rm E} \big [\log_2 \hspace{0.05cm} {1}/{P_X(X)} \big ] =|X|$  berechnet.  Damit verschwindet der erste Term und man erhält das bekannte Ergebnis:
$$H(X) \le {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$




Hinweise:

  • Die Gleichung der binären Entropiefunktion lautet:
$$H_{\rm bin}(p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$


Fragebogen

1

Welche Aussagen gelten für die rote Entropiefunktion  $H_{\rm R}(p)$?

$H_{\rm R}(p)$  ergibt sich zum Beispiel mit  $p_1 = p$,  $p_2 = 1- p$  und  $p_3 = 0$.
$H_{\rm R}(p)$  ist identisch mit der binären Entropiefunktion  $H_{\rm bin}(p)$.

2

Welche Eigenschaften weist die binäre Entropiefunktion  $H_{\rm bin}(p)$  auf?

$H_{\rm bin}(p)$  ist konkav hinsichtlich des Parameters  $p$.
Es gilt  $\text {Max } [H_{\rm bin}(p)] = 2$  bit.

3

Welche Aussagen gelten für die blaue Entropiefunktion  $H_{\rm B}(p)$?

$H_{\rm B}(p)$  ergibt sich beispielsweise mit  $p_1 = p$,  $p_2 = 1/2- p$  und  $p_3 = 1/2$.
Es gilt  $H_{\rm B}(p = 0)= 1$  bit.
Es gilt  $\text {Max } [H_{\rm B}(p)] = \log_2 \hspace{0.1cm} (3)$  bit.

4

Welche Aussagen gelten für die grüne Entropiefunktion  $H_{\rm G}(p)$?

$H_{\rm G}(p)$  ergibt sich beispielsweise mit  $p_1 = p$,  $p_2 = 2/3- p$  und  $p_3 = 1/3$.
Es gilt  $H_{\rm G}(p = 0)= 1$  bit.
Es gilt  $\text {Max } [H_{\rm G}(p)] = \log_2 \hspace{0.1cm} (3)$ bit.


Musterlösung

(1)  Beide Aussagen sind richtig:

  • Setzt man  $p_3 = 0$ und formal  $p_1 = p$   ⇒    $p_2 = 1- p$, so ergibt sich die binäre Entropiefunktion
$$H_{\rm bin}(p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$


(2)  Richtig ist allein der Lösungsvorschlag 1:

  • Man kann die binäre Entropiefunktion wegen  $\log(x) = \ln(x)/\ln(2)$  auch in die folgende Form bringen:
$$H_{\rm bin}(p) = \frac{-1}{{\rm ln}(2)} \cdot \big [ p \cdot {\rm ln}(p) + (1-p) \cdot {\rm ln}(1-p) \big ] \hspace{0.05cm}.$$
  • Die erste Ableitung führt zum Ergebnis
$$\frac {{\rm d}H_{\rm bin}(p)}{{\rm d}p} = \frac{-1}{{\rm ln}(2)} \cdot \big [ {\rm ln}(p) + p \cdot \frac{1}{p} - {\rm ln}(1-p) - (1-p) \cdot \frac{1}{1-p} \big ] = \frac{1}{{\rm ln}(2)} \cdot \big [ {\rm ln}(1-p) - {\rm ln}(p) \big ] = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{p} \hspace{0.05cm}.$$
  • Durch Nullsetzen dieser Ableitung erhält man den Abszissenwert  $p = 0.5$, der zum Maximum der Entropiefunktion führt:   $H_{\rm bin}(p =0.5) = 1$ bit
    ⇒   der Lösungsvorschlag 2 ist falsch.
  • Durch nochmaliges Differenzieren erhält man für die zweite Ableitung:
$$\frac {{\rm d}^2H_{\rm bin}(p)}{{\rm d}p^2} = \frac{1}{{\rm ln}(2)} \cdot \left [ \frac{-1}{1-p} - \frac{1}{p} \right ] = \frac{-1}{{\rm ln}(2) \cdot p \cdot (1-p)} \hspace{0.05cm}.$$
  • Diese Funktion ist im gesamten Definitionsgebiet  $0 ≤ p ≤ 1$  negativ   ⇒   $H_{\rm bin}(p)$ ist konkav   ⇒   der Lösungsvorschlag 1 ist richtig.


Drei Entropiefunktionen mit  $M = 3$

(3)  Richtig sind hier die Aussagen 1 und 2:

  • Für  $p = 0$  erhält man die Wahrscheinlichkeitsfunktion  $P_X(X) = \big [\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.15cm} 1/2\hspace{0.05cm},\hspace{0.15cm} 1/2 \hspace{0.05cm} \big ]$   ⇒   $H(X) = 1$  bit.
  • Das Maximum unter der Voraussetzung  $p_3 = 1/2$  ergibt sich für  $p_1 = p_2 = 1/4$:
$$P_X(X) = \big [\hspace{0.05cm}1/4\hspace{0.05cm}, \hspace{0.05cm} 1/4\hspace{0.05cm},\hspace{0.05cm} 1/2 \hspace{0.05cm} \big ] \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Max} \ [H_{\rm B}(p)] = 1.5 \ \rm bit \hspace{0.05cm}.$$
  • In kompakter Form lässt sich  $H_{\rm B}(p)$  mit der Einschränkung  $0 ≤ p ≤ 1/2$  wie folgt darstellen:
$$H_{\rm B}(p) = 1.0\,{\rm bit} + {1}/{2} \cdot H_{\rm bin}(2p) \hspace{0.05cm}.$$


(4)  Richtig sind hier die erste und letzte Aussage:

  • Der grüne Kurvenzug beinhaltet mit  $p = 1/3$  auch die Gleichverteilung aller Wahrscheinlichkeiten
$$ {\rm Max} \ [H_{\rm G}(p)] = \log_2 (3)\ \text{bit}.$$
  • Allgemein lässt sich der gesamte Kurvenverlauf im Bereich  $0 ≤ p ≤ 2/3$  wie folgt ausdrücken:
$$H_{\rm G}(p) = H_{\rm G}(p= 0) + {2}/{3} \cdot H_{\rm bin}(3p/2) \hspace{0.05cm}.$$
  • Aus der Grafik auf der Angabenseite erkennt man auch, dass folgende Bedingung erfüllt sein muss:
$$H_{\rm G}(p = 0) + {2}/{3}= {\rm log}_2 \hspace{0.01cm} (3) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_{\rm G}(p= 0) = 1.585 - 0.667 = 0.918 \,{\rm bit} \hspace{0.05cm}.$$
  • Der zweite Lösungsvorschlag ist somit falsch.  Zum gleichen Ergebnis gelangt man über die Gleichung
$$H_{\rm G}(p = 0) = {1}/{3} \cdot {\rm log}_2 \hspace{0.01cm} (3) +{2}/{3} \cdot {\rm log}_2 \hspace{0.01cm} (3/2) = {\rm log}_2 \hspace{0.01cm} (3) -2/3 \cdot {\rm log}_2 \hspace{0.01cm} (2) \hspace{0.05cm}.$$