Teorie informace

Předpokladem je základní znalost pravděpodobnosti a statistiky.

Zkouška: klasická matematická – písemná a ústní část

Model digitální informace

  1. Zdroj vysílá informaci.
  2. Kodér zdroje zajišťuje, aby vysílaná informace měla co nejmenší objem.
  3. Kodér kanálu se snaží minimalizovat pravděpodobnost chyby.
  4. Kanál přenáší informaci a může do ní vnést nějakou chybu.
  5. Dekodér kanálu se snaží invertovat to, co udělal kodér kanálu, a opravit chyby.
  6. Dekodér zdroje se snaží invertovat to, co udělal kodér zdroje.

Pro návrh efektivního přenosu informace je nutné znát četnost výskytu jednotlivých zpráv.

Kanál má jistou kapacitu, kterou nelze překročit, jinak dojde k chybě – to formuloval matematik Claude Shannon.

Příklad Dostihů se účastní 8 koní s pravděpodobností výhry 12,14,18,116,164,164,164,164. Mohli bychom kódovat každého pomocí tří bitů: 000,001,010,011,100,101,110,111. Potom zjevně průměrná délka zprávy bude 3. Ale místo toho můžeme vymyslet kód, kde častěji vyhrávající koně mají kratší kódy:
0,10,110,1110,111100,111110,111101,111111.
Když si to spočteme, zjistíme, že průměrná délka vyslaného kódu je jen 2.

Neurčitost

Definice Nechť 𝒳︀ je spočetná množina možných zpráv a p(x) je pravděpodobnostní rozdělení na 𝒳︀. Zdroj informace je dvojice (𝒳︀,p(x)). Zpráva je náhodná veličina X∼(𝒳︀,p(x)).
Konvence Symbolem log budeme značit dvojkový logaritmus.
Definice Nechť zpráva x má pravděpodobnost p(x). Potom její neurčitost je −logp(x).
Definice Entropie zdroje X∼(𝒳︀,p(x)) je
H(X)≔−∑x∈𝒳︀p(x)⋅logp(x)=Elog1p(X).
Poznámka Jelikož entropie vůbec nezávisí na samotných prvcích množiny 𝒳︀, ale pouze na jejich pravděpodobnostech, budeme také používat značení
H(p1,…,pn)≔−∑i=1npi⋅logpi.
Poznámka Intuitivně entropie vyjadřuje, jak „těžké“ je předpovědět hodnotu zprávy.
Příklad Máme-li Bernoulliovo rozdělení 𝒳︀={0,1},p(1)=p,p(0)=1−p, potom
H(X)=H(p,1−p)=−p⋅logp−(1−p)⋅log(1−p)≕h(p).
Věta nezápornost entropie Pro libovolný zdroj X∼(𝒳︀,p(x)) platí H(X)≥0, přičemž rovnost nastává, právě když rozdělení je Diracovo, tedy pro nějaké x0∈𝒳︀ je p(x0)=1.
Důkaz Triviální.
Definice Nechť (X,Y) je náhodný vektor se sdruženou pravděpodobností p(x,y). Potom jeho sdružena entropie je
H(X,Y)≔−∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x,y)=Elog1p(X,Y).
Věta Jsou-li X,Y nezávislé, potom H(X,Y)=H(X)+H(Y).
Důkaz
H(X,Y)=−∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x,y)=−∑x∈𝒳︀∑y∈𝒴︀p(x)⋅p(y)⋅(logp(x)+logp(y))=−∑x∈𝒳︀p(x)⋅logp(x)⋅∑y∈𝒴︀p(y)⏟1−∑y∈𝒴︀p(y)⋅logp(y)⋅∑x∈𝒳︀p(x)⏟1=H(X)+H(Y).
Definice Střední podmíněná entropie zdroje (X,Y)∼(𝒳︀×𝒴︀,p(x,y)) je
H(Y|X)≔∑x∈𝒳︀p(x)⋅H(Y|X=x).
Poznámka Pro střední podmíněnou entropii platí
H(Y|X)≔∑x∈𝒳︀p(x)∑y∈𝒴︀p(y|x)⋅logp(y|x)=∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(y|x)=Elog1p(Y|X).
Věta řetězové pravidlo Mějme zdroj (X,Y)∼(𝒳︀×𝒴︀,p(x,y)). Potom H(X,Y)=H(X)+H(Y|X).
Důkaz
H(X,Y)=−∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x,y)=−∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅(logp(x)+logp(y|x))=−∑x∈𝒳︀p(x)⋅logp(x)⋅∑y∈𝒴︀p(y)⏟1−H(Y|X)=H(X)+H(Y|X).

