Zur Wiederholdung: wir betrachten eine endliche Menge $\X$ und eine Codierung von $X$ über dem Alphabet $\{0,1\}$. Diese Codierung ist eine Funktion $C: \X \rightarrow \{0,1\}^*$, und sie heißt präfixfrei wenn für alle $x, y \in X$ mit $x \ne y$ gilt:
\begin{align*} C(x) \not \preceq C(y) \ . \end{align*}Das Codewort $C(x)$ darf also kein Präfix von $C(y)$ sein, und insbesondere muss $C(x) \ne C(y)$ gelten. Wenn $\X$ mit einer Wahrscheinlichkeitsverteilung $P: X \rightarrow [0,1]$ ausgestattet ist, dann können wir über die erwartete Codelänge sprechen:
\begin{align*} \E_{x \sim P} [|C(x)|] = \sum_{x \in X} P(x) |C(x)| \ . \end{align*}Theorem (Source-Coding-Theorem). Sei $\X$ eine endliche Menge und $P$ eine Wahrscheinlichkeitsverteilung über $X$.
- Untere Schranke: wenn $C: \X \rightarrow \{0,1\}^*$ ein präfixfreier Code ist, dann gilt \begin{align*} \E_{x \sim P} [|C(x)|] \geq H(P) \ . \end{align*}
- Obere Schranke: es gibt einen präfixfreien Code $C: \X \rightarrow \{0,1\}^*$ mit \begin{align} |C(x)| \leq \ceil{\log_2 \pfrac{1}{P(x)}} \label{ineq-individual} \end{align} für jedes $x \in \X$, und somit auch \begin{align*} \E_{x \sim P} [|C(x)|] \leq H(P) + 1 \ . \end{align*}
Beweis (untere Schranke). Sei $C: \X \rightarrow \{0,1\}^*$ ein Code. Wir definieren
\begin{align*} Q: \X & \rightarrow \R \\ x & \mapsto 2^{-|C(x)|} \end{align*}Nach Teil $1$ von (der Kraft-McMillan-Ungleichung) gilt $\sum_{x \in X} Q(x) \leq 1$. Wir rechnen nun
\begin{align*} \E_{x \sim P} [|C(x)|] & = \E_{x \sim P} [ - \log Q(x) ] \\ & = \E_{x \sim P} [ - \log P(x) - \log Q(x) + \log P(x)] \\ & = \E_{x \sim P} [- \log P(x)] + \E_{x \sim P} \left[\log\pfrac{P(x)}{Q(x)} \right]\\ & = H(P) + \E_{x \sim P} \left[\log\pfrac{P(x)}{Q(x)} \right] \ . \end{align*}Es bleibt zu zeigen, dass der zweite Term dieser Summe nicht negativ ist.
\begin{align*} \E_{x \sim P} \left[\log\pfrac{P(x)}{Q(x)} \right] & \geq 0 \quad \Longleftrightarrow\\ \E_{x \sim P} \left[\log\pfrac{Q(x)}{P(x)} \right] & \leq 0 \ . \end{align*}Wir rechnen nun weiter mit der linken Seite der letzten Ungleichung. Wenn wir die Zufallsvariable $X \sim P$ wählen - also $\Pr[X = x] = P(x)$ und $Y := \frac{Q(X)}{P(X)}$ setzen, dann ist $Y$ auch eine Zufallsvariable, die endlich viele Werte annimmt (höchstens so viele wie $X$ selbst, also maximal $|\X|$ viele). Darüberhinaus ist $Y$ auch immer definiert: $X$ nimmt ja nur jene Werte $x \in \X$ an, für die $P(x) \gt 0$ gilt. Und für jedes $x \in \X$ gilt ja auch $Q(x) \gt 0$. Somit ist $Y = \frac{Q(X)}{P(X)}$ definiert und größer als $0$, und so ist auch $\log Y$ auch definiert. Die linke Seite der obigen Ungleichung ist also
\begin{align*} \E_P\left[ \log_2 (Y) \right] \ . \end{align*}Nun ist $Y$ eine Zufallsvariable, die nur endlich viele Werte annimmt, und $\log_2$ ist eine konkave Funktion. Wir wenden Jensens Ungleichung an:
\begin{align*} \E_P\left[ \log_2 (Y) \right] \leq \log_2 \left(\E_P[Y] \right) \ . \end{align*}Was ist $\E_P[Y]$, der Erwartungswert von $Y$ über der Wahrscheinlichkeitsverteilung $P$?
\begin{align*} \E_P[Y] & = \sum_{x \in \X} P(x) Y(x) \\ & = \sum_{x \in \X} P(x) \frac{Q(X)}{P(X)} \\ & = \sum_{x \in \X} Q(x) \ . \end{align*}Diese Summe ist, nach der Kraft-McMillan-Ungleichung () höchstens $1$, und somit ist ihr Logarithmus höchstens $0$. \(\square\)
Anmerkung. Ganz allgemein gilt, mit der gleichen Rechnung wie gerade eben: wenn $P$ und $Q$ zwei Wahrscheinlichkeitsverteilungen über einer Menge $\X$ sind und $Q(x) \gt 0$ ist für alle $x$ mit $P(x) \gt 0$, dann ist
\begin{align} \E_{x \sim P} \left[\frac{P(x)}{Q(x)} \right] \label{expression-kullback-leibler} \end{align}definiert und nichtnegativ. Der Ausdruck (\ref{expression-kullback-leibler}) ist als Kullback-Leibler-Divergenz bekannt und wird auch mit ${\rm KL}(P||Q)$ abgekürzt. Im Lichte der obigen Rechnung hat ${\rm KL}(P||Q)$ folgende Interpretation (die mit einer Prise Salz zu nehmen ist): wenn wir davon ausgehen, dass die Elemente $X \sim \X$ der Verteilung $Q$ folgen und einen präfixfreien Code konstruieren, der für $Q$ optimal wäre, die wirklich Wahrscheinlichkeitsverteilung jedoch $P$ ist, dann ist ${\rm KL}(P||Q)$ der Preis, den wir für diese Fehleinschätzung bezahlen müssen: im Schnitt ist jedes Codewort um ${\rm KL}(P||Q)$ länger, als es in einer für $P$ optimalen Verteilung der Fall wäre.
Beweis (obere Schranke). Der Einfachheit halber sei $\X = \{x_1,\dots,x_n\}$ und $p_i := P(x_i)$. Wir setzen $l_i := \ceil{\log_2 p_i}$. Der Ausdruck $2^{-l_i}$ ist also $p_i$, abgerundet auf die nächstkleinere Zweierpotenz. So würden wir beispielsweise $1/7$ auf $1/8$ abrunden und $15/32$ auf $1/4$. Es gilt
\begin{align*} \sum_{i=1}^n 2^{-l_i} \leq \sum_{i=1}^n p_i = 1 \ . \end{align*}Wir können also den zweiten Teil von , der Kraft-McMillan-Ungleichung anwenden und erhalten einen präfixfreien Code $\{\c_1, \dots, \c_n\}$ mit $|\c_i| = l_i = \ceil{\log_2 p_i}$. Somit ist (\ref{ineq-individual}) gezeigt. Für die erwartete Codelänge gilt nun
\begin{align*} \E_{x \sim P}[ |C(x)|] & = \E_{x \sim P} \left[\ceil{\log_2 \pfrac{1}{P(x)}} \right] \\ & \lt \E_{x \sim P} \left[1 + \log_2 \pfrac{1}{P(x)} \right] \\ & = 1 + \E_{x \sim P} \left[\log_2 \pfrac{1}{P(x)} \right] \\ & = 1 + H(P) \ . \end{align*}Somit ist Teil 2 gezeigt.\(\square\)
Der definierte Code für $\X$ weißt individuelle Optimalität auf: es gilt $|C(x)| \leq 1 + \log_2 \pfrac{1}{P(x)}$ für jedes $x$. Diese individuelle Optimalität gilt aber im Allgemeinen nicht für das Ergebnis des Huffman-Algorithmus:
Übungsaufgabe Sei $p \in [0,1]$ und $n \in \N$. Definieren Sie eine Wahrscheinlichkeitsverteilung über $\{1,\dots,n\}$ mit $P(1) = p$, so dass $|C^*(1)|$ möglichst groß wird; der Code $C^*$ ist hier der vom Huffman-Algorithmus erzeugte optimale Code. Zeigen Sie, dass $|C^*(1)|$ deutlich größer werden kann als $\log_2 \pfrac{1}{P(1)}$.