1 Pravděpodobnostní prostor

Úvod do pravděpodobnosti prizmatem teorie informace Tomáš Kroupa

1

2014

Pravděpodobnostní prostor

Základním objektem teorie pravděpodobnosti je pravděpodobnostní prostor. Modeluje všechny možné elementární výsledky experimentu (množina Ω) a jejich měřitelné množiny (množinový systém A), které mají přiřazenu pravděpodobnost (pomocí pravděpodobnostní míry P ). Popišme si nejdříve přesně všechny 3 složky tohoto modelu. (i) Množina elementárních výsledků Ω je libovolná neprázdná množina. Její prvky nazýváme elementární jevy. Např. při hodu jednou kostkou máme Ω = {1, . . . , 6}, při popisu losování ve Sportce dostáváme 6 ą Ω= {1, . . . , 49} = {1, . . . , 49}6 , i=1

což je množina všech uspořádaných šestic (ω1 , . . . , ω6 ) čísel mezi 1 a 49. Při modelování komplikovanějších procesů, které závisejí na časovém vývoji sledovaného systému, potřebujeme i složitější množinu Ω. Např. náhodný pohyb bodu ve čtverci C = ⟨0, 1⟩2 měřený v diskrétním čase je popsán posloupností (ωn )n∈N , kde ωn ∈ C. V tomto případě množina elementárních jevů Ω obsahuje všechny takové posloupnosti: Ω=

∞ ą

C.

i=1

V teorii informace často zpracováváme dlouhé řetězce symbolů ω1 ω2 . . . nad nějakou abecedou Λ. Množinu Ω pak můžeme ztotožnit s množinou všech posloupností Λ∞ (nekonečných řetězců) nad abecedou Λ: Λ∞ = { (ωn )n∈N | ωn ∈ Λ, n ∈ N } . (ii) Množinový systém A, který uchovává možné jevy v daném experimentu, tvoří tzv. σ-algebru podmnožin Ω. To znamená: 1

(a) A ⊆ 2Ω , kde 2Ω je množina všech podmnožin Ω; (b) ∅, Ω ∈ A; (c) pokud A ∈ A, potom A ∈ A; (d) pokud A1 , A2 , . . . ∈ A, potom

∪∞ n=1

An ∈ A.

Prvky A (jsou to množiny!) nazýváme jevy. Pokud je Ω konečná, obvyklou volbou σ-algebry je množina všech podmnožin Ω, tedy A = 2Ω . Složitější situace nastává nastává pro nekonečné Ω, jako je např. prostor posloupností Λ∞ . (iii) Pravděpodobnostní míra je zobrazení P : A → ⟨0, 1⟩ takové, že platí: (i) P (∅) = 0, P (Ω) = 1; (ii) jsou-li množiny A1 , A2 , . . . po dvou disjunktní (Ai ∩ Aj = ∅, pro i ̸= j), potom (∞ ) ∞ ∪ ∑ P An = P (An ). n=1

n=1

Podmínka (b) se nazývá σ-aditivita. Je nutné rozlišovat mezi pravděpodobností P (A) jevu A ∈ A a pravděpodobnostní mírou P : zatímco pravděpodobnost je číslo z intervalu ⟨0, 1⟩, pravděpodobnostní míra je funkce definovaná na celé σ-algebře A. Otázka, jak definovat míru P pro všechny jevy z A, je v teorii pravděpodobnosti klíčová. Jednoduchá je situace v případě konečné množiny elementárních jevů Ω, kterou si vždy můžeme představit jako Ω = {1, . . . , n}. Stačí totiž zadat n čísel p(i) ∈ ⟨0, 1⟩ takových, že p(1) + · · · + p(n) = 1. Každé p(i) prohlásíme za pravděpodobnost elementárního jevu i ∈ Ω a položíme ∑ P (A) = p(i), A ⊆ Ω. i∈A

Snadno lze ověřit, že P je pravděpodobnostní míra. Pro množinu všech posloupností Λ∞ však takový postup nelze použít: již v případě dvouprvkové množiny Λ totiž není Λ∞ spočetná, a proto nelze využít σaditivitu k definici P (A). Řešení si ukážeme v další části textu.

2

Definice 1.1 (Kolmogorov, 1933). Pravděpodobnostní prostor je trojice (Ω, A, P ), kde Ω je neprázdná množina, A je σ-algebra podmnožin Ω a P je pravděpodobnostní míra na A. Ukažme si příklady pravděpodobnostních prostorů důležitých v teorii informace. Ve všech níže uvedených příkladech chceme postihnout digitální procesy, které v diskrétním čase produkují symboly z nějaké konečné abecedy Λ. Podle druhu aplikace může být abeceda Λ např. • množina {0, 1}, • množina písmen anglické abecedy {a, . . . , z}, • množina symbolů vyjádřitelných ve standardu Unicode (UTF-8). Dále vždy mlčky předpokládáme, že Λ je konečná abeceda obsahující alespoň dva symboly. Popíšeme pravděpodobnostní prostory používané pro modelování náhodného výskytu (i) 1 znaku, (ii) řetězce pevné délky n, (iii) libovolně dlouhého řetězce. Příklad 1.1. Při modelování výskytu jediného znaku z abecedy Λ položíme Ω = Λ, A = 2Λ . Protože je Λ konečná, pravděpodobnostní míru P zadáme pomocí pravděpodobností p(ω) jednotlivých symbolů ω ∈ Λ, kde ∑ p(ω) ∈ ⟨0, 1⟩ a p(ω) = 1. ω∈Λ

Funkci p : Ω → ⟨0, 1⟩ říkáme pravděpodobnostní funkce nebo také pravděpodobnostní distribuce na Ω. Schéma uvedené v příkladu 1.1 umožňuje postihnout frekvenci výskytu jednotlivých symbolů1 v abecedě (např. pomocí statistického odhadu na základě dlouhého textu), ovšem neporadí si s frekvencemi řetězců délky větší než 1. 1

Z hlediska statistiky textů se jednotlivé symboly nazývají také unigramy.

3

