Exercise 3.3: Entropy of Ternary Quantities

Rechts sehen Sie die Entropiefunktionen $H_{\rm R}(p)$, $H_{\rm B}(p)$ und $H_{\rm G}(p)$, wobei „R” für „Rot” steht, „B” für „Blau” und „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}.$$

Es gilt der Zusammenhang $p_1 = p$ und $p_2 = 1 - p_3- p$.

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}\}$$

mit dem Symbolumfang $|X| = M$ 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}.$$

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

$$H(X) = {\rm E} \left [\log_2 \hspace{0.05cm} {1}/{P_X(X)} \right ]\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 $0$ 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 Aufgabe 3.2 wurde für den Fall$p_\mu \ne 0$ für alle $\mu$ der Erwartungswert ${\rm E} [\log_2 \hspace{0.05cm} {1}/{P_X(X)}] =|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 Aufgabe gehört zum Kapitel Einige Vorbemerkungen zu den 2D-Zufallsgrößen.
Insbesondere wird Bezug genommen auf die Seite Wahrscheinlichkeitsfunktion undEntropie.
Ausgegangen wird hier von der gleichen Konstellation wie in Aufgabe 3.2.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
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

Musterlösung

Solution

(1) Beide Aussagen sind richtig. Setzt man p₃ = 0 und formal p₁ = p ⇒ p₂ = 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) 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 \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 d}H_{\rm bin}(p)}{{\rm d}p} = \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 ] = \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 p = 0.5, der zum Maximum der Entropiefunktion führt: H_bin(p = 0.5) = 1 bit ⇒ 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_bin(p) ist konkav ⇒ Richtig ist allein der Lösungsvorschlag 1.

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

Für p = 0 erhält man die Wahrscheinlichkeitsfunktion P_X(X) = [0, 1/2, 1/2] ⇒ H(X) = 1 bit.
Das Maximum unter der Voraussetzung p₃ = 1/2 ergibt sich für p₁ = p₂ = 1/4:

$$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}] \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_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 die erste und letzte Aussage:

Der grüne Kurvenzug beinhaltet mit p = 1/3 auch die Gleichverteilung aller Wahrscheinlichkeiten ⇒ Max[H_G(p)] = log₂ (3) 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 2 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}.$$

	$H_{\rm R}(p)$ ergibt sich z.B. 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)$.

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

	H_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 \ \rm bit.$
	Es gilt Es gilt $\text {Max} [H_{\rm B}(p)] = \log_2 \hspace{0.1cm} (3) \ \rm bit$.

	$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 \ \rm bit.$
	Es gilt $\text {Max} [H_{\rm G}(p)] = \log_2 \hspace{0.1cm} (3) \ \rm bit$.