Markovské řetězce

Kapitola 1
Markovské řetězce
1.1 Základní pojmy
1.1.1 Markovský řetězec je náhodný proces s diskrétní množinou stavů, diskrétním časem a takový,
že pravděpodobnost p(t)i , že v čase t bude proces ve stavu i, je stochasticky závislá pouze na stavu
v předchozím okamžiku, tj. na stavu v čase t−1.
Budeme se zabývat pouze tzv. homogenními markovskými řetězci, tj. takovými, kde výše zmíněné
pravděpodobnosti nezávisí na čase t.
A dále, budeme se zabývat pouze konečnými markovskými řetězci, tj. takovými, jejichž množina stavů
je konečná. Často přitom budeme předpokládat, že stavy máme očíslovány přirozenými čísly 1,2,3,...
1.1.2 Diskrétní čas. Předpoklad, že v markovském řetězci je čas diskrétní, znamená, že nás stavy
procesu zajímají pouze v okamžicích, které tvoří (potenciálně nekonečnou) rostoucí posloupnost. Mezi
těmito okamžiky se v markovském řetězci nic neděje, čas mezi těmito okamžiky v modelu neexistuje.
Zejména to znamená, že pro okamžik t má smysl hovořit o následujícím časovém okamžiku – budeme
jej značit jako okamžik t+1. Pro spojitý čas toto neplatí: ve spojitém čase mezi každými dvěma různými
okamžiky t1,t2 leží nekonečně mnoho okamžiků t takových, že t1 < t < t2.
Při praktickém modelování nějakého děje pomocí markovského řetězce jsou okamžiky ti zpravidla
odvozeny od výskytu nějaké události. Často touto událostí bývá změna stavu řetězce, to odpovídá situaci,
kdy nás zajímají jen změny stavů a nikoli doby, za jak dlouho ke změně stavu dochází. Okamžiky ti však
mohou být odvozeny i od jiných událostí, než pouze od změn stavu.
Jiný, rovněž častý, způsob modelování spočívá v tom, že stavy modelovaného děje sledujeme se
zcela pravidelným časovým krokem, např. každých 5 milisekund nebo každého prvního v měsíci. To pak
znamená, že ve skutečném ději (v ději, který modelujeme) může během časového kroku dojít i k několika
změnám stavu, ale model (markovský řetězec) tyto změny nedokáže zachytit. Tento způsob modelování
však na rozdíl od předchozího umožňuje modelovat dobu, která uplyne mezi změnami stavů nebo než je
dosaženo nějakého cílového stavu.
1.1.3 Pravděpodobnostní vektor v čase t. Svou znalost (zpravidla neúplnou) o tom, ve kterém
stavu se nacházel, nachází nebo bude nacházet markovský řetězec v čase t, budeme vyjadřovat jako
pravděpodobnostní vektor
p(t) = (p(t)1 ,p(t)2 ,...,p(t)n ) ,
kde n je počet stavů markovského řetězce.
Pokud s jistotou víme, že v čase t řetězec byl ve stavu i, pak jde o speciální případ, kdy p(t)i = 1 a
ostatní pravděpodobnosti p(t)j pro j negationslash= 0 jsou nulové.
Pravděpodobnostní vektor má vždy všechny složky nezáporné a jejich součet je roven jedné. Pravdě-
podobnostní vektor budeme pokládat za vektor řádkový (to kvůli pohodlnému násobení tzv. přechodovou
maticí).
1
2 Kapitola 1. Markovské řetězce
1.1.4 Pravděpodobnosti přechodu, přechodová matice. Označme pi,j podmíněnou pravděpo-
dobnost, že markovský řetězec bude v čase t ve stavu j, za podmínky, že v předchozím okamžiku t−1
byl ve stavu i.
Máme-li stavy pevně očíslovány 1,2,...,n, pak pravděpodobnosti pi,j můžeme uspořádat do čtvercové
matice, kterou nazýváme přechodovou maticí.
Přechodová matice má všechny prvky nezáporné a součet prvků v libovolném řádku je roven jedné.
Její řádky jsou tedy pravděpodobnostní vektory ve smyslu 1.1.3.
Naopak, každá čtvercová matice, jejíž všechny prvky jsou nezáporné a součty řádků jsou rovny jedné,
je přechodovou maticí nějakého markovského řetězce. Taková matice se nazývá stochastická.
1.1.5 Příklad – hazardní hra. Dva hráči mají dohromady 3Kč. Hra se skládá z posloupnosti partií,
v každé partii se hraje o jednu korunu: ten, kdo partii prohrál, musí zaplatit vítězi 1Kč. Když hráč prohrál
partii a nemá na zaplacení, pak tento hráč prohrál celou hru a hra tím končí. Všechny partie se hrají
stejným způsobem a spočívají v tom, že oba hráči hodí kostkou a komu na kostce padne méně bodů, ten
prohrál a zaplatí 1Kč. Pokud oběma hráčům padne stejný počet bodů, je výsledek partie nerozhodný a
nikdo nic neplatí a stav hry se nemění.
Na této hře nás může zajímat například to, jak závisí pravděpodobnost celkové prohry na výchozím
stavu, tj. na tom, s kolika penězi náš hráč začínal hrát. Dále by nás mohlo zajímat, jaký bude střední
počet partií než hra skončí, jaká je pravděpodobnost, že po pěti partiích již bude hra skončena nebo jaká
je pravděpodobnost, že po čtyřech partiích bude náš hráč mít přesně 2Kč.
Tuto hru lze modelovat markovským řetězcem o šesti stavech. Čtyři stavy odpovídají stavům financí
jednoho z hráčů (0, 1, 2, 3), další dva stavy odpovídají celkové prohře a celkové výhře. Čas je v tomto
modelu určen událostí, totiž sehráním další partie. Přechodová matice má tvar
P =