Příklad 1.2. Model pro studium řetězců pevně zvolené délky n ∈ N je tento: Ω = Λn , A = 2 Ω . Jedná se o tzv. n-gramový model. Prvky Λn jsou, přísně vzato, uspořádáné n-tice (ω1 , . . . , ωn ). Níže však preferujeme zjednodušený zápis typický pro řetězce nad nějakou abecedou a píšeme tak ω1 . . . ωn místo (ω1 , . . . , ωn ). Složitost popisu pravděpodobností všech řetězců ω1 . . . ωn ∈ Λn roste exponenciálně s délkou n řetězce: je nutno určit všech |Λ|n pravděpodobností tvaru pn (ω1 . . . ωn ), abychom zadali pravděpodobnostní distribuci pn na Λn . Např. abecedu obsahující 30 symbolů to znamená zadat 304 = 810 000 pravděpodobností, pokud chceme modelovat pravděpodobnostní chování řetězců délky 4. Výpočetně nejjednodušší je přijetí předpokladu nezávislosti výskytu po sobě jdoucích znaků: n-gramový model je tak možné odvodit z pravděpodobností p1 (ωi ) jednotlivých unigramů ωi , neboť díky předpokladu musí platit pn (ω1 . . . ωn ) = p1 (ω1 ) · · · p1 (ωn ). To je zřejmě přílišné zjednodušení. Realističtější modely zahrnují závislost výskytu znaku ωi na předchozím znaku ωi−1 . Např. v průměrném anglickém textu je po písmenu t velmi pravděpodobný výskyt písmene h [3]. Příklad 1.3. Libovolně dlouhý řetězec lze modelovat pomocí nekonečné posloupnosti (ωi )i∈N = ω1 ω2 . . . symbolů z Λ. Budeme též používat značení ω1∞ místo (ωi )i∈N . Množina elementárních jevů je prostor všech posloupností ω1∞ , tedy Ω = Λ∞ . Jelikož je Ω je nekonečná nespočetná, nastává otázka ohledně volby vhodné σ-algebry podmnožin Λ∞ . Vezměme libovolné am , am+1 , . . . , an ∈ Λ, kde m, n ∈ N, m ≤ n, a položíme anm := am am+1 . . . an . Speciálně platí am m = am . Ukazuje se, že zásadní je umět změřit“ všechny ” jevy tvaru n [anm ] := {ω1∞ ∈ Λ∞ |ωm = anm } . Množina [anm ] se nazývá válec a je tvořena všemi nekonečnými řetězci n ωn+1 . . . , ω1 ω2 . . . ωm−1 ωm

které obsahují na pozicích m až n dané symboly am , am+1 , . . . , an ∈ Λ. Potom definujeme σ-algebru A∞ jako nejmenší σ-algebru, která obsahuje všechny 4

válce [anm ], kde m, n ∈ N, m ≤ n a am , am+1 , . . . , an ∈ Λ. To je korektní definice a A∞ nazýváme součinovou σ-algebrou. Tak už lze vyjádřit všechny prakticky zajímavé jevy (a mnohé další). Uveďme si některé příklady jevů patřících do A∞ : (i) [a31 ] jsou všechny posloupnosti znaků začínající daným řetězcem a1 a2 a3 ; ∪ (ii) ∞ n=1 [a2n ], kde a2n := a ∈ Λ pro každé n ∈ N, vybere všechny posloupnosti obsahující na některé sudé pozici daný symbol a ∈ Λ; ∩∞ n ∞ ∞ (iii) i=1 [a1 ] = [a1 ] ∩ [a21 ] ∩ · · · = {a∞ 1 }, kde a1 ∈ Λ , průnik válců tak ∞ obsahuje pouze zadaný nekonečný řetězec a1 . Povšimněme si, že válec [an1 ] ∈ A∞ , který tvoří nekonečné sekvence začínající řetězcem an1 , lze ztotožnit se samotným řetězcem pevné délky an1 ∈ Λn . Takovým konečným řetězcům však umíme přiřadit pravděpodobnost (viz Příklad 1.2) pomocí pravděpodobnostní distribuce pn na Λn . Ukazuje se, že pokud konzistentně“ přiřadíme pravděpodobnostní distribuce nad řetězci an1 ” všech možných délek n ∈ N, stačí to již k zadání pravděpodobnostní míry P na A. O tom hovoří následující věta. Věta 1.1. Nechť p1 , p2 , . . . je posloupnost pravděpodobnostních distribucí definovaných na množinách Λ, Λ2 , . . . , přičemž platí podmínka konzistence, tj. ∑ pn (an1 ) = pn+1 (an1 an+1 ), n ∈ N, an1 ∈ Λn . (1) an+1 ∈Λ

Potom existuje jediná pravděpodobnostní míra P na A∞ taková, že platí P ([an1 ]) = pn (an1 ),

n ∈ N, an1 ∈ Λn .

Problém specifikace pravděpodobnostní míry P pro prostor posloupností Λ je tím vyřešen. Poznamenejme, že podmínka konzistence je naprosto přirozená. Např. pro Λ = {0, 1} vezměme tuto pravděpodobnostní distribuci na bitových řetězcích délky 2: ∞

p2 (00) = 0.2, p2 (01) = 0.1, p2 (10) = 0.3, p2 (11) = 0.4. Jaká je pravděpodobnost pozorování jediného bitu? Zřejmě čekáme p1 (0) = p2 (00) + p2 (01) = 0.3

a p1 (1) = p2 (10) + p2 (11) = 0.7. 5

Přesně to však říká podmínka (1). Podobnou úvahu lze provést i pro jiné délky řetězců. Jaké pravděpodobnostní míry P se vyskytují v aplikacích při práci s pravděpodobnostním prostorem (Λ∞ , A∞ , P )? Rozeberme si dva základní modely. Příklad 1.4 (Bernoulliho model.). Jedná se o nejjednodušší model genero∞ vání řetězce a∞ 1 ∈ Λ . Předpokládáme, že výskyty jednotlivých symbolů v řetězci jsou nezávislé. To je velmi silný předpoklad. Jak specifikujeme Bernoulliho model pomocí Věty 1.1? Nechť p(a) jsou pravděpodobnosti jednotlivých symbolů a ∈ Λ. Definujme pravděpodobnost řetězce an1 ∈ Λn jako pn (an1 ) = p(a1 )p(a2 ) · · · p(an ),

pro každé n ∈ N.

Podmínka (1) platí: ∑

pn+1 (an1 an+1 )

an+1 ∈Λ

∑ n+1 ∏

=

p(ai ) =

an+1 ∈Λ i=1

n ∏

∑

p(ai )

i=1

p(an+1 ) = pn (an1 ).

an+1 ∈Λ

|

{z

}

1

Podle Věty 1.1 tak máme jednoznačně zadánu míru P na σ-algebře A∞ . Pro zajímavost určeme pravděpodobnost libovolného elementárního jevu, ∞ řetězce a∞ 1 ∈ Λ . Předpokládejme, že každý symbol a ∈ Λ má pravděpodob1 2 nost p(a) < 1. Vzpomeňme si, že jev {a∞ 1 } lze vyjádřit jako [a1 ] ∩ [a1 ] ∩ · · · , přičemž platí [a11 ] ⊇ [a21 ] ⊇ · · · . Proto lze psát P ({a∞ 1 })

= lim

n→∞

P ([an1 ])

= lim

n→∞

pn (an1 )

= lim

n→∞

n ∏

p(ai ) = 0.

i=1

