De Waarschijnlijkheidssimplex
Een waarschijnlijkheidsverdeling over q symbolen is een punt in de (q−1)-dimensionale simplex: de verzameling van alle vectoren (p₁, ..., p_q) met pᵢ ≥ 0 en Σ pᵢ = 1.
Voor q = 2: de simplex is een lijnstuk [0,1], geparametriseerd door een enkele waarschijnlijkheid p. Voor q = 3: de simplex is een gelijkzijdige driehoek in ℝ². Elke hoek is een deterministische verdeling (alle waarschijnlijkheid op één symbool); het midden is de uniforme verdeling.
Entropie H(p) wijst een reëel getal toe aan elk punt van de simplex. De geometrie van de functie bepaalt veel fundamentele resultaten.
Concaviteit
H is concaaf op de simplex: voor alle twee verdelingen p en q en alle λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Een mengsel van twee verdelingen heeft entropie minstens zo groot als het gewogen gemiddelde van hun individuele entropieën. Intuïtie: twee bronnen mengen verhoogt onzekerheid.
Concaviteit Verifiëren
Voor binaire entropie H(p) is concaviteit zichtbaar in de grafiek: de curve buigt omhoog, valt nooit onder enig akkoord dat twee punten verbindt.
Formele test voor concaviteit: de tweede afgeleide H''(p) ≤ 0 overal.
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 voor alle p ∈ (0,1)
De tweede afgeleide is overal in het inwendige strikt negatief: H is strikt concaaf.
De Invoerverdeling die Capaciteit Bereikt
Kanaalcapaciteit wordt gedefinieerd als de maximale wederzijdse informatie over alle invoerverdelingen p(x):
C = max_{p(x)} I(X; Y)
waarbij I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Voor het binair symmetrisch kanaal met foutwahrschijnlijkheid Q: de invoerverdeling die capaciteit bereikt is de uniforme verdeling p(0) = p(1) = 0.5.
Waarom: H(Y) wordt gemaximaliseerd door de uniforme uitvoerverdeling. Met een BSC geeft een uniforme invoer een uniforme uitvoer. Elke andere invoerverdeling maakt H(Y) kleiner, waardoor I(X;Y) afneemt.
Meetkundig: de wederzijdse informatie I(X;Y) is een concave functie van de invoerverdeling p(x) op de simplex. Het maximum van een concave functie op een convexe verzameling wordt bereikt op een uniek punt (het midden, voor een symmetrisch kanaal).
KL-Divergentie
De Kullback-Leibler-divergentie (relatieve entropie) van verdeling q naar verdeling p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 altijd (Gibbs' ongelijkheid). D(p || q) = 0 als en slechts als p = q.
D is geen echte afstand: het is asymmetrisch (D(p||q) ≠ D(q||p) in het algemeen) en voldoet niet aan de driehoeksongelijkheid. Maar het werkt als een maatstaf voor hoe 'ver' p van q is in waarschijnlijkheidsruimte.
KL-divergentie verschijnt in de hele informatietheorie:
- Wederzijdse informatie: I(X;Y) = D(p(x,y) || p(x)p(y)). De wederzijdse informatie is de KL-divergentie tussen de gezamenlijke verdeling en het product van de marginaalverdelingen — hoe ver de gezamenlijke van onafhankelijkheid verwijderd is.
- Gibbs' ongelijkheid: de ruisloze coderingsstelling volgt rechtstreeks uit D(p || q) ≥ 0.
- Kanaalcapaciteit: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
KL-Divergentie Berekenen
Voorbeeld: p = (0.5, 0.5) uniforme binaire, q = (0.8, 0.2) voorgespannen binaire.
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
Kanaalcapaciteit als Meetkundige Afstand
Kanaalcapaciteit heeft een meetkundige interpretatie in de ruimte van waarschijnlijkheidsverdelingen.
Voor een kanaal p(y|x), definieer de invoerverdeling die capaciteit bereikt, p*(x). De capaciteit voldoet aan:
C = D(p*(y) || r(y))
waarbij p(y) = Σ p(x) p(y|x) de uitvoerverdeling onder de optimale invoer is, en r(y) = argmin_r max_x D(p(y|x) || r(y)) de minimale-informatie-uitvoerverdeling is — het punt in de uitvoerwaarschijnlijkheidsruimte dat het dichtst (in KL-divergentie) bij alle voorwaardelijke uitvoerverdelingen tegelijk ligt.
Dit is het informatie-meetkundige oogpunt: kanaalcapaciteit is de straal van de kleinste KL-divergentiebal in de ruimte van uitvoerverdelingen die alle voorwaardelijke verdelingen p(y|x=0) en p(y|x=1) bevat.
Voor de BSC: p(y|x=0) = (1−Q, Q) en p(y|x=1) = (Q, 1−Q). Door symmetrie, de minimale-informatie-uitvoer r(y) = (0.5, 0.5). Capaciteit = D((1−Q, Q) || (0.5, 0.5)) = 1 − H(Q). De formule herstelt het standaardresultaat uit de meetkunde.
Capaciteit uit KL-Divergentie
Verifieer de meetkundige formule: C = D(p(y|x=0) || r(y)) voor een BSC met Q = 0.1, r(y) = (0.5, 0.5).
p(y|x=0) = (0.9, 0.1) (stuur 0, ontvang 0 met kans 0.9, ontvang 1 met kans 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
Controle: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 bits ✓
Rate-Distortion & de Limieten van Compressie
Rate-distortiontheorie breidt informatietheorie uit tot compressie met verlies. In plaats van te vragen 'wat is het minimum aantal bits om een bron exact weer te geven?' vraagt het: 'gegeven tolerantie voor enige gemiddelde vervorming D, wat is de minimale snelheid R(D) bits per symbool?'
De rate-distortionfunctie R(D) is convex en afnemend in D: meer vervormingstolerantie stelt lagere snelheden in staat. Bij D = 0 (verliesvrij): R(0) = H(bron). Naarmate D toeneemt, R(D) → 0.
Meetkundig: R(D) traceert een curve op het (snelheid, vervorming)-vlak. Elk bereikbaar (R, D)-paar ligt op of boven deze curve. Punten onder de curve zijn onmogelijk — je kunt niet onder de fundamentele limiet comprimeren bij enig vervormingsniveau.
De rate-distortionstelling (Shannon, 1959): voor elke R > R(D) bestaan codes die verwachte vervorming van ten minste D bereiken. Voor R < R(D): geen code bereikt verwachte vervorming D. De curve is een meetkundige grens in (snelheid, vervorming)-ruimte.