Markovské řetězce

1.2.3 Příklad. V markovském řetězci z příkladu 1.1.5 předpokládejme, že náš hráč začíná ve stavu
3, tj. na začátku má 1Kč. S jakou pravděpodobností bude mít po čtyřech partiích přesně 3Kč? Kolika
způsoby může tohoto stavu dosáhnout?
Výchozí pravděpodobnostní vektor je
p(0) = (0,0,1,0,0,0) .
Pravděpodobnostní vektor p(4) bychom mohli zjistit tak, že bychom vektor p(0) čtyřikrát vynásobili maticí
P zprava a z výsledného vektoru bychom vzali pátou složku, tj. p(4)5 . To je postup vhodný pro počítač
(nebo pro kalkulačku, která umí násobit matice). Pro ruční výpočet je to poněkud pracné a nepohodlné.
Jiný způsob by mohl být tento: Napíšeme seznam všech možností, jak se náš řetězec může dostat
ze stavu 3 do stavu 5. Každá tato možnost je vlastně posloupnost výsledků čtyř partií. Pro každou
z těchto posloupností vypočteme pravděpodobnost, že průběh hry bude přesně takový (půjde o součin
čtyř pravděpodobností pro čtyři partie). Pravděpodobnosti jednotlivých posloupností pak sečteme.
1 PVVV 5/12 ·5/12·5/12·5/12 = 0.0301408
1 VPVV 5/12 ·5/12·5/12·5/12 = 0.0301408
1 VVPV 5/12 ·5/12·5/12·5/12 = 0.0301408
1 NNVV 2/12 ·2/12·5/12·5/12 = 0.0048225
1 NVNV 2/12 ·5/12·2/12·5/12 = 0.0048225
1 NVVN 2/12 ·5/12·5/12·2/12 = 0.0048225
1 VNNV 5/12 ·2/12·2/12·5/12 = 0.0048225
1 VNVN 5/12 ·2/12·5/12·2/12 = 0.0048225
1 VVNN 5/12 ·5/12·2/12·2/12 = 0.0048225
= 0.1193576
Tato „metoda hrubé sílycsquotedblright sice zaručeně vede ke správnému výsledku, ale je zřejmé, že je velice
pracná, zejména pro větší hodnoty t je dokonce mnohem pracnější než výpočet mocniny matice Pt.
Další nevýhodou této metody jsou problémy se zaokrouhlováním, neboť výsledek získáme jako součet
velkého počtu velmi malých čísel.
Jiří Demel: Operační výzkum 16. prosince 2002, 16:04
4 Kapitola 1. Markovské řetězce
Pro ruční výpočet je v našem jednoduchém příkladě vhodnější počítat pravděpodobnostní vektory
postupně, tedy vlastně stejně jako při násobení přechodovou maticí, ale namísto nepohodlného násobení
maticí budeme postupovat podle schématu
p(t)i−1 p(t)i p(t)i+1
arrowsoutheast ↓ arrowsouthwest
p(t+1)i
přičemž samozřejmě nesmíme počítat neexistující přechody ze stavů 1 a 6.
Podle stejného schématu lze snadno spočítat o počet možností, jen přitom používáme prostě sečítáme
příslušné hodnoty z předchozího řádku. Poněvadž výpočet počtu možností je jednodušší, předvedeme jej
jako první:
t 1 2 3 4 5 6
0 0 0 1 0 0 0
1 0 1 1 1 0 0
2 1 2 3 2 1 0
3 3 5 7 6 3 1
4 8 12 18 16 9 4
Všimněte si, že z poslední řádky stačilo spočítat jen jednu hodnotu, která nás zajímá (tj. 9 možností) a
podobně jsme mohli vynechat i několik dalších hodnot.
Nyní již předvedeme výpočet pravděpodobnosti p(4)5 :
t 1 2 3 4 5 6
0 1
1 5/12 2/12 5/12
2 54/144 20/144 25/144
3 435/1728 150/1728
4 2475/20736
což dává výsledek shodný s předchozím.
1.3 Klasifikace stavů a typy řetězců
Většinu těchto pojmů definujeme pomocí vlastností přechodového grafu, neboť tyto vlastnosti lze v grafu
poměrně snadno ověřit.
1.3.1 Stochasticky uzavřená množina stavů je taková množina, ze které nevychází žádná hrana
ven. Jinak řečeno, pravděpodobnost, že markovský řetězec opustí stochasticky uzavřenou množinu, je
nulová.
1.3.2 Ergodická množina stavů je stochasticky uzavřená množina, která neobsahuje menší stochas-
ticky uzavřenou množinu.
Množina stavů je ergodická právě tehdy, když jí odpovídající podgraf přechodového grafu je silně
souvislou komponentu, ze které nevychází ven žádná hrana.
Ergodický stav je stav, který je prvkem nějaké ergodické množiny. Každý markovský řetězec má
alespoň jednu ergodickou množinu.
1.3.3 Transientní stav je stav, který není ergodický.
Transientní množina je množina všech transientních stavů. Transientní množina se tedy skládá z nula
až několika silně souvislých komponent přechodového grafu.
16. prosince 2002, 16:04 Jiří Demel: Operační výzkum
1.4. Analýza obecného markovského řetězce 5
1.3.4 Absorbující stav je stav, který sám tvoří jednoprvkovou ergodickou množinu.
Stav je absorbující právě tehdy, když v přechodovém grafu z tohoto stavu vychází jediná hrana a to
smyčka (která má tudíž pravděpodobnost 1).
1.3.5 Absorbující řetězec je takový markovský řetězec, jehož všechny ergodické stavy jsou absor-
bující.
1.3.6 Ergodický markovský řetězec je takový, jehož přechodový graf je silně souvislý.
1.3.7 Stacionární markovský řetězec je takový, jehož přechodový graf je silně souvislý a největší
společný dělitel délek všech cyklů je roven jedné (tj. délky všech cyklů jsou nesoudělné). Dodejme, že
délku cyklu zde chápeme jako počet jeho hran.
Vysvětlení názvu stacionární je podáno v 1.6.
1.3.8 Periodický markovský řetězec je takový, jehož přechodový graf je silně souvislý a největší
společný dělitel délek všech cyklů je větší než jedna (tj. délky všech cyklů jsou soudělné). Dodejme, že
délku cyklu zde chápeme jako počet jeho hran.
Vysvětlení názvu periodický je podáno v 1.7.
1.4 Analýza obecného markovského řetězce
Prvým krokem v analýze obecného markovského řetězce je vždy nalezení silně souvislých komponent a
jejich rozdělení na transientní a ergodické.
1.4.1 Analýza transientního chování. Má-li řetězec neprázdnou transientní část, pak základní
otázky týkající se této části jsou:
• Je-li dán výchozí transientní stav a cílová ergodická množina, určit pravděpodobnost, že řetězec
dosáhne této ergodické množiny
• Je-li dán výchozí transientní stav, určit střední počet kroků, než bude dosaženo některého ergodic-
kého stavu.
• Je-li dán výchozí transientní stav i a další transientní stav j, určit střední počet průchodů stavem
j, než bude dosaženo některého ergodického stavu.
Pro účely řešení těchto otázek lze markovský řetězec zjednodušit tím, že každou ergodickou množinu
stavů nahradíme jedním absorbujícím stavem. Pro řešení otázek 2 a 3 dokonce můžeme všechny ergodické
množiny nahradit jedním společným absorbujícím stavem.
Řešením těchto otázek se budeme zabývat v 1.5.
Je-li transientní část řetězce prázdná, jsou všechny stavy řetězce ergodické a analýzu transientního
chování přeskakujeme.
1.4.2 Analýza ergodického chování. Co se s řetězcem děje po dosažení ergodického stavu, lze
zjišťovat pro každou ergodickou množinu zvlášť, neboť řetězec nemůže ergodickou množinu opustit.
Ukazuje se, podrobněji viz 1.6 a 1.7, že dlouhodobé chování ergodického řetězce je do značné míry
nezávislé na výchozím stavu. Proto v analýze ergodického chování uvažujeme každou ergodickou množinu
zvlášť jako samostatný ergodický markovský řetězec.
V ergodických řetězcích jsou základní otázky tyto:
• Pro každý stav i určit pravděpodobnost wi, že v náhodně zvoleném okamžiku najdeme řetězec ve
stavu i.
• Pro každý stav i určit střední počet kroků, po kterém se řetězec vrátí do stavu i.
Řešením těchto otázek se budeme zabývat v 1.6 a 1.7.
Jiří Demel: Operační výzkum 16. prosince 2002, 16:04
6 Kapitola 1. Markovské řetězce
1.5 Absorbující řetězce
Uvedeme dva způsoby řešení otázek uvedených v 1.4.1. Jeden bude založen na úpravách grafu, druhý
bude založen na maticích. Nejprve však důležité tvrzení.
1.5.1 Věta. Pro každý markovský řetězec a pro každý výchozí transientní stav i platí, že posloupnost
pravděpodobností, že se řetězec v čase t nachází v transientním stavu, konverguje k nule pro t →∞