Všechny elementární jevy a∞ 1 tak mají nulovou pravděpodobnost! V tomto bodě znovu vidíme, že pravděpodobnostní míru P na A∞ nelze specifikovat pomocí hodnot pravděpodobnosti pro a∞ 1 . Východisko nabízí právě věta 1.1. Stojí za poznámku, že situace není nepodobná práci s pravděpodobnostní mírou na množině elementárních jevů Ω′ = ⟨0, 1⟩, neboť ani zde si nevystačíme s pravděpodobnostmi čísel x ∈ Ω′ .2 Nabízí se následující analogie: nekonečně 2

Nevyjádřili bychom tak základní spojité modely, jako je např. rovnoměrné rozdělení, kterým se řídí náhodný výběr čísla z Ω′ . Pro něj to totiž platí P ({x}) = 0, pro každé x ∈ Ω′ .

6

∞ dlouhý pokus (generování náhodného řetězce a∞ 1 ∈ Λ ) si lze představit též jako nekonečně jemný pokus (náhodný výběr čísla x ∈ Ω′ ). To lze snadno ukázat pro abecedu Λ = {0, 1} pomocí dvojkového rozvoje čísla x ∈ Ω′ .

Příklad 1.5 (Markovský model.). Studujme přirozené zobecnění Bernoulliho modelu: připustíme, že výskyt symbolu ai v řetězci na pozici i je ovlivněn výskytem předchozího symbolu ai−1 . Pravděpodobnosti popisující závislosti mezi všemi dvojicemi symbolů a, b ∈ Λ zachytíme pomocí stochastické matice P = (pab )a,b∈Λ . Složky matice jsou podmíněné pravděpodobnosti pab výskytu znaku b po znaku a, proto požadujeme ∑ pab = 1. b∈Λ

Podobně jako u Bernoulliho modelu musíme dále zadat (nepodmíněné) pravděpodobnosti pa symbolů a ∈ Λ. Spočtěme pravděpodobnostní distribuce pn pro řetězce délek 1, 2, . . . , n, tak, jak mohou být postupně generovány pro libovolné n ∈ N: p1 (a) = pa , a ∈ Λ, p2 (a1 a2 ) = pa1 pa1 a2 , a1 a2 ∈ Λ2 , .. . n pn (a1 ) = pa1 pa1 a2 · · · pan−2 an−1 pan−1 an , an1 ∈ Λn . {z } | pn−1 (an−1 ) 1

I nyní snadno nahlédneme, že podmínka konzistence (1) je splněna: ∑ ∑ ∑ pn+1 (an1 an+1 ) = pn (an1 )pan an+1 = pn (an1 ) pan an+1 . an+1 ∈Λ

an+1 ∈Λ

an+1 ∈Λ

|

{z

}

1

Podle Věty 1.1 tak vidíme, že markovský model nad abecedou Λ je již zadán stochastickou maticí řádu |Λ| a pravděpodobnostní distribucí na Λ.

2

Náhodná veličina

Pravděpodobnostní prostor (Ω, A, P ) je sice základním objektem teorie pravděpodobnosti, ovšem naše znalosti a výroky o modelovaném systému vyjadřujeme spíše pomocí náhodných veličin. Podívejme se na některé příklady: 7

(i) Při 10 opakováních hodu symetrickou kostkou nás zajímá, jaká je pravděpodobnost, že maximum z výsledků bylo 4. Obecněji můžeme chtít stanovit pravděpodobnost, že maximum dosahuje hodnoty k = 1, . . . , 6. (ii) Náhodný generátor bitů produkuje řetězce an1 délky n, kde ai ∈ {0, 1}. Bity jsou zapisovány nezávisle, jednotkový bit má pravděpodobnost výskytu p ∈ ⟨0, 1⟩. Jaká je pravděpodobnost, že se v takto náhodně vygenerovaném řetězci vyskytne právě k = 0, . . . , n jednotkových bitů? (iii) Mějme stejné zařízení jako v (ii) s tím rozdílem, že náhodně generované řetězce mohou být libovolné délky. Jelikož neexistuje omezení na délku řetězce, vhodným modelem je zde prostor všech bitových posloupností Λ∞ , kde Λ = {0, 1}. Zajímá nás hodnota bitu na pozici 512. Před zodpovězením uvedených otázek si zopakujme pojem náhodné veličiny [1]. Podstatou tohoto pojmu je zobrazení množiny elementárních jevů Ω do množiny hodnot R, která reprezentují měření. Dále požadujeme, aby všechny množiny hodnot měření, které lze uvažovat, tvořily σ-algebru B podmnožin množiny R. Definice 2.1. Nechť (Ω, A, P ) je pravděpodobnostní prostor, R je libovolná neprázdná množina a B je σ-algebra jejích podmnožin. Náhodná veličina je zobrazení X : Ω → R, které je měřitelné, tj. pro každé B ∈ B platí [X ∈ B] := { ω ∈ Ω | X(ω) ∈ B } ∈ A. Podmínka měřitelnosti zajišťuje, že všechny podstatné množiny hodnot náhodné veličiny X (jsou to množiny B ∈ B) odpovídají jevům ze σ-algebry A. Pro nejjednodušší pravděpodobnostní modely v teorii informace je podmínka měřitelnosti automaticky splněna: pokud je Ω konečná, R = Λ je konečná abeceda, potom klademe A = 2Ω , B = 2Λ , a každá funkce X : Ω → Λ je tak náhodná veličina. To platí, neboť A musí obsahovat z definice všechny jevy [X ∈ B]. Měřitelnost vstupuje do našich úvah výrazně až v případě nekonečné množiny Ω nebo když je obor hodnot R náhodné veličiny množina reálných čísel R. Uvedená problematika spadá do pokročilého kursu matematické analýzy, zejména do partie známé jako teorie míry. Pro základní orientaci a seznam vhodné literatury doporučujeme čtenáři skriptum [1]. 8

Jak výstižně poznamenal slavný matematik G.-C. Rota, náhodná veli” čina není ani náhodná, ani veličina.“ Název zde vyjadřuje úzké sepjetí náhodné veličiny X (funkce na množině elementárních jevů) s pravděpodobnostní mírou na oboru hodnot X: každý jev B ∈ B má totiž přiřazenu pravděpodobnost P [X ∈ B] pomocí interpretace jevu [X ∈ B] v σ-algebře A, neboli P [X ∈ B] := P ({ ω ∈ Ω | X(ω) ∈ B }). Používáme také ekvivalentní značení PX (B) := P [X ∈ B],

(2)