Relativní entropie a informace

Definice Nechť p(x),q(x) jsou rozdělení na 𝒳︀, přičemž q(x)>0. Potom relativní entropie alias informační divergence alias Kullback-Leiblerova divergence je veličina
D(p‖q)≔∑x∈𝒳︀p(x)⋅logp(x)q(x).
Poznámka Relativní entropie je něco jako vzdálenost, ale není to metrika (nesplňuje symetrii ani trojúhelníkovou nerovnost).
Definice Informace ve zprávě Y o zprávě X zdroje (X,Y)∼(𝒳︀×𝒴︀,p(x,y)) je
I(x;y)≔D(p(x,y)‖p(x)p(y))=∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x,y)p(x)p(y).
Poznámka Jsou-li X,Y nezávislé, potom I(X,Y)=0. Tedy informace nám udává, jak moc nám Y řekne o X.
Věta
I(X;Y)=I(Y;X).
Důkaz Triviální.
Věta
I(X;Y)=H(X)−H(X|Y).
Poznámka Interpretace: Informace udává, o kolik se sníží neurčitost X, když se dozvíme Y.
Důkaz
I(X;Y)=∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x,y)p(x)p(y)=∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x|y)−∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x)=∑x∈𝒳︀∑y∈𝒴︀p(x,y)⋅logp(x|y)−∑x∈𝒳︀p(x)⋅logp(x)=H(X)−H(X|Y).
Důsledek
I(X;Y)=H(X)+H(Y)−H(X,Y).
Důsledek
I(X;Y)≤min{H(X),H(Y)}.
Důsledek
I(X;X)=H(X).
Poznámka Všechny tyto vztahy můžeme hezky znázornit do Vennova diagramu: TBD: dokreslit

Konvexnost a Jensenova nerovnost

Definice Funkce f je konvexní na intervalu (a,b), pokud pro všechna λ∈[0,1],x,y∈(a,b) platí
f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y).
Pokud rovnost nastane jen pro λ∈{0,1}, f je ryze konvexní. Je-li −f konvexní, f je konkávní.
Věta Jensenova nerovnost Nechť X∼(𝒳︀,p(x)) je zdroj a f je konvexní funkce. Potom
Ef(X)≥f(EX)
neboli
∑x∈𝒳︀f(x)p(x)≥f(∑x∈𝒳︀xp(x)).
Navíc je-li f ryze konvexní, potom rovnost nastává jen pro Diracovo rozdělení.
Důkaz Dokážeme pro konečné 𝒳︀ indukcí přes |𝒳︀|; pro spočetnou 𝒳︀ stačí provést limitní přechod. Pro |𝒳︀|=2 to plyne přímo z definice konvexnosti:
f(x1)p1+f(x2)p2≥f(x1p1+x2p2).
Nyní provedeme indukční krok n−1→n:
∑i=1nf(xi)pi=f(xn)pn+(1−pn)⋅∑i=1n−1f(x)pi1−pn≥IPf(xn)pn+(1−pn)⋅f(∑i=1n−1xipi1−pi)≥f(xnpn+(1−pn)⋅∑i=1n−1xipi1−pn)=f(∑i=1nxipi).
Věta informační nerovnost Nechť p(x),q(x) jsou rozdělení pravděpodobnosti na 𝒳︀ a q(x)>0. Potom D(p‖q)≥0, přičemž rovnost nastává, právě když p=q.
Důkaz V důkazu použijeme Jensenovu nerovnost s tím, že logaritmus je ryze konkávní funkce.
−D(p‖q)=−∑x∈𝒳︀p(x)⋅logp(x)q(x)=∑x∈𝒳︀p(x)⋅logq(x)p(x)≤log(∑x∈𝒳︀p(x)⋅q(x)p(x))=0.
Důsledek I(X;Y)=0, přičemž rovnost nastává, právě když X,Y jsou nezávislé.
Důsledek Pro konečný zdroj X∼(𝒳︀,p(x)) platí H(X)≤log|𝒳︀|.
Důkaz Nechť u(x)=1|𝒳︀| je rovnoměrné rozdělení na 𝒳︀. Potom
0≤D(p(x)‖u(x))=∑x∈𝒳︀p(x)⋅log(p(x)⋅|𝒳︀|)=−H(x)+log|𝒳︀|.
Důsledek H(X|Y)≤H(X), přičemž rovnost nastane, právě když X,Y jsou nezávislé.
Poznámka To intuivivně říká, že znalost dalších informací může v průměru jen snížit neurčitost. Ovšem pro jednu konkrétní informaci to platit nemusí, tedy může být H(X|Y=y)>H(X). Příkladem je p(x1,y1)=0,p(x2,y1)=34,p(x1,y2)=18,p(x2,y2)=18.
Důsledek Nechť (X1,…,Xn) je náhodný vektor s rozdělením p(x1,…,xn). Potom
H(X1,…,Xn)≤∑i=1nH(Xi).

