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=1npilogpi.
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)=1p, potom
H(X)=H(p,1p)=plogp(1p)log(1p)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)1y𝒴︀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)1H(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(pq)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)p2f(x1p1+x2p2).
Nyní provedeme indukční krok n1n:
i=1nf(xi)pi=f(xn)pn+(1pn)i=1n1f(x)pi1pnIPf(xn)pn+(1pn)f(i=1n1xipi1pi)f(xnpn+(1pn)i=1n1xipi1pn)=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(pq)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(pq)=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
0D(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 XYZ.
Poznámka
XYZp(x,y,z)=p(x)p(y|x)p(z|y).
Poznámka
XYZp(x,z|y)=p(x|y)p(z|y).
Poznámka Je-li Z=f(Y), potom XYZ.
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 XYZ, 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 PeP[X^X].
Věta Fanova nerovnost
h(Pe)+Pelog(|𝒳︀|1)H(X|Y).
Důsledek slabší verze
PeH(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,1Pe)=h(Pe).
První člen si rozepíšeme:
H(X|E,Y)=H(X|E=0,Y)0P[E=0]1Pe+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)),p1pm 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=1p1. Fanova nerovnost nám říká
h(1p1)+(1p1)log(m1)H(X|Y)=H(X)=j=1mpjlogpj.
Zvolíme-li konkrétně p2==pm1p1m1, potom nastane rovnost.

Asymptotická nerovnost velkých čísel

Připomeňme si z PRST:
Definice XnPx, pokud pro všechna ε>0 platí
limnP[|XnX|ε]=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
1nlogp(X1,,Xn)PH(X).
Důkaz
1nlogp(x1,,xn)=1nlogi=1np(Xi)=1ni=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|2n(H(x)+ε)p(x1,,xn)2n(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)ε1nlogp(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)xAε(n)p(x)2n(H(x)+ε)xAε(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))=xAε(n)p(x)2n(H(x)ε)xAε(n)1.
Důsledek |Aε(n)|=Θ(2nH(x)).

Kódování a komprese informace

Definice Nechť X(𝒳︀,p(x)) je zdroj informace a D,𝒟︀{0,,D1}. 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 xix~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ódyjednoznačně dekódovatelné kódynesingulární kódyvš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:10,20,30,40,
C2:10,201,310,4100,
C3:10,201,3011,4111,
C4:10,210,3110,4111.
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=1mDi1.
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 maxim^i. Pokud strom prodloužíme, aby obsahoval všechna slova délky , kódovému slovu C(i) bude příslušet Di koncových uzlů. Těch je celkem D, takže máme
i=1mDiD.
Podělením D dostaneme kýženou nerovnost. Mějme nyní daná čísla 1m. 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=1Di1.
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)y1yi přiřaďme číslo c(i)[0.y1yi]D=j=1liyjDj. Jelikož kód je instantní, toto číslo zabírá celý interval c(i),c(i)+Di). Z disjunktnosti těchto intervalů přímo plyne znění nerovnosti. Máme-li naopak dané délky 12, 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{Li=1mpii|(1,,m)m,i=1mDi1}.
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 LHD(X), přičemž rovnost nastává, právě když pro všechna x𝒳︀ je p(x)=D(x).
Důkaz
LHD(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:
LHD(X)=x𝒳︀p(x)logDp(x)q(x)x𝒳︀p(x)logD(x~𝒳︀D(x))=DD(pq)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=Dn.
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)LSFHD(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)LnHD(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(pq)E(X)<HD(p)+DD(pq)+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=1kmaxa(m)Dmm=1kmax1=kmax.
Máme tedy x𝒳︀D(x)kmaxk. 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 D1, 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,,D1, 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 jk,
  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 1m1=m. Na základě něj můžeme definovat sloučený kód Cm1, 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=1mpii=i=1m2pii+pm1(m1+1)+pm(m1+1)=L(Cm1)+pm1+pm.
Teď budeme hledat optimální kód pro m1 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,jP[Xn+1=j|Xn=i]. Potom
p(i1,,in)=qnk=1m1𝐏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)limnH(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=nlogm(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,loglogi1(mod2),0,loglogi0(mod2).
Tedy H(Xi)=loglogimod2. 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)limnH(Xn|Xn1,,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|Xn1,,X1)=stacionárníH(Xn|Xn1,,X1).
Jelikož je posloupnost zároveň nezáporná, limita existuje.
Lemma limita Cesàrova součtu Má-li posloupnost (an) limitu a, potom i bn1ni=1naia.
Důkaz Nechť ε>0. Z definice limity víme, že pro všechna n od nějakého nε je |ana|<ε. Potom
|bna|=|1ni=1naia|=|1ni=1n(aia)|1ni=1n|aia|=1ni=1nε|aia|+1ni=nεn|aia|1ni=1nε|aia|+ε.
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)=ijqi𝐏i,jlog𝐏i,j.
Důkaz
(p)=stacionární~(p)=deflimnH(Xn|Xn1,,X1)=MarkovlimnH(Xn|Xn1)=stacionárníH(X2|X1),
H(X2|X1)=iH(X2|X1=i)P[X1=i]=ijqi𝐏i,jlog𝐏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).
Definice Nechť n. n-té bezpaměťové rozšíření kanálu K=𝒳︀,p(y|x),𝒴︀ je trojice 𝒦︀n𝒳︀n,pn(y|x),𝒴︀n, kde pn(y|x)i=1np(yi|xi).
Definice Nechť M,n. (m,n)-kód pro kanál 𝒦︀n=𝒳︀n,pn(y|x),𝒴︀n se skládá z kódové knihy {x(1),,x(M)},x:M^𝒳︀n a dekodéru δ:𝒴︀nM^.
Definice Podmíněná pravděpodobnost chyby (M,n)-kódu je
λi???
TBD
Definice Rychlost přenosu informace (M,n)-kódem pro kanál 𝒦︀ je RlogMn.
Definice Rychlost R0 je dosažitelná v kanálu 𝒦︀, pokud existuje posloupnost (2nR,n)-kódů taková, že limnλ(n)=0.
Definice Operační kapacita kanálu 𝒦︀ je sup{R0|Rje dosažitelná v𝒦︀}.

