Effiziente Algorithmen, Kapitel 1.4

1.4 Shannon-Entropie

Im Folgenden werden wir die Shannon-Entropie kennenlernen - ein Maß für die Unvorhersagbarkeit einer Wahrscheinlichkeitsverteilung.

Definition 1.4.1 Sei $X$ eine endliche oder abzählbar unendliche Menge und $P : X \to [0, 1]$ eine Wahrscheinlichkeitsverteilung. Die Entropie von $P$ ist

\begin{array}{r} H (P) := \sum_{x \in X} P (x) \log (\frac{1}{P (x)}) . \end{array}

Für die Definition nehmen wir an, dass $P (x) > 0$ gilt für alle $x \in X$ . Falls nicht, so könnten wir uns einfach auf den Träger $supp (P)$ (enligsch Support) konzentrieren: die Menge $X^{'} := {x \in X | P (x) > 0}$ . Oder einfach bemerken, dass die Funktion $p \mapsto p \log (\frac{1}{p})$ für $p \to 0$ gegen $0$ konvergiert und sie somit bei $p = 0$ stetig fortzusetzen.

Beispiel 1: die Gleichverteilung. Wenn $X = {1, \dots, n}$ ist und $P$ die Gleichverteilung darauf, gilt also $P (x) = 1 / n$ für jedes $x \in X$ und $H (P) = \sum_{i = 1}^{n} \frac{1}{n} \log_{2} (n) = \log_{2} (n)$ .

Beispiel 2: Münzwürfe. Wir werfen eine faire Münze, bis Kopf erscheint. Sei $X$ die Anzahl der benötigten Würfe.

\begin{array}{r} Pr [X = k] = 2^{- k} . \end{array}

Dies definiert also eine Wahrscheinlichkeitsverteilung über $N^{+}$ mit $P (k) = 2^{- k}$ . Es gilt

\begin{array}{r} H (P) = \sum_{k = 1}^{\infty} k \cdot 2^{- k} . \end{array}

Dies ist zufälligerweise auch $E [X]$ , die erwartete Anzahl der benötigten Münzwürfe. Wir können die Summe wie folgt evaluieren:

\begin{aligned} H (P) & = \sum_{k = 1}^{\infty} k \cdot 2^{- k} \\ = \frac{1}{2} \cdot \sum_{k = 1}^{\infty} k \cdot 2^{- (k - 1)} \\ (via l := k - 1) & = \frac{1}{2} \cdot \sum_{l = 0}^{\infty} (l + 1) \cdot 2^{- l} \\ = \frac{1}{2} \cdot \sum_{l = 0}^{\infty} l 2^{- l} + \frac{1}{2} \cdot \sum_{l = 0}^{\infty} 2^{- l} \\ = \frac{1}{2} H (P) + \frac{1}{2} \cdot 2, \end{aligned}

wobei die letzte Gleichheit folgt, weil die erste Summe das Gleiche ist wie $H (P)$ , nur mit Laufindex $l$ statt $k$ (beachten Sie, dass der Term für $l = 0$ verschwindet) und weil die zweite Summe eine geometrische Reihe ist, deren Wert wir kennen. Wir haben also $H (P) = \frac{1}{2} H (P) + 1$ erhalten und können dies zu $H (P) = 2$ auflösen.

Das zweite Beispiel ist insofern interessant, als es eine Zufallsvariable behandelt, die natürliche Zahlen annimmt und bei Erwartungswert und Entropie gleich sind. Dies ist im Allgemeinen nicht der Fall (im ersten Beispiel ist $E [X] = \frac{n + 1}{2})$ und $H (X) = \log n$ . Die Frage, wie groß die Entropie werden kann bei gegebenem Erwartungswert wird uns später noch beschäftigen.

Theorem 1.4.2 Sei $X$ eine endliche Menge mit $n := | X |$ und $P$ eine Wahrscheinlichkeitsverteilung auf $X$ . Dann gilt $H (P) \leq \log n$ .

Beweis. Wir nehmen an, dass $P (x) > 0$ für alle $x \in X$ gilt; andernfalls ersetzen wir $X$ durch den Träger $X^{'} := supp$ und erhalten statt der oberen Schranke $\log | X |$ die noch bessere Schranke $\log | X^{'} |$ . Wir definieren eine Zufallsvariable $W : X \to R$ wie folgt:

\begin{array}{r} W (x) := \frac{1}{P (x)} . \end{array}

Die Entropie $H (P)$ können wir nun schreiben als

\begin{aligned} H (P) & = \sum_{x \in X} P (x) \log (\frac{1}{P (x)}) = \sum_{x \in X} P (x) \log (W (x)) \\ = \underset{x \sim P}{E} [\log W (x)] . \end{aligned}

Die Funktion $w \mapsto \log w$ ist konkav; wir können daher Jensens Ungleichung (Reference "theorem-jensen" not found. Go to put-all-in-one-page.html and read the instructions.) anwenden und erhalten

\begin{aligned} \underset{x \sim P}{E} [\log W (x)] & \leq \log (\underset{x \in P}{E} W (x)) . \end{aligned}

Wir müssen nun nur noch $E_{x \sim P} [W (x)]$ ausrechnen:

\begin{aligned} \underset{x \sim P}{E} [W (x)] & = \sum_{x \in X} P (x) W (x) = \sum_{x \in X} P (x) \frac{1}{P (x)} = \sum_{x \in X} 1 = | X | = n . \end{aligned}

Das Theorem ist somit bewiesen.

◻

Übungsaufgabe 1.4.1 Beweisen Sie die folgende, allgemeinere Eigenschaft der Entropie: wenn $P$ eine Wahrscheinlichkeitsverteilung auf $X$ ist und $Y \subseteq X$ eine endliche Teilmenge und wir eine neue Wahrscheinlichkeitsverteilung $Q$ auf $X$ definieren, indem wir alle Wahrscheinlichkeiten für $y \in Y$ durch ihren Durchschnitt ersetzen, also

\begin{array}{r} Q (x) := {\begin{cases} \frac{\sum_{y \in Y P (y)}}{| Y |} & für x \in Y \\ P (x) & für x \in X ∖ Y, \end{cases} \end{array}

dann gilt $H (P) \leq H (Q)$ . In Worten: glätten erhöht die Entropie.