Sannolikhetssimplexen
En sannolikhetsfördelning över q symboler är en punkt i den (q−1)-dimensionella simplexen: mängden av alla vektorer (p₁, ..., p_q) med pᵢ ≥ 0 och Σ pᵢ = 1.
För q = 2: simplexen är ett linjesegment [0,1], parametriserat av en enskild sannolikhet p. För q = 3: simplexen är en liksidig triangel i ℝ². Varje hörn är en deterministisk fördelning (all sannolikhet på en symbol); mitten är den enhetliga fördelningen.
Entropi H(p) tilldelar ett reellt tal till varje punkt på simplexen. Funktionens geometri bestämmer många grundläggande resultat.
Konkavitet
H är konkav på simplexen: för två godtyckliga fördelningar p och q och något λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
En blandning av två fördelningar har entropi minst lika stor som det vägda medelvärdet av deras individuella entropier. Intuition: att blanda två källor ökar osäkerheten.
Verifikation av konkavitet
För binär entropi H(p) är konkavitet synlig i grafen: kurvan böjs uppåt, aldrig fallande under någon korda som förbinder två punkter.
Formellt test för konkavitet: andraderivatan H''(p) ≤ 0 överallt.
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 för alla p ∈ (0,1)
Andraderivatan är strikt negativ överallt i det inre: H är strikt konkav.
Kapacitetsuppnåendefördelningen
Kanalkapacitet definieras som det maximala ömsesidiga informationen över alla indatafördelningar p(x):
C = max_{p(x)} I(X; Y)
där I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
För den binära symmetriska kanalen med felfrekvens Q: den kapacitetsuppnåendeindatafördelningen är den enhetliga fördelningen p(0) = p(1) = 0,5.
Varför: H(Y) maximeras av den enhetliga utdatafördelningen. Med en BSC ger en enhetlig indata en enhetlig utdata. Någon annan indatafördelning gör H(Y) mindre, vilket reducerar I(X;Y).
Geometriskt: den ömsesidiga informationen I(X;Y) är en konkav funktion av indatafördelningen p(x) på simplexen. Maximumet för en konkav funktion på en konvex mängd uppnås på en unik punkt (centrumet, för en symmetrisk kanal).
KL-divergens
Kullback-Leibler divergensen (relativ entropi) från fördelning q till fördelning p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 alltid (Gibbs olikhet). D(p || q) = 0 om och endast om p = q.
D är inte ett sant avstånd: det är asymmetriskt (D(p||q) ≠ D(q||p) i allmänhet) och uppfyller inte triangelolikheten. Men det fungerar som ett mått på hur långt p är från q i sannolikhetsrummet.
KL-divergens förekommer överallt i informationsteorin:
- Ömsesidig information: I(X;Y) = D(p(x,y) || p(x)p(y)). Den ömsesidiga informationen är KL-divergensen mellan den gemensamma fördelningen och produkten av marginaler — hur långt den gemensamma är från oberoende.
- Gibbs olikhet: kodningssatsen för förlustfritt följer direkt från D(p || q) ≥ 0.
- Kanalkapacitet: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
Beräkning av KL-divergens
Exempel: p = (0,5, 0,5) enhetlig binär, q = (0,8, 0,2) snedfördelad 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 bitar
Kanalkapacitet som geometriskt avstånd
Kanalkapacitet har en geometrisk tolkning i rummet för sannolikhetsfördelningar.
För en kanal p(y|x), definiera den kapacitetsuppnåendeindata fördelningen p*(x). Kapaciteten uppfyller:
C = D(p*(y) || r(y))
där p(y) = Σ p(x) p(y|x) är utdatafördelningen under det optimala indata, och r(y) = argmin_r max_x D(p(y|x) || r(y)) är den minimuminformationsutdatafördelning — punkten i utdatasannolikhetsrummet närmast (i KL-divergens) alla betingade utdatafördelningar samtidigt.
Detta är den informationsgeometriska synen: kanalkapacitet är radien för den minsta KL-divergensbollen i utdatasannolikhetsrummet som innehåller alla betingade fördelningar p(y|x=0) och p(y|x=1).
För BSC: p(y|x=0) = (1−Q, Q) och p(y|x=1) = (Q, 1−Q). Genom symmetri är minimuminformationsutdatan r(y) = (0,5, 0,5). Kapacitet = D((1−Q, Q) || (0,5, 0,5)) = 1 − H(Q). Formeln återställer standardresultatet från geometrin.
Kapacitet från KL-divergens
Verifiera den geometriska formeln: C = D(p(y|x=0) || r(y)) för en BSC med Q = 0,1, r(y) = (0,5, 0,5).
p(y|x=0) = (0,9, 0,1) (skicka 0, ta emot 0 med san. 0,9, ta emot 1 med san. 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 bitar
Kontroll: C = 1 − H(0,1) ≈ 1 − 0,469 = 0,531 bitar ✓
Hastighets-förvridning & gränserna för komprimering
Hastighets-förvridningsteorin utvidgar informationsteorin till förlustig komprimering. Istället för att fråga 'vad är minsta bitar för att exakt representera en källa?' frågar den: 'givet tolerans för viss genomsnittlig förvridning D, vad är minsta takt R(D) bitar per symbol?'
Hastighets-förvridningsfunktionen R(D) är konvex och minskande i D: mer förvridningstolerans tillåter lägre takter. Vid D = 0 (förlustfritt): R(0) = H(källa). När D ökar, R(D) → 0.
Geometriskt: R(D) spårar en kurva på planet (hastighet, förvridning). Varje uppnåelig (R, D) par ligger på eller ovan denna kurva. Punkter under kurvan är omöjliga — du kan inte komprimera under den grundläggande gränsen vid någon förvridningsnivå.
Hastighets-förvridningssatsen (Shannon, 1959): för något R > R(D) finns koder som uppnår förväntad förvridning högst D. För R < R(D): ingen kod uppnår förväntad förvridning D. Kurvan är en geometrisk gräns i (hastighet, förvridning) rummet.