Der Wahrscheinlichkeits-Simplex
Eine Wahrscheinlichkeitsverteilung über q Symbole ist ein Punkt im (q−1)-dimensionalen Simplex: die Menge aller Vektoren (p₁, ..., p_q) mit pᵢ ≥ 0 und Σ pᵢ = 1.
Für q = 2: Der Simplex ist ein Liniensegment [0,1], parametrisiert durch eine einzelne Wahrscheinlichkeit p. Für q = 3: Der Simplex ist ein gleichseitiges Dreieck in ℝ². Jede Ecke ist eine deterministische Verteilung (alle Wahrscheinlichkeit auf ein Symbol); der Mittelpunkt ist die Gleichverteilung.
Entropie H(p) ordnet jedem Punkt des Simplex eine reelle Zahl zu. Die Geometrie der Funktion bestimmt viele grundlegende Ergebnisse.
Konkavität
H ist konkav auf dem Simplex: für beliebige zwei Verteilungen p und q und beliebiges λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Eine Mischung zweier Verteilungen hat eine Entropie, die mindestens so groß ist wie der gewichtete Durchschnitt ihrer einzelnen Entropien. Intuition: Das Mischen zweier Quellen erhöht die Unsicherheit.
Konkavität überprüfen
Für binäre Entropie H(p) ist die Konkavität im Graphen sichtbar: die Kurve wölbt sich nach oben und unterschreitet niemals eine Sehne, die zwei beliebige Punkte verbindet.
Formaler Test für Konkavität: die zweite Ableitung H''(p) ≤ 0 überall.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H'(p) = −log₂(p) − 1/ln(2) + log₂(1−p) + 1/ln(2) = log₂((1−p)/p)
H''(p) = −1/(p ln(2)) − 1/((1−p) ln(2)) = −1/(p(1−p) ln(2)) < 0 for all p ∈ (0,1)
Die zweite Ableitung ist überall im Inneren streng negativ: H ist streng konkav.
Die kapazitätsreichende Verteilung
Kanalkapazität ist definiert als die maximale gegenseitige Information über alle Eingabeverteilungen p(x):
C = max_{p(x)} I(X; Y)
wobei I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Für den binärsymmetrischen Kanal mit Fehlerwahrscheinlichkeit Q: die kapazitätsreichende Eingabeverteilung ist die Gleichverteilung p(0) = p(1) = 0,5.
Warum: H(Y) wird durch die Gleichverteilung der Ausgabe maximiert. Mit einem BSC ergibt eine gleichmäßige Eingabe eine gleichmäßige Ausgabe. Jede andere Eingabeverteilung macht H(Y) kleiner und reduziert I(X;Y).
Geometrisch: Die gegenseitige Information I(X;Y) ist eine konkave Funktion der Eingabeverteilung p(x) auf dem Simplex. Das Maximum einer konkaven Funktion auf einer konvexen Menge wird an einem eindeutigen Punkt erreicht (die Mitte für einen symmetrischen Kanal).
KL-Divergenz
Die Kullback-Leibler-Divergenz (relative Entropie) von Verteilung q zu Verteilung p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 immer (Gibbs' Ungleichung). D(p || q) = 0 wenn und nur wenn p = q.
D ist keine echte Distanz: sie ist asymmetrisch (D(p||q) ≠ D(q||p) im Allgemeinen) und erfüllt nicht die Dreiecksungleichung. Aber sie funktioniert als Maß dafür, wie 'weit' p von q im Wahrscheinlichkeitsraum entfernt ist.
KL-Divergenz erscheint in der ganzen Informationstheorie:
- Gegenseitige Information: I(X;Y) = D(p(x,y) || p(x)p(y)). Die gegenseitige Information ist die KL-Divergenz zwischen der gemeinsamen Verteilung und dem Produkt der Randverteilungen — wie weit die gemeinsame Verteilung von Unabhängigkeit entfernt ist.
- Gibbs' Ungleichung: der Satz über verlustlose Codierung folgt direkt aus D(p || q) ≥ 0.
- Kanalkapazität: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
KL-Divergenz berechnen
Beispiel: p = (0,5, 0,5) gleichmäßig binär, q = (0,8, 0,2) verzerrt binär.
D(p || q) = 0,5 log₂(0,5/0,8) + 0,5 log₂(0,5/0,2)
= 0,5 log₂(0,625) + 0,5 log₂(2,5)
≈ 0,5 × (−0,678) + 0,5 × 1,322 ≈ −0,339 + 0,661 ≈ 0,322 bits
Kanalkapazität als geometrischer Abstand
Kanalkapazität hat eine geometrische Interpretation im Raum der Wahrscheinlichkeitsverteilungen.
Für einen Kanal p(y|x), definieren Sie die kapazitätsreichende Eingabeverteilung p*(x). Die Kapazität erfüllt:
C = D(p*(y) || r(y))
wobei p(y) = Σ p(x) p(y|x) die Ausgabeverteilung unter der optimalen Eingabe ist, und r(y) = argmin_r max_x D(p(y|x) || r(y)) die minimale-Information-Ausgabeverteilung ist — der Punkt im Ausgabe-Wahrscheinlichkeitsraum, der (in KL-Divergenz) am nächsten an allen bedingten Ausgabeverteilungen p(y|x) gleichzeitig liegt.
Dies ist die informationsgeometrische Ansicht: Kanalkapazität ist der Radius der kleinsten KL-Divergenz-Kugel im Ausgabe-Verteilungsraum, die alle bedingten Verteilungen p(y|x=0) und p(y|x=1) enthält.
Für den BSC: p(y|x=0) = (1−Q, Q) und p(y|x=1) = (Q, 1−Q). Durch Symmetrie, die minimale-Information-Ausgabe r(y) = (0,5, 0,5). Kapazität = D((1−Q, Q) || (0,5, 0,5)) = 1 − H(Q). Die Formel stellt das Standardergebnis aus der Geometrie wieder her.
Kapazität aus KL-Divergenz
Verifizieren Sie die geometrische Formel: C = D(p(y|x=0) || r(y)) für einen BSC mit Q = 0,1, r(y) = (0,5, 0,5).
p(y|x=0) = (0,9, 0,1) (sende 0, empfange 0 mit Wahrscheinlichkeit 0,9, empfange 1 mit Wahrscheinlichkeit 0,1).
D((0,9, 0,1) || (0,5, 0,5)) = 0,9 log₂(0,9/0,5) + 0,1 log₂(0,1/0,5)
= 0,9 log₂(1,8) + 0,1 log₂(0,2)
log₂(1,8) ≈ 0,848, log₂(0,2) ≈ −2,322
= 0,9×0,848 + 0,1×(−2,322) ≈ 0,763 − 0,232 ≈ 0,531 bits
Überprüfung: C = 1 − H(0,1) ≈ 1 − 0,469 = 0,531 bits ✓
Rate-Distortion & die Grenzen der Kompression
Rate-Distortion-Theorie erweitert Informationstheorie auf verlustbehaftete Kompression. Statt zu fragen 'was ist die minimale Anzahl von Bits zur exakten Darstellung einer Quelle?' fragt sie: 'gegeben Toleranz für etwas durchschnittliche Verzerrung D, was ist die minimale Rate R(D) Bits pro Symbol?'
Die Rate-Distortion-Funktion R(D) ist konvex und fallend in D: mehr Verzerrungstoleranz ermöglicht niedrigere Raten. Bei D = 0 (verlustlos): R(0) = H(Quelle). Wenn D zunimmt, R(D) → 0.
Geometrisch: R(D) zeichnet eine Kurve auf der (Rate, Verzerrung)-Ebene. Jedes erreichbare (R, D)-Paar liegt auf oder über dieser Kurve. Punkte unter der Kurve sind unmöglich — Sie können nicht unterhalb der fundamentalen Grenze bei irgendeiner Verzerrungsstufe komprimieren.
Das Rate-Distortion-Theorem (Shannon, 1959): Für jede R > R(D), existieren Codes, die die erwartete Verzerrung auf höchstens D erreichen. Für R < R(D): Kein Code erreicht die erwartete Verzerrung D. Die Kurve ist eine geometrische Grenze im (Rate, Verzerrung)-Raum.