což nám umožňuje mluvit o funkci PX : B → ⟨0, 1⟩ definované skrze (2). Lze snadno ověřit, že PX je pravděpodobnostní míra na σ-algebře B. Říkáme, že PX je pravděpodobnostní rozdělení náhodné veličiny X na množině R. Pravděpodobnostní rozdělení PX specifikuje pravděpodobnost pro množiny hodnot náhodné veličiny X a umožňuje tak zkonstruovat nový pravděpodobnostní prostor, který popisuje transformaci zprostředkovanou zobrazením X. Tím jsme vlastně dokázali následující tvrzení. Tvrzení 2.1. Nechť X je náhodná veličina na pravděpodobnostním prostoru (Ω, A, P ) s hodnotami v R. Potom je trojice (R, B, PX ) pravděpodobnostní prostor. Ilustrujme si obsah pojmu náhodné veličiny na řešení otázek (i)–(iii) formulovaných na začátku této kapitoly. Příklad 2.1. V situaci (i) je zřejmě množina elementárních jevů Ω = {1, . . . , 6}10 a proto uvažujeme σ-algebru A = 2Ω . Pravděpodobnost každého elementárního jevu je 6110 , neboť |Ω| = 610 . Zajímá nás maximum z (ω1 , . . . , ω10 ) ∈ Ω, což vede na náhodnou veličinu X(ω1 , . . . , ω10 ) := max ωi i=1,...,10

s hodnotami v množině R = {1, . . . , 6}. Jaké je pravděpodobnostní rozdělení PX náhodné veličiny X? Protože je R konečná, stačí určit pravděpodobnosti 9

P [X = k] pro k = 1, . . . , 6. K jejich stanovení je nutné pochopit povahu jevů [X = k]. Podmínku X = k je totiž možné vyjádřit ekvivalentně jako tvrzení v uspořádané 10-tici (ω1 , . . . , ω10 ) je každé ωi menší nebo rovno ” než k, přičemž existuje ωj , které je rovno k“. Potom už snadno stanovíme pravděpodobnostní rozdělení veličiny X: P [X = k] =

k 10 − (k − 1)10 , 610

k = 1, . . . , 6.

Tím jsme určili pravděpodobnosti všech možných maxim výsledků při 10násobném hodu kostkou. Příklad 2.2. Čtenář znalý základního kursu teorie pravděpodobnosti rozpozná v (ii) tzv. binomické rozdělení. Jak však vypadá náhodná veličina, jejíž rozdělení je binomické? Prostor elementárních jevů je nyní Ω = {0, 1}n , σalgebra A je samozřejmě 2Ω . Pravděpodobnost elementárního jevu an1 ∈ Ω závisí na počtu jednotkových bitů v tomto řetězci. Pokud obsahuje an1 právě k jednotkových bitů, potom zřejmě P ({an1 }) = pk (1 − p)n−k ,

(3)

kde p je pravděpodobnost výskytu jednotkového bitu. Chceme definovat náhodnou veličinu, která bude počítat jednotkové bity v řetězci an1 . To je snadné, stačí položit n ∑ n X(a1 ) := ai . i=1

Protože obor hodnot X je konečný, s měřitelností opět nejsou žádné problémy. Pravděpodobnostní rozdělení veličiny X (binomické rozdělení) dostaneme, pokud si uvědomíme, že jev [X = k] referuje ke všem řetězcům bitů an1 obsahujícím právě k jednotkových bitů. Z (3) potom plyne ( ) n k P [X = k] = p (1 − p)n−k , k = 0, . . . , n. k Příklad 2.3. Z příkladu 1.3 již víme, že modelem pro (iii) je pravděpodobnostní prostor (Λ∞ , A∞ , P ), kde Λ∞ = {0, 1}∞ , A je součinová σ-algebra a P je pravděpodobnostní míra odpovídající Bernoulliho modelu. Jak zjistíme hodnotu X512 bitu na pozici 512 v libovolném náhodně generovaném řetězci

10

∞ a∞ 1 ∈ Λ ? Jednoduše odečteme odpovídající bit z celého vstupního řetězce a proto stačí uvažovat náhodnou veličinu ∞ X512 (a511 1 a512 a513 ) := a512

(4)

definovanou na (Λ∞ , A∞ , P ) s hodnotami v {0, 1}. Ani v této situaci nejsou s měřitelností funkce X512 žádné problémy. Definiční obor náhodné veličiny je nyní sice nekonečná množina Λ∞ , ale X512 může nabývat pouze dvou různých hodnot. Stačí tedy ověřit, že jevy [X512 = 0] a [X512 = 1] patří do součinové σ-algebry A. To je však triviálně splněno: první jev odpovídá válci [a512 ] pro a512 = 0, druhý válci [a512 ] pro a512 = 1, a oba jevy tak patří do A∞ (viz příklad 1.3). Proto lze mluvit o pravděpodobnostech P [X512 = 0] a P [X512 = 1]. Podobně lze odečíst hodnotu bitu na libovolné pozici k ∈ N a tím bychom dostali náhodnou veličinu Xk definovanou analogicky jako v (4). Lze tak uvažovat konečné i nekonečné posloupnosti náhodných veličin spolu s jejich rozdělením. Více bude uvedeno v částech 3 a 4. Z uvedených příkladů bylo vidět, že povaha pravděpodobnostního prostoru (Ω, A, P ), na němž je náhodná veličina X definována, není rozhodující. Charakteristiky modelu jsou totiž určeny výhradně pravděpodobnostním rozdělením PX ! Jelikož známe celou řadu pravděpodobnostních měr a rozdělení (binomické, Poissonovo, normální atd.), nabízí se obrácený způsob konstrukce modelu: k zadanému pravděpodobnostnímu prostoru (R, B, P ) hodnot měření nalezneme náhodnou veličinu X, pro jejíž rozdělení PX platí PX = P . To je ovšem snadné, stačí totiž uvažovat pravděpodobnostní prostor (Ω, A, P ), kde Ω = R, A = B a náhodnou veličinu X : Ω → Ω definovanou jako identitu, X(ω) := ω pro každé ω ∈ Ω. Tím máme zajištěno, že v pojmech náhodných veličin a jejich rozděleních vyjádříme stejná fakta o daném modelu jako v řeči původního pravděpodobnostního prostoru. Naše vyjadřování to však velmi usnadňuje, neboť pojem měření a jeho výsledků je v inženýrské teorii i praxi bytostně spjat s pojmem veličiny, jejíž hodnoty měříme. Při modelování digitální informace bývá obvyklé uvažovat náhodnou veličinu X s hodnotami v konečné abecedě Λ. To nám usnadňuje popis pravděpodobnostního rozdělení PX , které je určeno pravděpodobnostní distribucí pX náhodné veličiny X, což je funkce Λ → ⟨0, 1⟩ definovaná jako pX (a) := P [X = a], 11

a ∈ Λ.

Takový způsob popisu rozdělení náhodné veličiny X bylo možno pozorovat již v příkladech 2.1–2.3.