Typické dvojice zpráv

Definice Nechť ε>0 a (X,Y)(𝒳︀×𝒴︀,p(x,y)) je dvojitý zdroj. Dvojice zpráv (x,y) je ε-typická, pokud Množinu všech ε-typických dvojic zpráv značíme Ae(n).
Věta Nechť (X,Y) je dvojice náhodných posloupností délky n s rozdělením pravděpodobnosti
pn(x,y)=i=1np(xi,yi).
Potom pro libovolné ε>0 platí:
  1. limnP[(X,Y)Aε(n)]=1,
  2. Pro všechna n je
    |Aε(n)|2n(H(X,Y)ε),
    a pro dostatečně velká n je
    |Aε(n)|(1ε)2n(H(X,Y)ε).
  3. ???
Důkaz
  1. 1nlogpn(x)=1nlogi=1np(xi)=1ni=1nlogp(xi)PElogp(x)=H(x).
    Z toho pro všechna ε>0
    limnP[|1nlogpn(x)H(X)|>ε]=0.
    Analogicky pro pn(y) a pn(x,y). Díky tomu jistě najdeme takové n0(ε), že pro všechna n>n0(ε) je
    P(B1)P[|1nlogpn(x)H(X)|>ε]<ε3,
    P(B2)P[|1nlogpn(y)H(Y)|>ε]<ε3,
    P(B3)P[|1nlogpn(x,y)H(X,Y)|>ε]<ε3.
    Potom
    P[(X,Y)Aε(n)]=P(B1B2B3)>1ε.

Základní věta teorie informace

Věta Shannonova Všechny rychlosti přenosu informace menší než kapacita kanálu 𝒦︀=𝒳︀,p(y|x),𝒴︀ jsou dosažitelné. Tedy pro každé R<C(𝒦︀) existuje posloupnost (2nR,n)-kódů taková, že
ε>0,n0,n>n0:λ(n)<ε.
Jinými slovy Coper(𝒦︀)C(𝒦︀). Naopak pro každou takovou posloupnost kódů platí RC(𝒦︀), tedy Coper(𝒦︀)=C(𝒦︀).
Důkaz Zvolme nějakou pravděpodobnost p(x). Předpokládejme pro jednoduchost, že 2nR. Jako kódovou knihu vezmeme náhodnou matici řádu 2nR×n obsahující náhodné proměnné s rozdělením (𝒳︀,p(x)), kde značíme 𝒞︀i,j=xj(i). Pravděpodobnost, že jsme zvolili daný ponkrétní kód, je
P(𝒞︀)=w=12nRi=1np(xi(w)).
Zprávu W volíme rovnoměrně: P[W=w]2nR. Kanálem pošleme kódové slovo x(w). Na výstupu obdržíme y takové, že pn(y)=pn(y|x(w)). Dekodér bude fungovat tak, že δ(y)=w^, pokud existuje právě jedno w^𝒲︀ takové, že (x(w^),y)Aε(n). Jinak δ(y)=0. Označme [ww^] množinu jevů, kdy dojde k chybě, Pe(n)(𝒞︀) průměrnou pravděpodobnost chyby pro daný kód a λw𝒫︀[δ(Y)w|X=x(w)]. Potom
P()=𝒞︀P(|𝒞︀)P(𝒞︀)=𝒞︀P(𝒞︀)Pe(n)(𝒞︀)=𝒞︀P(𝒞︀)12nRw=12nRλw(𝒞︀)=12nRw=12nR𝒞︀P(𝒞︀)λw(𝒞︀)=12nRw=12nR𝒞︀P(𝒞︀)λ1(𝒞︀)=𝒞︀P(𝒞︀)λ1(𝒞︀)=P(|W=1).
Označme w[(X(w),Y)Aε(n)]. Potom
P(|W=1)=P(1w=22nRw|W=1)P(1|W=1)+w=22nRP(w|W=1).
Odhadneme členy součtu na pravé straně: TBD