Difference between revisions of "Aufgaben:Exercise 3.3: Entropy of Ternary Quantities"

From LNTwww
Line 1: Line 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen
+
{{quiz-Header|Buchseite=Informationstheorie/Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen
 
}}
 
}}
  

Revision as of 11:31, 1 December 2016

P ID2754 Inf A 3 3.png

Rechts sehen Sie die Entropiefunktionen HR(p), HB(p) und HG(p), wobei „R” für „Rot” steht, usw. Für alle Zufallsgrößen lautet die Wahrscheinlichkeitsfunktion:

$$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 p1 = p und p2 = 1 – p3 – 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 [{\rm log}_2 \hspace{0.1cm} {1}/{P_X(X)} \right ]\hspace{0.05cm},$$

und liegt stets im Bereich 0 ≤ H(X) ≤ log2 |X|. Die untere Schranke H(X) = 0 ergibt sich, wenn eine beliebige Wahrscheinlichkeit pμ = 1 ist und alle anderen 0 sind. Die obere Schranke soll hier wie in [Kra13] hergeleitet werden:

  • Durch Erweiterung obiger Gleichung um |X| in Zähler und Nenner erhält man unter Verwendung von log2(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 nachfolgender Grafik hervorgeht, gilt die Abschätzung ln(x) ≤ 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}.$$
P ID2755 Inf A 3 3 B neu.png
  • In Aufgabe A3.2 wurde für den Fall, dass pμ ≠ 0 für alle μ gilt, der Erwartungswert E[1/PX(X)] zu |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}.$$

Hinweis: Die Aufgabe gehört zu Kapitel 3.1. Es wird auf die binäre Entropiefunktion Bezug genommen:

$$H_[[:Template:\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 HR(p)?

HR(p) ergibt sich z.B. mit p3 = 0, p1 = p, p2 = 1 – p.
HR(p) ist identisch mit der binären Entropiefunktion Hbin(p).

2

Welche Eigenschaften weist die binäre Entropiefunktion auf?

Hbin(p) ist konkav hinsichtlich des Parameters p.
Es gilt Max[Hbin(p)] = 2 bit.

3

Welche Aussagen gelten für die blaue Entropiefunktion HB(p)?

HB(p) ergibt sich z.B. mit p3 = 1/2, p1 = p, p2 = 1/2 – p.
Es gilt HB(p = 0) = 1 bit.
Es gilt Max[HB(p)] = log2 (3) bit.

4

Welche Aussagen gelten für die grüne Entropiefunktion HG(p)?

HG(p) ergibt sich z.B. mit p3 = 1/3, p1 = p, p2 = 2/3 – p.
Es gilt HG(p = 0) = 1 bit.
Es gilt Max[HG(p)] = log2 (3) bit.


Musterlösung

1.  Beide Aussagen sind richtig. Setzt man p3 = 0 und formal p1 = p  ⇒  p2 = 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 log2(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 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 p = 0.5, der zum Maximum der Entropiefunktion führt: Hbin(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 dp^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  ⇒  Hbin(p) ist konkav  ⇒  Richtig ist dementsprechend (allein) der Lösungsvorschlag 1.

3.  Richtig sind hier die Aussagen 1 und 2:

  • Für p = 0 erhält man die Wahrscheinlichkeitsfunktion PX(X) = [0, 1/2, 1/2]  ⇒  H(X) = 1 bit.
  • Das Maximum unter der Voraussetzung p3 = 1/2 ergibt sich für p1 = p2 = 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}.$$
P ID2756 Inf A 3 3 ML.png

In kompakter Form lässt sich HB(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[HG(p)] = log2 (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 Lösungsvorschlag 2 ist hier 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}.$$

Die Grafik zeigt nochmals die Ausgangsgrafik, aber nun mit Bemaßungen.