3

Náhodný vektor

Definice 3.1. Náhodný vektor je n-tice náhodných veličin (X1 , . . . , Xn ) definovaných na společném pravděpodobnostním prostoru (Ω, A, P ). V teorii informace budeme obvykle uvažovat konečnou abecedu Λ jako společný obor hodnot pro všechny náhodné veličinu Xi , kde i = 1, . . . , n. Tím modelujeme náhodný výskyt řetězců an1 ∈ Λn pevné délky n nad abecedou Λ (viz příklad 1.2). Náhodný vektor tak lze chápat jako n-rozměrnou náhodnou veličinu s hodnotami v Λn , (X1 , . . . , Xn ) : Ω → Λn . Stejně jako u jedné náhodné veličiny Xi : Ω → Λ, ani zde nebývá problém n s měřitelností (Definice 2.1): Λn je konečná, klademe B = 2Λ , a proto stačí ověřit, že pro každé an1 ∈ Λn platí [X1 = a1 , . . . , Xn = an ] := { ω ∈ Ω | X1 (ω) = a1 , . . . , Xn (ω) = an } ∈ A. (5) Příklad 3.1 (pokračování příkladu 2.3). Uvažujeme opět model generování libovolně dlouhých bitových řetězců. Nyní chceme zaznamenat hodnotu prv∞ ních n bitů v libovolném řetězci a∞ 1 ∈ Λ . Tak dostaneme n-rozměrný náhodný vektor (X1 , . . . , Xn ) definovaný jako (X1 , . . . , Xn )(an1 an+1 . . .) := an1 ,

an1 ∈ Λ∞ .

Podmínka (5) je splněna, protože [X1 = a1 , . . . , Xn = an ] = [a1 ] ∩ · · · ∩ [an ] = [an1 ] ∈ A∞ , kde A∞ je součinová σ-algebra na Λ∞ . V dalších odstavcích budeme používat následující zjednodušené značení. Protože náhodný vektor (X1 , . . . , Xn ) si lze představit jako model pro náhodně generovaný řetězec nad abecedou Λ, budeme též psát X1 . . . Xn místo 12

(X1 , . . . , Xn ). Libovolný podřetězec Xi Xi+1 . . . Xk−1 Xk vybraný z X1 . . . Xn , kde 1 ≤ i ≤ k ≤ n, budeme značit jako Xik . Např. X25 = X2 X3 X4 X5 , X1n = X1 . . . Xn , X33 = X3 . Pro náhodný vektor X1n definujeme podobné pojmy jako v případě jedné náhodné veličiny X. Simultánní výskyt hodnot X1n popíšeme sdruženým (nrozměrným) pravděpodobnostním rozdělením, které lze v případě konečné abecedy Λ jednoznačně určit pravděpodobnostmi všech řetězců an1 ∈ Λn . Sdružená pravděpodobnostní distribuce náhodného vektoru X1n je funkce pX1n : Λn → ⟨0, 1⟩ definovaná takto: pX1n (an1 ) := P [X1n = an1 ] = P [X1 = a1 , . . . , Xn = an ],

an1 ∈ Λn .

(6)

Podobně můžeme uvažovat pravděpodobnostní distribuci libovolného náhodného vektoru Xi1 . . . Xik vybraného z X1n , kde i1 , . . . , ik ∈ {1, . . . , n}: pXi1 ...Xik (ai1 , . . . , aik ) := P [Xi1 = ai1 , . . . , Xik = aik ],

ai1 , . . . , aik ∈ Λ. (7)

Pravděpodobnostní distribuce pXi1 ...Xik definovaná v (7) se nazývá marginální pravděpodobnostní distribuce, neboť určuje pravděpodobnostní rozdělení pouze části původního náhodného vektoru X1n . Speciálně, rozdělení každé náhodné veličiny Xi je určeno (1-rozměrnou) marginální pravděpodobnostní distribucí pXi na Λ. Marginální pravděpodobnostní distribuci (7) lze spočítat ze sdružené distribuce (6): ∑ pX1n (an1 ), kde J = {1, . . . , n} \ {i1 , . . . , ik }. pXi1 ...Xik (ai1 , . . . , aik ) = (aj )j∈J ∈Λ|J|

(8) Čtenář může vzorec (8) chápat tak, že součet probíhá přes všechny hodnoty náhodných veličin z X1n kromě Xi1 . . . Xik . Ukažme si výpočet marginálního rozdělení na příkladě.

13

X3 = 0 X3 = 1

X1 = 0 X2 = 0  X2 = 1 0.05 0 0.30 0.20

X1 = 1 X2 = 0  X2 = 1 0.15 0.10 0.10 0.10

Tabulka 1: Hodnoty sdružené distribuce pX13 Příklad 3.2. Náhodný vektor X13 s hodnotami v {0, 1}3 má sdružené rozdělení zachycené v tabulce 1. Z ní snadno vyčteme, že např. pX13 (100) = 0.15. Jak určíme marginální rozdělení pX2 X3 ? Podle vzorce (8) platí ∑ pX2 X3 (a2 a3 ) = pX13 (a1 a2 a3 ) a1 ∈{0,1}

pro každé a2 a3 ∈ {0, 1}2 . Pro a2 a3 = 01 dostaneme pX2 X3 (01) = pX13 (001) + pX13 (101) = 0.30 + 0.10 = 0.40. Podobně pro ostatní řetězce a2 a3 a tak dostaneme tabulku 2 popisující hodnoty marginální pravděpodobnostní distribuce pX2 X3 . Analogicky můžeme X3 = 0 X3 = 1

X2 = 0 0.20 0.40

 X2 = 1 0.10 0.30

Tabulka 2: Hodnoty marginální distribuce pX2 X3 dopočítat zbylé marginální distribuce: dvě 2-rozměrné (pX1 X2 a pX1 X3 ) a tři 1-rozměrné (pX1 , pX2 a pX3 ). Sdružené rozdělení jednoznačně určuje všechna marginální rozdělení složek náhodného vektoru X1n . Ovšem pozor—obráceně to neplatí! Např. znalost 2-rozměrných rozdělení X1 X2 , X1 X3 a X2 X3 nám v příkladě 3.2 bez dodatečných předpokladů neumožňuje jednoznačně zrekonstruovat sdružené rozdělení vektoru X1 X2 X3 .3 Předpokladem umožňujícím popsat sdružené rozdělení vektoru X1n pomocí jednotlivých marginálních rozdělení veličin Xi je nezávislost složek vektoru. 3

Na tento fakt lze nahlížet i pomocí geometrické analogie. Pro 2 náhodné veličiny si představme kruh v rovině a jeho průměty na obě souřadné osy. Vzniknou tak 2 úsečky, které však neurčují jednoznačně původní útvar, jehož jsou průmětem.

