---

Aufgabe: Kapazität des Skalarproduktes

Vervollständigen Sie Ihre Lösung zum letzten Übungsblatt.

Augabe: 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.

Augabe: Korrelation und Mutual Information

Die Kovarianz zweier Zufallsvariablen \(X\) und \(Y\) ist als \[ Cov[X,Y] = \mathbb{E}\left[\left(X- \mathbb{E}[X]\right)\left(Y- \mathbb{E}[Y]\right)\right] \] definiert und die Korrelation zweier Zufallsvariablen \(X\) und \(Y\) ist durch \[ \rho_{XY} = \frac{Cov[X,Y]}{\sqrt{Var[X]Var[Y]}} \] gegeben. (Der Nenner normalisiert den Wert lediglich auf das Intervall \([-1,1]\).

1. Zeigen Sie, dass zwei unabhängige Zufallsvariablen eine Korrelation von Null haben, \(Cov[X,Y] = 0\).
2. Zeigen Sie mithilfe eines Gegenbeispiels, dass eine Korrelation von 0 keine Unabhängigkeit impliziert (Im Gegensatz zur Mutual Information).
   Hinweis: Wählen Sie eine (einfache) nicht-lineare Abbildung \(f(X)\).
3. Tatsächlich ist die Korrelation lediglich in der Lage lineare Zusammenhänge zu messen. Wir zeigen dies nun auf folgende Art und Weise: Für die zwei Zufallsvariablen \(X\) und \(Y\) suchen wir eine lineare Funktion \(f(x) = ax + b\), die die Relation dieser zwei Variablen so gut wie möglich beschreibt. Um die Parameter dieser zu finden formulieren wir (was sonst) ein Least Squares Problem: \[ L(a,b) = \frac{1}{2} \mathbb{E}_{X,Y}\left[ (f(X) - Y)^2 \right]. \] Bestimmen Sie \(a\) und \(b\) so, dass \(L(a,b)\) minimal wird.
   
   Schließen Sie, dass die Korrelation zweier Zufallsvariablen lediglich lineare Zusammenhänge abbildet.