Difference between revisions of "Aufgaben:Exercise 1.2: Entropy of Ternary Sources"

From LNTwww
Line 70: Line 70:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>2.</b>&nbsp;&nbsp;Mit den Auftrittswahrscheinlichkeiten 1/2, 1/3 und 1/6 erhält man folgenden Entropiewert:
+
'''(1)'''&nbsp; Mit den Auftrittswahrscheinlichkeiten $1/2$, $1/3$ und $1/6$ erhält man folgenden Entropiewert:
:$$H \hspace{0.1cm}  =  \hspace{0.1cm}  1/2 \cdot {\rm log}_2\hspace{0.1cm}(2) +1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) +1/6 \cdot {\rm log}_2\hspace{0.1cm}(6) =\\
+
:$$H \hspace{0.1cm}  =  \hspace{0.1cm}  1/2 \cdot {\rm log}_2\hspace{0.1cm}(2) +1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) +1/6 \cdot {\rm log}_2\hspace{0.1cm}(6) =(1/2 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(2) +  (1/3 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(3) \hspace{0.15cm}\underline {\approx 1.46 \, {\rm bit}} \hspace{0.05cm}.$$
  \hspace{0.1cm}  =  \hspace{0.1cm}  (1/2 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(2) +  (1/3 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(3) =\\
 
  \hspace{0.1cm}  =  \hspace{0.1cm}  2/3 \cdot 1\,{\rm bit} + 1/2 \cdot 1.585\,{\rm bit}\hspace{0.15cm}\underline {\approx 1.46 \, {\rm bit}}
 
  \hspace{0.05cm}.$$
 
  
:<b>2.</b>&nbsp;&nbsp;Richtig ist <u>Lösungsvorschlag 2</u>. Die Entropie hängt nur von den Auftrittswahrscheinlichkeiten ab. Es ist dabei egal, welche Zahlenwerte oder physikalische Größen man den einzelnen Symbolen zuordnet. Anders ist es bei Mittelwerten oder der AKF&ndash;Berechnung. Werden nur Symbole angegeben, so kann man hierfür keine Momente angeben. Außerdem hängen die Mittelwerte, Autokorrelation, usw. davon ab, ob man die Zuordnung bipolar (&ndash;1, 0, +1) oder unipolar (zum Beispiel: 0, 1, 2) vereinbart.
+
'''(2)'''&nbsp; Richtig ist <u>Lösungsvorschlag 2</u>:
 +
* Die Entropie hängt nur von den Auftrittswahrscheinlichkeiten ab. Es ist dabei egal, welche Zahlenwerte oder physikalische Größen man den einzelnen Symbolen zuordnet.  
 +
*Anders ist es bei Mittelwerten oder der AKF&ndash;Berechnung. Werden nur Symbole angegeben, so kann man hierfür keine Momente angeben. *Außerdem hängen die Mittelwerte, Autokorrelation, usw. davon ab, ob man die Zuordnung bipolar $(-1, \hspace{0.05cm}0, \hspace{0.05cm}+1)$ oder unipolar (zum Beispiel: $(0, \hspace{0.05cm}1, \hspace{0.05cm}2)$ vereinbart.
  
:<b>3.</b>&nbsp;&nbsp;Die Entropie der Quelle Q<sub>2</sub> lässt sich wie folgt ausdrücken:
 
:$$H \hspace{0.1cm} =  \hspace{0.1cm} p \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p}+ 2 \cdot \frac{1-p}{2}  \cdot {\rm log}_2\hspace{0.1cm}\frac {2}{1-p}=\\
 
\hspace{0.1cm}  =  \hspace{0.1cm} p \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p}+ (1-p)  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{1-p} + (1-p)\cdot {\rm log}_2\hspace{0.1cm}(2)= H_{\rm bin}(p) + 1-p \hspace{0.05cm}.$$
 
:Für <i>p</i> = 0.5 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <i>H</i><sub>bin</sub>(<i>p</i>) = 1 ergibt sich <i>H</i> <u>= 1.5 bit</u>.
 
  
:<b>4.</b>&nbsp;&nbsp;Die maximale Entropie einer gedächtnislosen Quelle mit dem Symbolumfang <i>M</i> ergibt sich, wenn alle <i>M</i> Symbole gleichwahrscheinlich sind. Für den Sonderfall <i>M</i> = 3 folgt daraus:
+
'''(3)'''&nbsp; Die Entropie der Quelle $\rm Q_2$ lässt sich wie folgt ausdrücken:
 +
:$$H \hspace{0.1cm} =  \hspace{0.1cm} p \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p}+ 2 \cdot \frac{1-p}{2}  \cdot {\rm log}_2\hspace{0.1cm}\frac {2}{1-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} + (1-p)\cdot {\rm log}_2\hspace{0.1cm}(2)= H_{\rm bin}(p) + 1-p \hspace{0.05cm}.$$
 +
Für $p = 0.5$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $H_{\rm bin}(p) = 1$ ergibt sich $\underline{H = 1.5\hspace{0.05cm}\rm  bit}$.
 +
 
 +
 
 +
'''(4)'''&nbsp; Die maximale Entropie einer gedächtnislosen Quelle mit dem Symbolumfang $M$ ergibt sich, wenn alle $M$ Symbole gleichwahrscheinlich sind. Für den Sonderfall $M=3$ folgt daraus:
 
:$$p_{\rm R} + p_{\rm G} + p_{\rm S} = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
:$$p_{\rm R} + p_{\rm G} + p_{\rm S} = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
  \underline {p = 1/3}\hspace{0.05cm}.$$
+
  \underline {p = 1/3 = 0.333}\hspace{0.05cm}.$$
:Damit erhält man mit dem Ergebnis der Teilaufgabe (3) die folgende Entropie:
+
Damit erhält man mit dem Ergebnis der Teilaufgabe (3) die folgende Entropie:
:$$H \hspace{0.1cm} = \hspace{0.1cm} H_{\rm bin}(1/3) + 1-1/3 = 1/3 \cdot  
+
:$$H = H_{\rm bin}(1/3) + 1-1/3 = 1/3 \cdot  
{\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot {\rm log}_2\hspace{0.1cm}(3/2) + 2/3 =\\
+
{\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot {\rm log}_2\hspace{0.1cm}(3/2) + 2/3 $$
\hspace{0.1cm} = \hspace{0.1cm}  1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot  
+
:$$\Rightarrow \hspace{0.3cm}H = 1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot  
 
{\rm log}_2\hspace{0.1cm}(3) - 2/3 \cdot {\rm log}_2\hspace{0.1cm}(2)+ 2/3 =  
 
{\rm log}_2\hspace{0.1cm}(3) - 2/3 \cdot {\rm log}_2\hspace{0.1cm}(2)+ 2/3 =  
 
{\rm log}_2\hspace{0.1cm}(3) = {1.585 \, {\rm bit}}
 
{\rm log}_2\hspace{0.1cm}(3) = {1.585 \, {\rm bit}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>5.</b>&nbsp;&nbsp;&bdquo;Roulette 1&rdquo; ist informationstheoretisch gleich der Konfiguration Q<sub>2</sub> mit <i>p</i> = 1/37:
+
'''(5)'''&nbsp; Roulette 1&rdquo; ist informationstheoretisch gleich der Konfiguration Q<sub>2</sub> mit <i>p</i> = 1/37:
 
:$$p_{\rm G} = p =  \frac{1}{37}\hspace{0.05cm},\hspace{0.2cm} p_{\rm R} = p_{\rm S} = \frac{1-p}{2} = \frac{18}{37} \hspace{0.05cm}.$$
 
:$$p_{\rm G} = p =  \frac{1}{37}\hspace{0.05cm},\hspace{0.2cm} p_{\rm R} = p_{\rm S} = \frac{1-p}{2} = \frac{18}{37} \hspace{0.05cm}.$$
 
:Damit erhält man mit dem Ergebnis der Teilaufgabe (3):
 
:Damit erhält man mit dem Ergebnis der Teilaufgabe (3):
Line 101: Line 101:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>6.</b>&nbsp;&nbsp; Setzt man bei Roulette auf einzelne Zahlen &#8658; Konfiguration &bdquo;Roulette 2&rdquo;, so sind alle Zahlen von <b>0</b> bis <b>36</b> gleichwahrscheinlich und man erhält:
+
'''(6)'''&nbsp; Setzt man bei Roulette auf einzelne Zahlen &#8658; Konfiguration &bdquo;Roulette 2&rdquo;, so sind alle Zahlen von <b>0</b> bis <b>36</b> gleichwahrscheinlich und man erhält:
 
:$$H = {\rm log}_2\hspace{0.1cm}(37)  \hspace{0.15cm} \underline { = 5.209 \, {\rm bit}}
 
:$$H = {\rm log}_2\hspace{0.1cm}(37)  \hspace{0.15cm} \underline { = 5.209 \, {\rm bit}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$

Revision as of 17:11, 25 April 2017

Wahrscheinlichkeiten zweier Ternärquellen

Die Entropie einer wertdiskreten gedächtnislosen Nachrichtenquelle mit $M$ möglichen Symbolen lautet:

$$H = \sum_{\mu = 1}^M p_{\mu} \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{p_\mu}\hspace{0.05cm},\hspace{0.3cm} {\rm Pseudoeinheit\hspace{-0.15cm}: \hspace{0.15cm}bit}\hspace{0.05cm}.$$

Hierbei bezeichnen die $p_\mu$ die Auftrittswahrscheinlichkeiten der einzelnen Symbole bzw. Ereignisse. Im vorliegenden Beispiel werden die Ereignisse mit R(ot), G(rün) und S(chwarz) bezeichnet.

  • Bei einer binären Quelle mit den Auftrittswahrscheinlichkeiten $p$ und $1-p$ kann hierfür geschrieben werden:
$$H = 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},\hspace{0.3cm} {\rm Pseudoeinheit\hspace{-0.15cm}: \hspace{0.15cm}bit}\hspace{0.05cm}.$$
  • Die Entropie einer mehrstufigen Quelle lässt sich häufig mit dieser „binären Entropiefunktion” $H_{\rm bin}(p)$ ausdrücken.

Betrachtet werden in dieser Aufgabe zwei Ternärquellen mit den Symbolwahrscheinlichkeiten gemäß der obigen Grafik:

  • die Quelle $\rm Q_1$ mit $p_{\rm G }= 1/2$, $p_{\rm S }= 1/3$ und $p_{\rm R }= 1/6$,
  • die Quelle $\rm Q_2$ mit $p_{\rm G }= p$ sowie $p_{\rm S } = p_{\rm R } = (1-p)/2$.


Die Ternärquelle $\rm Q_2$ lässt sich auch auf das Roulette anwenden, wenn ein Spieler nur auf die Felder Rot, Schwarz und Grün (die „Null”) setzt. Dieser Spieltyp wird im Fragebogen mit „Roulette 1” bezeichnet.

Dagegen weist „Roulette 2” darauf hin, dass der Spieler auf einzelne Zahlen (0, ... , 36) setzt.

Hinweise:


Fragebogen

1

Welche Entropie $H$ besitzt die Quelle $\rm Q_1$?

$\rm Q_1$:      $H \ = $

$\ \rm bit$

2

Welche der folgenden Aussagen sind zutreffend, wenn man R, G und S durch die Zahlenwerte $-1$, $0$ und $+1$ darstellt?

Es ergibt sich eine kleinere Entropie.
Die Entropie bleibt gleich.
Es ergibt sich eine größere Entropie.

3

Bestimmen Sie die Entropie der Quelle $\rm Q_2$ unter Verwendung der binären Entropiefunktion $H_{\rm bin}(p)$. Welcher Wert ergibt sich für $p = 0.5$?

${\rm Q_2}, \ p = 0.5$:     $H \ = $

$\ \rm bit$

4

Für welchen $p$–Wert ergibt sich die maximale Entropie der Quelle $\rm Q_2$?

${\rm Q_2},\ H → H_\text{max}$:     $p \ = $

5

Welche Entropie hat die Nachrichtenquelle „Roulette” hinsichtlich der Ereignisse Rot, Schwarz und Grün (die „Null”)?

$\text{Roulette 1}$:     $H \ = $

$\ \rm bit$

6

Welche Entropie weist „Roulette” hinsichtlich der Zahlen $0$, ... , $36$ auf?

$\text{Roulette 2}$:     $H \ = $

$\ \rm bit$


Musterlösung

(1)  Mit den Auftrittswahrscheinlichkeiten $1/2$, $1/3$ und $1/6$ erhält man folgenden Entropiewert:

$$H \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot {\rm log}_2\hspace{0.1cm}(2) +1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) +1/6 \cdot {\rm log}_2\hspace{0.1cm}(6) =(1/2 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(2) + (1/3 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(3) \hspace{0.15cm}\underline {\approx 1.46 \, {\rm bit}} \hspace{0.05cm}.$$

(2)  Richtig ist Lösungsvorschlag 2:

  • Die Entropie hängt nur von den Auftrittswahrscheinlichkeiten ab. Es ist dabei egal, welche Zahlenwerte oder physikalische Größen man den einzelnen Symbolen zuordnet.
  • Anders ist es bei Mittelwerten oder der AKF–Berechnung. Werden nur Symbole angegeben, so kann man hierfür keine Momente angeben. *Außerdem hängen die Mittelwerte, Autokorrelation, usw. davon ab, ob man die Zuordnung bipolar $(-1, \hspace{0.05cm}0, \hspace{0.05cm}+1)$ oder unipolar (zum Beispiel: $(0, \hspace{0.05cm}1, \hspace{0.05cm}2)$ vereinbart.


(3)  Die Entropie der Quelle $\rm Q_2$ lässt sich wie folgt ausdrücken:

$$H \hspace{0.1cm} = \hspace{0.1cm} p \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p}+ 2 \cdot \frac{1-p}{2} \cdot {\rm log}_2\hspace{0.1cm}\frac {2}{1-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} + (1-p)\cdot {\rm log}_2\hspace{0.1cm}(2)= H_{\rm bin}(p) + 1-p \hspace{0.05cm}.$$

Für $p = 0.5$   ⇒   $H_{\rm bin}(p) = 1$ ergibt sich $\underline{H = 1.5\hspace{0.05cm}\rm bit}$.


(4)  Die maximale Entropie einer gedächtnislosen Quelle mit dem Symbolumfang $M$ ergibt sich, wenn alle $M$ Symbole gleichwahrscheinlich sind. Für den Sonderfall $M=3$ folgt daraus:

$$p_{\rm R} + p_{\rm G} + p_{\rm S} = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline {p = 1/3 = 0.333}\hspace{0.05cm}.$$

Damit erhält man mit dem Ergebnis der Teilaufgabe (3) die folgende Entropie:

$$H = H_{\rm bin}(1/3) + 1-1/3 = 1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot {\rm log}_2\hspace{0.1cm}(3/2) + 2/3 $$
$$\Rightarrow \hspace{0.3cm}H = 1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot {\rm log}_2\hspace{0.1cm}(3) - 2/3 \cdot {\rm log}_2\hspace{0.1cm}(2)+ 2/3 = {\rm log}_2\hspace{0.1cm}(3) = {1.585 \, {\rm bit}} \hspace{0.05cm}.$$

(5)  Roulette 1” ist informationstheoretisch gleich der Konfiguration Q2 mit p = 1/37:

$$p_{\rm G} = p = \frac{1}{37}\hspace{0.05cm},\hspace{0.2cm} p_{\rm R} = p_{\rm S} = \frac{1-p}{2} = \frac{18}{37} \hspace{0.05cm}.$$
Damit erhält man mit dem Ergebnis der Teilaufgabe (3):
$$H \hspace{0.1cm} = \hspace{0.1cm} H_{\rm bin}(1/37) + \frac{36}{37} = \frac{1}{37} \cdot {\rm log}_2\hspace{0.1cm}(37) + \frac{36}{37} \cdot {\rm log}_2\hspace{0.1cm}(37) - \frac{36}{37} \cdot {\rm log}_2\hspace{0.1cm}36 + \frac{36}{37} =\\ \hspace{0.1cm} = \hspace{0.1cm} {\rm log}_2\hspace{0.1cm}(37) + \frac{36}{37} \cdot ( 1- {\rm log}_2\hspace{0.1cm}(36)) = 5.209 - 4.057 \hspace{0.15cm} \underline { = 1.152 \, {\rm bit}} \hspace{0.05cm}.$$

(6)  Setzt man bei Roulette auf einzelne Zahlen ⇒ Konfiguration „Roulette 2”, so sind alle Zahlen von 0 bis 36 gleichwahrscheinlich und man erhält:

$$H = {\rm log}_2\hspace{0.1cm}(37) \hspace{0.15cm} \underline { = 5.209 \, {\rm bit}} \hspace{0.05cm}.$$