14

Definice 3.2. Nechť X1n je náhodný vektor. Náhodné veličiny X1 , . . . , Xn nazveme nezávislé, pokud platí pX1n (an1 ) = pX1 (a1 ) · · · pXn (an ),

an1 ∈ Λn .

(9)

Ihned vidíme, že náhodné veličiny X1 , X2 a X3 z příkladu 3.2 nejsou nezávislé, jelikož (9) neplatí: 0 = pX13 (010) ̸= pX1 (0)pX2 (1)pX3 (0) = 0.55 · 0.40 · 0.30 = 0.066. Náhodný vektor s nezávislými složkami odpovídá Bernoulliho modelu (příklad 1.4.) Podívejme se, jak vypadá model pro bitové řetězce a31 ∈ {0, 1}3 délky 3, které vzniknou náhodným generováním bitů s danou pravděpodobností jednotkového bitu p ∈ ⟨0, 1⟩. Příklad 3.3 (3-rozměrný náhodný vektor s nezávislými složkami). Uvažujme náhodné veličiny X1 , X2 a X3 s pravděpodobnostními distribucemi pXi (1) = p, pXi (0) = 1 − p,

i = 1, 2, 3,

kde p ∈ ⟨0, 1⟩. Sdruženou pravděpodobnostní distribuci pX13 náhodného vektoru X13 definujeme pomocí (9)—pravděpodobnostní distribuce pX13 je součinem tří 1-rozměrných pravděpodobnostních distribucí pXi , pX13 (a31 ) = pX1 (a1 )pX2 (a2 )pX3 (a3 ),

a31 ∈ {0, 1}3 .

Výsledek vidíme v tabulce 3.

X3 = 0 X3 = 1

X1 = 0 X1 = 1 X2 = 0  X2 = 1 X2 = 0  X2 = 1 3 2 2 (1 − p) p(1 − p) p(1 − p) p2 (1 − p) 2 p(1 − p) p2 (1 − p) p2 (1 − p) p3

Tabulka 3: Hodnoty pX13 pro nezávislé veličiny X1 , X2 a X3

Nezávislost nám umožňuje výraznou redukci paměťové režie při vyjádření pravděpodobnostní distribuce pX1n . Již pro dvouprvkovou abecedu Λ totiž potřebujeme 2n pravděpodobností typu pX1n (an1 ). Pokud jsou však veličiny nezávislé, což často předpokládáme, potom je paměťová složitost lineární v 15

počtu veličin n. V příkladu 3.3 je situace ještě jednodušší, jelikož všechny náhodné veličiny Xi mají stejné rozdělení pXi určené jedinou hodnotou pravděpodobnosti p. Z úvodního kursu pravděpodobnosti víme, že vliv hodnot veličiny Xj na jinou veličiny Xi vyjádříme pomocí podmíněné pravděpodobnosti. Připoměňme si tento pojem. Definice 3.3. Mějme náhodný vektor X12 , kde X1 a X2 nabývá hodnot v konečné abecedě Λ. Podmíněná pravděpodobnostní distribuce veličiny X2 za podmínky X1 je funkce pX2 |X1 : Λ2 → ⟨0, 1⟩ definovaná jako pX2 |X1 (a2 |a1 ) :=

pX12 (a21 ) , pX1 (a1 )

a1 , a2 ∈ Λ, pX1 (a1 ) ̸= 0.

(10)

V případě pX1 (a1 ) = 0 hodnotu pX2 |X1 (a2 |a1 ) nedefinujeme. Povšimněme si, že pro dané a1 ∈ Λ splňující pX1 (a1 ) > 0 je funkce jedné proměnné pX2 |X1 (.|a1 ) : Λ → ⟨0, 1⟩ vlastně pravděpodobnostní distribuce náhodné veličiny X2 , jelikož ∑ pX12 (a1 a2 ) ∑ pX (a1 ) a2 ∈Λ = 1 = 1. pX2 |X1 (a2 |a1 ) = p p X1 (a1 ) X1 (a1 ) a ∈Λ 2

Vzorcem podobným (10) je možné definovat podmíněnou pravděpodobnostní distribuci libovolného náhodného vektoru (Xj )j∈J za podmínky dané jiným náhodným vektorem (Xi )i∈I , přičemž I ∩ J = ∅. Přibližme si to na příkladě. Příklad 3.4 (pokračování příkladu 3.2). Hledejme podmíněnou pravděpodobnostní distribuci pX1 X3 |X2 . Pro názornost budeme všechny výsledky zaokrouhlovat pouze na 2 desetinná místa. Zřejmě pX1 X3 |X2 (00|0) =

pX13 (000) 0.05 . = = 0.08. pX2 (0) 0.60

Podobně postupujeme pro další kombinace hodnot až dostaneme tabulku 4 podmíněných pravděpodobností. V tabulce 4 jsou oba řádkové součty rovny 16

X2 = 0 X2 = 1

X1 = 0 X3 = 0  X3 = 1 0.08 0.50 0 0.50

X1 = 1 X3 = 0  X3 = 1 0.25 0.17 0.25 0.25

Tabulka 4: Hodnoty podmíněné pravděpodobnostní distribuce pX1 X3 |X2

jedné, neboť první řádek obsahuje pravděpodobnostní distribuci pX1 X3 |X2 (.|0) a druhý obsahuje pX1 X3 |X2 (.|1). Povšimněme si, že pX1 X3 |X2 (.|0) ̸= pX1 X3 |X2 (.|1) (tabulka má různé řádky). To znamená, že výskyt prostředního bitu X2 ovlivňuje náhodný výskyt bitů X1 a X3 . To jen dále dokumentuje naše dřívější pozorování, že bity v řetězci X1 X2 X3 nejsou nezávislé. Nezávislost náhodných veličin X1 a X2 můžeme ekvivalentně popsat pomocí podmíněné pravděpodobnosti. Důkaz následujícího trvzení je bezprostředním důsledkem definice nezávislosti (definice 3.2) a podmíněné pravděpodobnostní distribuce (definice 3.3). Tvrzení 3.1. Mějme náhodné veličiny X1 a X2 takové, že pX2 (a2 ) > 0, pro každé a2 ∈ Λ. Veličiny X1 a X2 jsou nezávislé právě tehdy, když pX2 |X1 (a2 |a1 ) = pX2 (a2 ),

pro každé a1 , a2 ∈ Λ.

Příklad 3.5 (pokračování příkladu 3.3). Veličiny X1 , X2 a X3 jsou z definice nezávislé. Jak vypadá např. podmíněná pravděpodobnostní distribuce pX1 |X2 ? Předpokládejme 0 < pX2 (1) < 1. Platí pX1 |X2 (a1 |a2 ) =