Data processing inequality

Definice Náhodné veličiny X,Y,Z tvoří Markovův řetězec, pokud p(z|y,x)=p(z|y). Značíme X→Y→Z.
Poznámka
X→Y→Z⟺p(x,y,z)=p(x)⋅p(y|x)⋅p(z|y).
Poznámka
X→Y→Z⟺p(x,z|y)=p(x|y)⋅p(z|y).
Poznámka Je-li Z=f(Y), potom X→Y→Z.
Definice Podmíněná informace ve zprávě Y o zprávě X při dané zprávě Z je
I(X;Y|Z)≔H(X|Z)−H(X|Y,Z).
Lemma řetězové pravidlo pro informaci
I(X;Y,Z)=I(X;Z)+I(X;Y|Z).
Důkaz
I(X;Y,Z)=H(X)−H(X|Y,Z)=H(X)−H(X|Z)+H(X|Z)−H(X|Y,Z)=I(X;Z)+I(X;Y|Z).
Věta data processing inequality Je-li X→Y→Z, potom I(X;Y)≥I(X;Z).
Poznámka Interpretace: Zpracováním dat nemůžeme zvýšit množství informace, kterou nám dávají.
Důkaz
I(X,Z)≤I(X;Z)+I(X;Y|Z)=I(X;Y,Z)=I(X;Y)+I(X;Z|Y)=I(X;Y).

Fanova nerovnost

Byla poslána zpráva X a přijata zpráva Y. Chceme odhadnout X na základě Y, tedy X^=g(Y). Jaká je pravděpodobnost, že jsme uhodli správně?
Definice Nechť (X,Y)∼(𝒳︀×𝒴︀,p(x,y)) je zdroj a X^ je odhad X. Potom pravděpodobnost chyby je Pe≔P[X^≠X].
Věta Fanova nerovnost
h(Pe)+Pe⋅log(|𝒳︀|−1)≥H(X|Y).
Důsledek slabší verze
Pe≥H(X|Y)−1log|X|.
Důkaz Definujme náhodnou veličinu E≔[X^≠X]. Potom
H(X,E|Y)=H(X|Y)+H(E|X,Y)
a zároveň
H(X,E|Y)=H(E|Y)+H(X|E,Y).
Z toho si vyjádříme
H(X|Y)=H(E|Y)+H(X|E,Y)−H(E|X,Y).
Jelikož E je jednoznačně určena podle X,Y, máme H(E|X,Y)=0. Druhý člen odhadneme jako
H(E|Y)≤H(E)=H(Pe,1−Pe)=h(Pe).
První člen si rozepíšeme:
H(X|E,Y)=H(X|E=0,Y)⏟0⋅P[E=0]⏟1−Pe+H(x|E=1,Y)⏟≤log((𝒳︀)−1)⋅P[E=1]⏟Pe.
Tím je věta dokázána.
Příklad Nechť X∼(m^,(p1,…,pm)),p1≥⋯≥pm a Y je nezávislá na X. To znamená, že na základě X nemáme naprosto žádnou informaci o Y. Nezbývá nám než prostě tipnout nejčastější hodnotu: X^≔1, čímž se trefíme s pravděpodobností p1, takže Pe=1−p1. Fanova nerovnost nám říká
h(1−p1)+(1−p1)⋅log(m−1)≥H(X|Y)=H(X)=−∑j=1mpj⋅logpj.
Zvolíme-li konkrétně p2=⋯=pm≔1−p1m−1, potom nastane rovnost.

