---

Aufgabe 1: Kapazität des Skalarproduktes

Wie in der Übung besprochen schauen wir uns die Aufgabe zur Bestimmung der Kapazität des Skalarproduktes in dieser LE an.

Augabe 2: Codes & Entropie

Teil a: Verbesserung des Huffman-Codes

In der Vorlesung wurden Huffman-Codes vorgestellt. Diese sind so konstruiert, dass sie die Ereignisse \(x_1, \dots, x_n\) einer Zufallsvariable \(X\) so kodieren, dass die Länge des Codes \(C(x_i)\) gerade der Information des Ereignisses \(x_i\) entspricht, \[ C(x_i) = I(p_{x_i}) = -\log(p_{x_i}) \]

Wir haben in der Vorlesung gesehen, dass Huffman-Codes im Mittel maximal ein Bit verschwenden. \[ H(X) ≤ E_X[C(X)] < H(X) + 1 \tag{1}\]

Die Herleitung dazu ist recht einfach:

---

Wenn die Länge des Codes gerade der Information des Ereignisses entspricht, dann können wir die tatsächliche Länge \(C(x)\) durch die nächste ganze Zahl abschätzen (die Länge ist stets eine ganze Zahl). \[ I(x) ≤ C(x) = \left\lceil I(x)\right\rceil < I(x) + 1 \] Im Mittel ergibt sich damit: \[ E_X[I(X)]) ≤ E_X[C(X)] < E_X[I(X)] + 1\\ H(X) ≤ E_X[C(X)] < H(X) + 1 \]

Ist es möglich Codes zu erstellen, die sich um weniger als 1 Bit im Mittel verschätzen?

Wir nehmen an, dass wir eine Zufallsvariable \(Z\) beobachten, die lediglich ein \(n\)-dimensionaler Vektor ist, der aus unabhängigen gleichverteilten Zufallsvariablen \(X_i\) besteht, \[ Z = (X_1, \dots, X_n) \]

1. Leiten Sie zuerst her, dass \(H(Z) = n\cdot H(X)\) gilt.
2. Setzen Sie nun \(H(Z)\) anstelle von \(H(X)\) in die obige Ungleichung \((1)\) ein und folgern Sie, dass für \(n\rightarrow \infty\) der Huffman-Code von \(n\) Beobachtungen beliebig genau die Information der Eingabe codiert.

Teil b: maximale Entropie

Minimale Entropie zu erreichen ist recht einfach; wir wählen für ein Ereignis die Wahrscheinlichkeit 1, für alle anderen Ereignisse die Wsk. 0. Die Information einer solchen Zufallsvariable ist gerade 0. (Dies verdeutlicht, warum die Information häufig auch Überraschung genannt wird).

Gegeben sei eine beliebige Zufallsvariable \(X\), die die Werte \(x_1,\dots,x_n\) mit unbekannten Wahrscheinlichkeiten \(p_1,\dots,\p_n\) annehmen kann. Wir möchten nun herleiten, wann die Entropie maximal wird.

1. Beweisen Sie die Jensen-Ungleichung:
   Gegeben sei eine konvexe Funktion \(f\) und eine Zufallsvariable \(X\).
   Dann gilt \[E[f(X)] ≥ f(E[X]).\] (Die Gleichheit gilt genau dann, wenn \(f\) linear ist, oder \(H(X) = 0\).)
   
   Hinweis: Eine Funtkion \(f:\mathbb{R} \rightarrow \mathbb{R}\) ist genau dann konvex, wenn sich alle Funktionswerte über allen linearen Funktionen befinden, die die Funktion schneiden, also \[f(x) ≥ a\cdot x + b \qquad\forall x\].
2. Nutzen Sie nun die Jensen-Ungleichung, um die maximale Entropie der Zufallsvariable \(X\) zu bestimmen.
   Hinweis: Beginnen Sie mit der Definition der Entropie und nutzen Sie, dass \(f = -\log\) eine konvexe Funktion ist.

Teil c: Kettenregel

1. Beweisen Sie die Kettenregel: \[H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X)\].
2. Beweisen Sie die Kettenregel für drei Mengen: \[H(X,Y,Y) = H(X) + H(Y|X) + H(Z|X,Y)\].