pX12 (a21 ) pX (a1 )pX2 (a2 ) = 1 = pX1 (a1 ), pX2 (a2 ) pX2 (a2 )

pro každé a1 , a2 ∈ {0, 1}. Z toho plyne, že veličiny X1 a X2 jsou nezávislé, jak jsme očekávali. Podobně lze nezávislost ověřit i pro zbývající páry veličiny, X1 X3 a X2 X3 . Závěrem si uveďme užitečný vztah, který ihned plyne z definice podmíněné distribuce. Bayesův vzorec pro náhodné veličiny X1 a X2 říká, že pX |X (a2 |a1 )pX1 (a1 ) pX1 |X2 (a1 |a2 ) = ∑ 2 1 , pX2 |X1 (a2 |a′1 )pX1 (a′1 ) a′1 ∈Λ

17

a1 , a2 ∈ Λ,

(11)

kdykoli jsou uvedené podmíněné pravděpodobnosti definovány. V čitateli zlomku (11) je zřejmě hodnota marginální pravděpodobnostní distribuce pX2 pro a2 , neboli pravděpodobnost pX2 (a2 ).

4

Náhodný proces

V teorii informace slouží pojem náhodného procesu nad danou abecedou Λ ∞ k zachycení modelu náhodného řetězce libovolné délky a∞ 1 ∈ Λ , se kterým jsme se setkali již v příkladě 1.3. Na náhodný proces lze nahlížet jako na informační zdroj, který je schopen produkovat nekonečné řetězce symbolů. V daném okamžiku n ∈ N zapíše zdroj na pozici n náhodný symbol Xn , v další iteraci provede to samé na pozici n + 1 a tento postup pokračuje do nekonečna. Nekonečné řetězce se sice prakticky nevyskytují, přesto lze tento model přijmout, neboť (i) běžně se vyskytující řetězce mají délku, kterou již považujeme za dostatečně velkou; (ii) je důležité předem neomezovat délku náhodného řetězce na pevnou hodnotu n a připustit tak prakticky libovolnou délku. Definice 4.1. Náhodný proces (s diskrétním časem, nad konečnou abecedou Λ) je posloupnost náhodných veličin (Xn )n∈N definovaných na společném pravděpodobnostním prostoru (Ω, A, P ) a nabývajících hodnot v množině Λ. Místo (Xn )n∈N budeme rovněž psát X1∞ . Pro každé n ∈ N můžeme mluvit o n-rozměrném rozdělení procesu X1∞ , které definujeme jako n-rozměrné rozdělení náhodného vektoru X1n . Jak víme, to lze charakterizovat pomocí pravděpodobnostní distribuce pX1n na Λn : pX1n (an1 ) = P [X1n = an1 ],

an1 ∈ Λn .

(12)

Rozdělením procesu X1∞ nazveme posloupnost (pX1n )n∈N pravděpodobnostních distribucí (12). Povšimněme si, že rozdělení procesu (pX1n )n∈N splňuje podmínku konzistence (1), neboť pX1n je marginální pravděpodobnostní distribucí pro náhodný vektor X1n+1 . To nás přivádí na obrácený postup: k zadané posloupnosti pravděpodobnostních distribucí p1 , p2 , . . . definovaných na množinách Λ, Λ2 , . . .

18

a splňujících konzistenci (1) se pokusme nalézt pravděpodobnostní prostor ˆ 1∞ na (Ω, A, P ) takový, že (Ω, A, P ) a náhodný proces X pXˆ1n = pn ,

pro každé n ∈ N.

(13)

ˆ ∞ má rozdělení, které odPodmínka (13) říká, že nově definovaný proces X 1 povídá zadanému konzistentnímu systému (pn )n∈N . Návod ke konstrukci nám dává věta 1.1—položme Ω := Λ∞ , A := A∞ , P := jednoznačně určená pravděpodobnostní míra z věty 1.1. ˆ ∞ na (Λ∞ , A∞ , P ) definujeme jako projekci do n-té souNáhodný proces X 1 řadnice: ˆ n (a∞ ) := an , X 1

∞ pro každé n ∈ N a každé a∞ 1 ∈ Λ .

(14)