Asymptotická nerovnost velkých čísel

Připomeňme si z PRST:
Definice Xn→Px, pokud pro všechna ε>0 platí
limn→∞P[|Xn−X|≥ε]=0.
Věta zákon velkých čísel TBD
Analogií zákona velkých čísel v teorii informace je následující věta.
Věta asymptotická ekvipartiční vlastnost Nechť X1,…,Xn jsou nezávislé stejně rozdělené náhodné veličiny s pravděpodobnostní funkcí X∼(𝒳︀,p(x)). Potom
−1n⋅logp(X1,…,Xn)→PH(X).
Důkaz
−1n⋅logp(x1,…,xn)=−1n⋅log∏i=1np(Xi)=1n⋅∑i=1nlog1p(Xi).
Z toho podle zákona velkých čísel platí znění věty. K tomu ale musíme ověřit podmínky. Střední hodnota je konečná, jinak by entropie vůbec nebula definovaná. Že je rozptyl konečný, už nám vlastně nic nezaručuje, ale většinou pracujeme s konečnou množinou 𝒳︀, takže je to jedno.
Definice Nechť X1,…,Xn jsou nezávislé stejně rozdělené náhodné veličiny s pravděpodobnostní funkcí X∼(𝒳︀,p(x)). Potom pro každé ε>0 definujeme množinu ε-typických zpráv:
Aε(n)≔{(x1,…,xn)∈𝒳︀n|2−n⋅(H(x)+ε)≤p(x1,…,xn)≤2−n⋅(H(x)−ε)}.
Věta Nechť X1,…,Xn jsou nezávislé stejně rozdělené náhodné veličiny. Je-li (x1,…,xn)∈Aε(n), potom
H(X)−ε≤−1n⋅logp(x1,…,xn)≤H(X)+ε.
Důkaz Plyne přímo z definice typických zpráv.
Věta Nechť X1,…,Xn jsou nezávislé stejně rozdělené náhodné veličiny. Potom P(Aε(n))>1−ε pro dostatečně velká n a všechna ε>0.
Důkaz TBD
Věta Nechť X1,…,Xn jsou nezávislé stejně rozdělené náhodné veličiny. Potom |Aε(n)|≤2n⋅(H(X)+ε) pro všechna n∈ℕ,ε>0.
Důkaz
1=∑x∈𝒳︀np(x)≥∑x∈Aε(n)p(x)≥2−n(H(x)+ε)∑x∈Aε(n)1.
Věta Nechť X1,…,Xn jsou nezávislé stejně rozdělené náhodné veličiny. Potom |Aε(n)|≥(1−ε)2n⋅(H(x)−ε) pro dostatečně velká n a všechna ε>0.
Důkaz Pro dostatečně velká n máme
1−ε<P(Aε(n))=∑x∈Aε(n)p(x)≤2−n(H(x)−ε)∑x∈Aε(n)1.
Důsledek |Aε(n)|=Θ(2n⋅H(x)).

Kódování a komprese informace