1 0 0 0 0 0
5/12 1/6 5/12 0 0 0
0 5/12 1/6 5/12 0 0
0 0 5/12 1/6 5/12 0
0 0 0 5/12 1/6 5/12
0 0 0 0 0 1





.
1.1.6 Příklad – táž hazardní hra trochu jinak. Jiný model téže hry (tj. jiný markovský řetězec)
dostaneme, když nerozhodné partie budeme pokládat za neplatné (nepodařené) a nebudeme je počítat.
Tento markovský řetězec bude mít přechodovou matici
P =





1 0 0 0 0 0
1/2 0 1/2 0 0 0
0 1/2 0 1/2 0 0
0 0 1/2 0 1/2 0
0 0 0 1/2 0 1/2
0 0 0 0 0 1





.
V obou modelech lze rovnocenným způsobem spočítat pravděpodobnost celkové prohry. Průměrný
počet partií než hra skončí bude ovšem v obou modelech různý.
1.1.7 Přechodový graf markovského řetězce je orientovaný graf, jehož vrcholy odpovídají stavům
markovského řetězce a orientované hrany odpovídají možným přímým změnám stavů, tj. změnám, které
mají nenulovou pravděpodobnost. Každá hrana z vrcholu (stavu) i do vrcholu (stavu) j je ohodnocena
pravděpodobností přechodu pi,j > 0. Počet hran je tedy roven počtu nenulových prvků přechodové
matice. Z každého vrcholu vychází alespoň jedna hrana a součet ohodnocení všech hran, které z vrcholu
vycházejí, je roven jedné.
Graf markovského řetězce je důležitý nejen pro svou názornost, ale zejména proto, že mnoho důležitých
vlastností markovského řetězce lze snadno odvodit z vlastností jeho grafu, zejména z jeho rozkladu na
silně souvislé komponenty.
16. prosince 2002, 16:04 Jiří Demel: Operační výzkum
1.2. Jednoduché výpočty 3
1.2 Jednoduché výpočty
1.2.1 Výpočet pravděpodobnostních vektorů. Známe-li přechodovou matici P a pravděpodob-
nostní vektor pro nějaký časový okamžik t, lze pravděpodobnosti jednotlivých stavů pro následující časový
okamžik t+ 1 počítat podle vzorce
p(t+1)j =
nsummationdisplay
i=1
p(t)i ·pi,j .
Celý pravděpodobnostní vektor p(t+1) tedy lze získat z pravděpodobnostního vektoru p(t) násobením
přechodovou maticí zprava:
p(t+1) = p(t) ·P .
Stejným postupem lze postupně počítat další a další pravděpodobnostní vektory. Obecně platí
p(t) = p(0) ·Pt ,
Výraz Pt na pravé straně rovnice je t-tá mocnina přechodové matice, tj. součin t stejných přechodových
matic P.
1.2.2 Pravděpodobnosti přechodu za více kroků. Označme p(t)i,j pravděpodobnost, že řetězec
přejde ze stavu i za přesně t časových kroků do stavu j. Pro pevný počet časových kroků t můžeme tyto
pravděpodobnosti uspořádat do čtvercové matice, označme ji P(t).
Přechodová matice P je pak speciálním případem, kde je počet časových kroků t = 1.
Platí
P(t) = Pt .