ˆ n je zřejmě měřitelná vůči součinové σ-algebře A∞ a proKaždá veličina X ˆ ∞ , který nazveme souřadnicovým procesem, je tak dobře definován. ces X 1 ˆ ∞ splňuje (13). Volme an ∈ Λn libovolně. Ověřme, že souřadnicový proces X 1 1 Potom ˆ 1n = an1 ] = P ([an1 ]) = pn (an1 ), pXˆ1n (an1 ) = P [X kde druhá rovnost je důsledkem definice (14) a třetí plyne z věty 1.1. Dokázali jsme vlastně následující důležitou větu. Věta 4.1 (Kolmogorovova reprezentace procesu). Nechť X1∞ je náhodný proˆ ∞ na ces nad konečnou abecedou Λ. Potom existuje souřadnicový proces X 1 pravděpodobnostním prostoru (Λ∞ , A∞ , P ), který má stejné rozdělení jako původní proces X1∞ . Kolmogorovova reprezentace umožňuje na každý proces X1∞ nahlížet jako na postupné generování náhodného řetězce z množiny Λ∞ pomocí souřadˆ ∞ . S takovou představou o náhodném procesu jsme se nicového procesu X 1 ostatně seznámili již na začátku části 4. Zároveň nám věta 4.1 dává univerzální pravděpodobnostní prostor (Λ∞ , A∞ , P ), v němž lze přirozeně mluvit o pravděpodobnosti P (A) různých množin řetězců A ∈ A∞ . Podívejme se na důležité příklady náhodných procesů, se kterými se setkáváme v teorii informace. 19

Příklad 4.1 (Generování nezávislých bitů). Bernoulliho proces je náhodný proces X1∞ nad abecedou Λ = {0, 1}, přičemž náhodné veličiny X1 , X2 , . . . jsou nezávislé4 a platí pXn (1) = p ∈ ⟨0, 1⟩, pro každé n ∈ N. Na uvedený model jsme již narazili v příkladu 1.4. Pro každé n ∈ N vypadá n-rozměrné rozdělení Bernoulliho procesu takto:

kde suma

∑n

pX1n (an1 ) = p

i=1

∑n i=1

ai

(1 − p)n−

∑n i=1

ai

,

an1 ∈ Λn ,

(15)

ai v exponentu značí počet jednotkových bitů v řetězci an1 .

Představme si na okamžik, že pravděpodobnost p = pXn (1) je v Bernoulliho procesu neznámá. Máme všek k dispozici dostatečně rozsáhlý náhodný výběr5 v podobě dlouhého řetězce bitů X1n . Jak odhadneme neznámou pravděpodobnost p? Čtenář znalý základů matematické statistiky prohlásí za vhodný odhad výběrový průměr pozorování X n , kde X n :=

X1 + · · · + Xn . n

Intuice napovídá, že pro n → ∞ by měla růst kvalita odhadu pomocí X n . Pro konkrétní pozorovaný řetězec an1 tudíž očekáváme, že rozdíl mezi průměrem n a neznámou hodnotou p bude zanedbatelný, kdykoli n pozorování a1 +···+a n bude dostatečné velké. Přesnou formulaci poskytuje následující věta, známá jako (Borelův) silný zákon velkých čísel. Silný zákon velkých čísel (Borel, 1909). Nechť X1∞ je Bernoulliho proces, kde pXn (1) = p ∈ ⟨0, 1⟩. Platí [ ] P lim X n = p = 1. (16) n→∞

Co přesně vyjadřuje rovnost (16)? Podle věty 4.1 si můžeme Bernoulliho proces představit jako souřadnicový proces (14) na pravděpodobnostním prostoru (Λ∞ , A∞ , P ), kde Λ = {0, 1}. Pak můžeme psát [ ] ( ) ∞ ∞ ∞ P lim X n = p = P { a1 ∈ Λ | lim X n (a1 ) = p } n→∞ n→∞ }) ({ a1 + · · · + an ∞ ∞ =p = 1. =P a1 ∈ Λ lim n→∞ n 4

Nekonečná posloupnost náhodných veličin X1 , X2 , . . . je nezávislá, pokud jsou nezávislé veličiny Xi1 , . . . , Xik pro každé i1 , . . . , ik ∈ N. 5 Připomínáme, že náhodný výběr je náhodný vektor, jehož složky jsou nezávislé a mají stejné rozdělení.

20

Poslední výraz, který je ekvivalentní silnému zákonu velkých čísel, říká, že následující jev má pravděpodobnost 1: pozorujeme řetězec a∞ 1 , v němž je asymptotická relativní četnost jednotkových bitů rovna pravděpodobnosti p. Množinu všech takových řetězců nazýváme v teorii informace typickou. Silný zákon velkých čísel tak můžeme formulovat jako následující tvrzení: ∞ Množina typických řetězců a∞ má pravděpodobnost 1. 1 ∈ {0, 1}

Shrňme si naše úvahy: význam zákona velkých čísel spočívá v tom, že spojuje teorii pravděpodobnosti se statistickou úlohou odhadu neznámého parametru. Protože jevy mající pravděpodobnost 1 považujeme za skoro jisté, neznámou pravděpodobnost p můžeme dobře odhadnout na základě jedné dostatečně dlouhé realizace an1 Bernoulliho procesu jako relativní četnost a1 +···+an . n Veličiny X1 , X2 , . . . tvořící Bernoulliho proces jsou nezávislé. Pokusme se naopak vystihnout přirozenou závislost mezi symbolem Xn+1 a prefixem X1n . Nejjednodušší je markovský model párové závislosti mezi znakem Xn+1 a Xn , se kterým jsme se setkali již v příkladu 1.5. Příklad 4.2. Nechť P = (pab )a,b∈Λ je stochastická matice (viz příklad 1.5). Markovský řetězec je náhodný proces X1∞ nad konečnou abecedou Λ, který vyhoví podmínce pXn+1 |X1n (an+1 |an1 ) = pXn+1 |Xn (an+1 |an ) = pan an+1 pro každé n ∈ N, každé an+1 ∈ Λ a řetězec6 an1 ∈ Λn , pro který pX1n (an1 ) > 0. Snadno zjistíme, že n-rozměrné rozdělení markovského řetězce splňuje pX1n (an1 ) = pX1 (a1 )pX2 |X1 (a2 |a1 ) · · · pXn |Xn−1 (an |an−1 ),

an1 ∈ Λn .

Uveďme si dvě důležité vlastnosti procesů nad konečnou abecedu: stacionarita a ergodicita. Jejich splnění bývá nutné pro optimální fungování kompresních algoritmů v teorii informace (např. LZ algoritmy). Definice 4.2. Nechť X1∞ je náhodný proces nad konečnou abecedou Λ. Řekneme, že X1∞ je (striktně) stacionární, pokud platí pXmn (anm ) = pX n+k (anm ), m+k pro každé k, m, n ∈ N, m ≤ n, am , am+1 , . . . , an ∈ Λ. 6

Věříme, že mezi pojmy řetězec“ (slovo nad danou abecedou) a markovský řetězec“ ” ” (náhodný proces) nevznikne nedorozumění.

21

Stacionarita procesu vyjadřuje neměnnost jeho pravděpodobnostního chování n+k n na podřetězcích Xm a Xm+k , které se liší pouze posunem o k pozic. S trochou nadsázky si lze stacionaritu demonstrovat na příkladě dlouhého literárního díla, např. Anny Kareninové od L. N. Tolstého. Toto dílo by bylo realizací stacionárního procesu, pokud se budou všechna slova v textu použitá vyskytovat ve všech kapitolách a odstavcích se stejnou četností! Alespoň v případě jména hlavní hrdinky Anny lze doufat, že to může být splněno. Ovšem Levinův popis sklizně v první části knihy obsahuje mnoho výskytů řetězce kosa“ ” a ten se v dalších částech příliš nevyskytuje7 . Snadno nahlédneme, že Bernoulliho proces je stacionární, neboť výpočet pravděpodobnosti (15) závisí pouze na počtu jednotkových bitů v řetězci an1 . Markovský řetězec ovšem nemusí být stacionární—záleží na podobě počátečního rozdělení pX1 . Tvrzení 4.1. Nechť X1∞ je markovský řetězec s maticí přechodu P = (pab )a,b∈Λ nad konečnou abecedou Λ. Položme pX1 := (pX1 (a))a∈Λ . Markovský řetězec X1∞ je stacionární právě tehdy, pokud pro jeho počáteční rozdělení platí pX1 P = pX1 .

(17)

Tvrzení 4.1 lze přímo použít ke konstrukci stacionárního markovského řetězce. Vezměme libovolnou stochastickou matici P = (pab )a,b∈Λ a hledejme vektor pravděpodobností p = (pa )a∈Λ splňující (17), tedy pP = p. Vždy existuje alespoň jeden takový vektor p a nalezneme ho řešením odpovídající soustavy lineárních rovnic. Dostaneme tak markovský řetězec X1∞ s maticí přechodu P a počátečním rozdělením pX1 = p.

Reference [1] M. Navara. Pravděpodobnost a matematická statistika. Skriptum FEL ČVUT, Praha, 2007. [2] P. C. Shields. The Ergodic Theory of Discrete Sample Paths. AMS, 1996. [3] http://www.math.cornell.edu/~mec/2003-2004/cryptography/ subs/hints.html 7

V běžném petrohradském salóně se zřejmě nekosí.

22