Definice Nechť X∼(𝒳︀,p(x)) je zdroj informace a D∈ℕ,𝒟︀≔{0,…,D−1}. Kód zdroje X je zobrazení C:𝒳︀→𝒟︀*. Délku kódového slova x∈𝒳︀ značíme l(x).
Definice Kód C je nesingulární, pokud je to prosté zobrazení.
Definice Rozšíření kódu C:𝒳︀→𝒟︀* je zobrazení C*:𝒳︀*→𝒟︀* dané vztahem C*(x1,…,xn)≔C(x1)⋯C(xn).
Definice Kód je jednoznačně dekódovatelný, pokud jeho rozšíření je prosté zobrazení.
Definice Kód je instantní, pokud žádné slovo z C(𝒳︀) není prefixem jiného slova z C(𝒳︀).
Věta Je-li kód instantní, potom je jednoznačně dekódovatelný.
Důkaz Dokážeme obměněnou implikaci. Nechť existují x,x~∈𝒳︀* taková, že C(x)=C(x~). Označme i nejmenší číslo takové, že xi≠x~i. Potom C(xi),C(x~i) jsou dvě různá slova, z nichž jedno musí být prefixem druhého, takže kód není instantní.
Důsledek Platí řetězec striktních inkluzí:
instantní kódy⊊jednoznačně dekódovatelné kódy⊊nesingulární kódy⊊všechny kódy.
Důkaz Nestriktní inkluze jsme si buď již ukázali, nebo jsou zřejmé. Ukážeme si příklady demonstrující striktnost. Pro 𝒳︀≔{1,2,3,4} definujme binární kódy
C1:1↦0,2↦0,3↦0,4↦0,
C2:1↦0,2↦01,3↦10,4↦100,
C3:1↦0,2↦01,3↦011,4↦111,
C4:1↦0,2↦10,3↦110,4↦111.
Potom C1 je singulární, C2 je nesingulární, ale nejednoznačně dekódovatelný (například C(4)=C(3,1)), C3 je jednoznačně dekódovatelný (jelikož je „instantní pozpátku“), ale neinstantní a C4 je instantní.
Věta Kraftova nerovnost Nechť C je instantní D-znakový kód na 𝒳︀≔m^. Označme ℓi≔|C(i)|. Potom
∑i=1mD−ℓi≤1.
Naopak, pokud nějaká čísla ℓ1,…,ℓm splňují tuto nerovnost, potom existuje instantní D-znakový kód s těmito délkami.
Důkaz Nakreslíme si všechna kódová slova do prefixového stromu. Jelikož kód je instantní, všechna slova budou v koncových uzlech. Označme ℓ≔maxi∈m^ℓi. Pokud strom prodloužíme, aby obsahoval všechna slova délky ℓ, kódovému slovu C(i) bude příslušet Dℓ−ℓi koncových uzlů. Těch je celkem Dℓ, takže máme
∑i=1mDℓ−ℓi≤Dℓ.
Podělením Dℓ dostaneme kýženou nerovnost. Mějme nyní daná čísla ℓ1≤⋯≤ℓm. Sestavme prefixový strom pro všechna slova délky ℓm. Nyní postupně pro každé i=1,…,m zvolíme za C(i) libovolné slovo délky ℓi, které ještě zbývá ve stromě, a škrtneme ho včetně všech větví vycházejících z něj. Z konstrukce plyne, že vzniklý kód je instantní, a analogicky jako předtím můžeme odůvodnit, že v každém kroku nějaké slovo zbyde.
Věta rozšířená Kraftova nerovnost Nechť C je instantní D-znakový kód na 𝒳︀≔ℕ. Označme ℓi≔|C(i)|. Potom
∑i=1∞D−ℓi≤1.
Naopak, pokud nějaká čísla ℓ1,ℓ2,… splňují tuto nerovnost, potom existuje instantní D-znakový kód s těmito délkami.
Důkaz Každému kódovému slovu C(i)≕y1⋯yℓi přiřaďme číslo c(i)≔[0.y1⋯yℓi]D=∑j=1liyjD−j. Jelikož kód je instantní, toto číslo zabírá celý interval ⟨c(i),c(i)+D−ℓi). Z disjunktnosti těchto intervalů přímo plyne znění nerovnosti. Máme-li naopak dané délky ℓ1≥ℓ2≥⋯, analogicky jako u předchozího důkazu si budeme postupně rezervovat intervaly a nerovnost nám zaručí, že vždy zbyde místo.
Chceme pro daný zdroj najít instantní kód s minimální střední délkou zprávy. Hledáme tedy
min{L≔∑i=1mpiℓi|(ℓ1,…,ℓm)∈ℕm,∑i=1mD−ℓi≤1}.
Kdyby to vpravo nebyla nerovnost, ale rovnost, a hledali bychom reálná ℓi, mohli bychom použít metodu Lagrangeových multiplikátorů, čímž by nám vyšlo ℓ1*=−logDpi. Minimum potom vyjme L*=HD(X).
Věta Střední délka instantního D-znakového kódu pro zdroj X∼(𝒳︀,p(x)) splňuje nerovnost L≥HD(X), přičemž rovnost nastává, právě když pro všechna x∈𝒳︀ je p(x)=D−ℓ(x).
Důkaz
L−HD(X)=∑x∈𝒳︀p(x)⋅ℓ(x)+∑x∈𝒳︀p(x)⋅logDp(x)=∑x∈𝒳︀p(x)⋅logDp(x)D−ℓ(x).
Označíme-li q(x)≔D−ℓ(x)∑x~∈𝒳︀D−ℓ(x~), můžeme pokračovat:
L−HD(X)=∑x∈𝒳︀p(x)⋅logDp(x)q(x)−∑x∈𝒳︀p(x)⋅logD(∑x~∈𝒳︀D−ℓ(x))=DD(p‖q)−logD(∑x~∈𝒳︀D−ℓ(x))≥0.
Definice Pravděpodobnostní rozdělení (p1,p2,…) je D-adické, pokud pro každé i existuje n∈ℕ takové, že pi=D−n.
Poznámka Optimální kód podle věty můžeme najít jen pro D-adické rozdělení. Jinak budeme muset vzít horní celou část.
Definice Shannon-Fanův kód pro zdroj X∼(𝒳︀,p(x)) je kód s délkami
ℓi=⌈logD1pi⌉.
Poznámka Pro Shannon-Fanův kód je HD(x)≤LSF≤HD(x)+1. Vidíme, že je-li entropie velká, příliš se nám to nezvětší, ale pro malou entropii může být špatný.
Shannon-Fanův kód můžeme zkusit vylepšit tím, že místo jednotlivých zpráv budeme kódovat n-tice zpráv. Potom máme Ln=1nEℓ(X1,…,Xn), takže bude HD(x)≤Ln≤HD(x)+1n.
Věta Pro střední délku Shannon-Fanova D-znakového kódu pro rozdělení p(x) při volbě délek kódových slov ℓ(x)=⌈logD1q(x)⌉ platí
HD(p)+DD(p‖q)≤Eℓ(X)<HD(p)+DD(p‖q)+1.
Otázkou je, jestli jsme si omezením na instantní kódy zbytečně nezvýšili potřebnou délku, když nám ve skutečnosti stačí jednoznačně dekódovatelné. Následující věta říká, že ne.
Věta McMillen Délky kódových slov libovolného jednoznačně dekódovatelného kódu zdroje X∼(𝒳︀,p(x)) splňuje Kraftovu nerovnost
∑x∈𝒳︀D−ℓ(x)≤1.
Naopak, pokud nějaké délky splňují tuto nerovnost, potom existuje jednoznačně dekódovatelný kód.
Důkaz Druhé tvrzení triviálně plyne z Kraftovy věty, takže stačí dokázat první tvrzení. Je-li kód C jednoznačně dekódovatelný, potom jeho k-té rozšíření Ck(x1,…,xk)≔C(x1)⋯C(xk) je nesingulární pro každé k∈ℕ. Označme a(m) počet x∈𝒳︀k, která se zakódují do nějakého slova délky m. Z nesingularity plyne a(m)≤Dm. Máme
(∑x∈𝒳︀D−ℓ(x))k=∑x1∈𝒳︀⋯∑xk∈𝒳︀∏i=1kD−ℓ(xi)=∑(x1,…,xk)∈𝒳︀kDℓ(x1,…,xn)=∑m=1k⋅ℓmaxa(m)⋅D−m≤∑m=1k⋅ℓmax1=k⋅ℓmax.
Máme tedy ∑x∈𝒳︀D−ℓ(x)≤k⋅ℓmaxk. Je-li ℓmax omezené, toto pro k→∞ konverguje k 1, takže jsme hotovi. To pro konečnou množinu 𝒳︀ platí. Máme-li nekonečně mnoho zpráv, vybereme z nich jen m a provedeme limitní přechod m→∞.

Huffmanův kód

Definice Huffmanův d-znakový kód pro konečný zdroj X∼(𝒳︀,p(x)) je definován iterativně takto: Pokud počet zpráv není roven 1 modulo D−1, přidáme potřebný počet zpráv s pravděpodobnostmi 0. Následně opakovaně vyhledáme D zpráv s nejmenší pravďpodobností a přiřadíme jim písmena 0,…,D−1, přičemž pokud už nějaký kód mají, tak nové písmeno přidáme před něj. Následně ve zdroji tyto zprávy sloučíme do jedné. Toto budeme opakovat až do doby, než nám zbyde jen jedna zpráva.
Lemma Pro libovolné rozdělení p existuje optimální instantní binární kód takový, že
  1. je-li pj>pk, potom ℓj≤ℓk,
  2. dvě nejdelší kódová slova mají stejnou délku,
  3. dvě nejdelší kódová slova se liší pouze v posledním bitu a přísluší dvěma nejméně pravděpodobným zprávám.
Poznámka Ve skriptech je tohle lemma napsané špatně. Tvrdí, že existují právě dvě nejdelší kódová slova, což není obecně pravda (například pro čtyři zprávy se stejnou pravděpodobností je optimální kód {00,01,10,11}).
Důkaz
  1. Pokud bychom prohodili kódová slova j,k, nesměl by tím vzniknout lepší kód.
  2. Kdyby dvě nejdelší slova měla stejnou délku, mohli bychom jedno zkrátit, čímž vytvoříme lepší kód. Jelikož původní kód byl instantní, nový bude taky instantní.
  3. Tvrzení odpovídá tomu, že ve stromě každý koncový uzel má sourozence. Což kdyby neměl, tak by šel poslední bit useknout a pořád by to byl instantní kód.
Věta Huffmanův kód konečného zdroje je optimální kód pro tento zdroj.
Důkaz Vezměme optimální kód z tvrzení lemmatu; označme ho Cm s délkami ℓ1≤⋯≤ℓm−1=ℓm. Na základě něj můžeme definovat sloučený kód Cm−1, kde vezmeme dvě nejdelší zmíněná slova a jejich společný prefix (který je o jeden bit kratší) přiřadíme nové zprávě, která nahradí dvě původní zprávy a bude mít součet jejich pravděpodobností. Potom
L(Cm)=∑i=1mpiℓi=∑i=1m−2piℓi′+pm−1(ℓm−1′+1)+pm(ℓm−1′+1)=L(Cm−1)+pm−1+pm.
Teď budeme hledat optimální kód pro m−1 zpráv. Iterativně pokračujeme, až dojdeme ke dvěma zprávám a tam už je to jasné. Jelikož v každém kroku jsme zachovávali optimalitu, i původní kód je optimální. Konstrukce přesně odpovídá Huffmanovu kódu.

Rychlost entropie náhodných procesů

Definice Náhodný proces je posloupnost náhodných veličin X1,X2,… charakterizovaná sdruženou pravděpodobnostní funkcí P[X1=x1,…,Xn=xn]=p(x1,…,xn).
Definice Náhodný proces je stacionární, pokud pro každé n,ℓ∈ℕ a pro všechna (x1,…,xn)∈𝒳︀n je
P[X1=x1,…,Xn=xn]=P[X1+ℓ=x1,…,Xn+ℓ=xn].
Definice Náhodný proces je markovský/Markovův, pokud pro všechna n∈ℕ a pro všechna (x1,…,xn)∈𝒳︀n je
P[Xn+1=xn+1|Xn=Xn,…,X1=x1]=P[Xn+1=xn+1|Xn=xn].
Definice Markovský proces je homogenní, pokud pro všechna n∈ℕ,a,b∈𝒳︀ je
P[Xn+1=b|Xn=a]=P[X2=b|X1=a].
Věta Je-li řetězec stacionární a markovský, potom je homogenní.
Důkaz
P[Xn+1=b|Xn=a]=P[Xn=a,Xn+1=b]P[xn=a]=P[X1=a,X2=b]P[X1=a]=P[X1=a|X2=b].
Poznámka Markovský homogenní proces je charakterizován počátečním rozdělením q, kde qi=P[x1=i], a maticí přechodu 𝐏, kde 𝐏i,j≔P[Xn+1=j|Xn=i]. Potom
p(i1,…,in)=qn⋅∏k=1m−1𝐏ik,ij+1,
pn+1(j)=∑i=1mpn(i)⋅𝐏i,j.
Věta Homogenní markovský řetězec je stacionární, pokud q=q⋅𝐏.
Definice Rychlost entropie náhodného procesu (X1,…,Xn)∼(𝒳︀*,p) je
ℋ(p)≔limn→∞H(X1,…,Xn)n.
Příklad Máme-li m písmen s tím, že všechny posloupnosti jsou stejně pravděpodobné, potom
H(X1,…,Xn)=logmn=n⋅logm∴ℋ(p)=logm.
Příklad Jsou-li X1,…,Xn nezávislé stejně rozdělené, potom ℋ(p)=H(p1).
Příklad Nechť X1,…,Xn jsou nezávislé veličiny s pravděpodobnostmi
pi≔{12,⌈loglogi⌉≡1(mod2),0,⌈loglogi⌉≡0(mod2).
Tedy H(Xi)=⌈loglogi⌉mod2. Potom posloupnost H(X1,…,Xn)n osciluje, takže ℋ(p) neexistuje.
Definice Mezní podmíněná entropie symbolu náhodného procesu (X1,…,Xn)∼(𝒳︀*,p) je
ℋ~(p)≔limn→∞H(Xn|Xn−1,…,X1).
Lemma Je-li náhodný proces (X1,…,Xn) stacionární, potom ℋ~(p) existuje.
Důkaz Dokážeme, že posloupnost je nerostoucí:
H(Xn+1|Xn,…,X1)≤podmiňováníH(Xn+1|Xn−1,…,X1)=stacionárníH(Xn|Xn−1,…,X1).
Jelikož je posloupnost zároveň nezáporná, limita existuje.
Lemma limita Cesàrova součtu Má-li posloupnost (an) limitu a, potom i bn≔1n∑i=1nai→a.
Důkaz Nechť ε>0. Z definice limity víme, že pro všechna n od nějakého nε je |an−a|<ε. Potom
|bn−a|=|1n∑i=1nai−a|=|1n∑i=1n(ai−a)|≤1n∑i=1n|ai−a|=1n∑i=1nε|ai−a|+1n∑i=nεn|ai−a|≤1n∑i=1nε|ai−a|+ε.
První sčítanec konverguje k 0, takže ho můžeme od nějakého n0 omezit ε. Potom od min{nε,n0} je celý výraz menší než 2ε, takže konverguje k 0.
Věta Je-li náhodný proces (X1,…,Xn) stacionární, potom ℋ(p),ℋ~(p) existují a jsou si rovny.
Důkaz Triviálně plyne z předchozích dvou lemmat.
Poznámka Je-li proces stacionární a ergodický (definováno třeba v MEMC), jde z toho nějak odvodit, že každou zprávu dokážeme zakódovat v n⋅ℋ~(p) bitech.
Věta Je-li (X1,…,Xn)∼(𝒳︀*,p) markovský proces se stacionárním rozdělením q a maticí přechodu 𝐏, potom
ℋ(p)=−∑i∑jqi⋅𝐏i,j⋅log𝐏i,j.
Důkaz
ℋ(p)=stacionárníℋ~(p)=deflimn→∞H(Xn|Xn−1,…,X1)=Markovlimn→∞H(Xn|Xn−1)=stacionárníH(X2|X1),
H(X2|X1)=∑iH(X2|X1=i)⋅P[X1=i]=−∑i∑jqi⋅𝐏i,j⋅log𝐏i,j.

Kapacita kanálu

Přenos informace je fyzikální proces, který je vystaven nekontrolovanému šumu prostředí a nedokonalostem samotného přenosu. Máme nějaký konečný zdroj informace X∼(𝒳︀,p(x)). Pokud zdroj pozorujeme přímo, získáme informaci I(X,X)=H(X). Pozorujeme-li jen Y∼(𝒴︀,p(y)), které nějak závisí na X, dostáváme informaci I(X;Y).
Definice Informační kanál je trojice 𝒦︀=⟨𝒳︀,p(y|x),𝒴︀⟩.
Definice Informační kapacita kanálu 𝒦︀=⟨𝒳︀,p(y|x),𝒴︀⟩ je
C(𝒦︀)≔sup{I(X,Y)|X∼(𝒳︀,p(x))},
kde suprémum je přes všechna možná rozdělení pravděpodobnosti p(x).