Markovské řetězce

.
Důkaz je třeba doplnit.
1.5.2 Kanonický tvar přechodové matice absorbujícího řetězce. Stavy absorbujícího řetězce lze
přečíslovat tak, že nejnižšími čísly jsou očíslovány absorbující stavy a za nimi následují stavy transientní.
Po takovém přečíslování má přechodová matice tvar
P =
parenleftbigg E 0
R Q
parenrightbigg
1.5.3 Věta. Mocniny matice Q konvergují k nulové matici, tj. limt→∞Qt = 0.
Existuje inverzní matice (E −Q)−1
Součet maticové řady 0 +E +Q+Q2 +Q3 +... existuje a je roven (E −Q)−1.
1.5.4 Fundamentální matice absorbujícího řetězce je matice H = (E −Q)−1.
1.5.5 Věta. Prvky fundamentální matice H mají tento význam: hi,j je střední počet, kolikrát řetězec
projde stavem j, když začal ve stavu i.
Důsledek: Jestliže absorbující řetězec začal ve stavu i, pak střední počet časových kroků, než řetězec
dosáhne absorbujícího stavu, je roven součtu hodnot v i-tém řádku fundamentální matice H.
1.5.6 Pravděpodobnost absorbce v daném stavu Je dán absorbující řetězec, výchozí stav i a
absorbující stav j. Označme bi,j pravděpodobnost, že řetězec dosáhne stavu j, když (s pravděpodobností
1) začal ve stavu i.
Pravděpodobnosti bi,j lze uspořádat do matice B. Platí
B = R +QB .
Odtud plyne
(E −Q)B = R (1.1)
a tedy
B = (E −Q)−1R . (1.2)
1.5.7 Výpočty pomocí elementárních úprav grafu. Pro řetězce s nevelkým počtem stavů a pro
ruční výpočet je často vhodnější metoda založená na elementárních úpravách grafu:
Výpočet pravděpodobností absorbce pro výchozí stav i je snadný: Graf postupně redukujeme eli-
minováním smyček a vrcholů, až nakonec zbude pouze výchozí vrchol i a všechny absorbující vrcholy.
Elementární úpravy zachovávají pravděpodobnost dosažení stavu, proto z výsledného grafu lze okamžitě
zjistit hledané pravděpodobnosti absorbce v jednotlivých absorbujících stavech.
Výpočet středního počtu průchodů stavem j, když řetězec začal ve stavu i, lze také provést elemen-
tárními úpravami grafu. Nejprve všechny absorbující stavy nahradíme jediným absorbujícím stavem a,
protože v této úloze se nezajímáme, kde k absorbci dojde, ale kdy k ní dojde. Dále pak graf zredukujeme
elementárními úpravami tak, aby zbyly pouze tři vrcholy i,j,a. V tomto redukovaném grafu označme p
pravděpodobnost smyčky ve vrcholu j a dále označme q pravděpodobnost přechodu ze stavu i do stavu j.
Je dobré si uvědomit, že vzhledem k původnímu absorbujícímu řetězci je q pravděpodobnost, že ze stavu
i bude dosaženo stavu j (tj. že nedojde k absorbci dříve než stavu j dosáhneme) a pravděpodobnost p
je pravděpodobnost, že řetězec po průchodu stavem j do tohoto stavu ještě někdy vrátí (dříve než dojde
16. prosince 2002, 16:04 Jiří Demel: Operační výzkum
1.6. Stacionární řetězce 7
k absorbci). Máme-li takto určeny pravděpodobnosti p a q, lze střední počet průchodů stavem j určit
podle vzorce
hi,j = q1−p
1.6 Stacionární řetězce
Stacionární markovské řetězce by bylo možno pokládat za speciální případ řetězců periodických, kde
perioda je rovna jedné. Jde však o případ z praktického hlediska velmi významný, proto mu věnujeme
samostatnou sekci.
Lze dokázat, že ve stacionárním řetězci pro každý stav j existuje limita
limt→∞p(t)i,j = wj (1.3)
a tato limita nezávisí na výchozím stavu i.
Dále, ve stacionárním řetězci mocniny přechodové matice Pt pro t →∞ konvergují a to k matici W,
jejíž všechny řádky jsou rovny vektoru stacionárních pravděpodobností w = (w1,w2,...,wn).
Z toho plyne, že matice W musí splňovat rovnici
w·P = w . (1.4)
1.6.1 Výpočet stacionárních pravděpodobností. Základem pro výpočet je soustava rovnic 1.4.
Tuto soustavu lze získat také tak, že pro jednotlivé stavy uvažujeme všechny možné stavy předchozí: Pro
každý stav j tak dostáváme rovnici
wj = w1p1,j +w2p2,j +...+wnpn,j
Soustava rovnic 1.4 je ovšem homogenní (po převedení všech proměnných na levou stranu je pravá
strana nulová) a proto nemá jednoznačné řešení: libovolný násobek nějakého řešení je opět řešením této
soustavy. Matice této soustavy (P −E) je singulární, některý její řádek je lineární kombinací ostatních.
Proto ze soustavy 1.4 můžeme jednu rovnici vynechat (lze ji odvodit z ostatních), a dále k soustavě
přidáváme rovnici
nsummationdisplay
i=1
wi = 1 ,
Řešením takto vzniklé soustavy lineárních rovnic získáme vektor stacionárních pravděpodobností w.
1.6.2 Praktické využití stacionárních pravděpodobností. Při praktickém modelování je často
každý stav i v modelovaném ději spojen s náklady ci. Pro některé stavy to samozřejmě mohou být
náklady nulové. Případné zisky můžeme pokládat za záporné náklady.
Ze znalosti stacionárních pravděpodobností wi pak lze pro pro ustálené chování stacionárního mar-
kovského řetězce spočítat střední náklady na jednotku času (přesněji, na jeden časový krok) podle vzorce
C =
nsummationdisplay
i=1
wici .
1.7 Periodické řetězce
Označme d největší společný dělitel délek všech cyklů. Toto číslo budeme nazývat periodou řetězce.
1.7.1 Periodické třídy. Množinu stavů periodického řetězce lze rozdělit do d disjunktních podmnožin
C0,C1,C2,...,Cd−1 takových, že v přechodovém grafu vycházejí všechny hrany z množiny C0 vedou pouze
do množiny C1, všechny hrany z množiny C1 vedou pouze do množiny C2, atd., až nakonec všechny hrany
z množiny Cd−1 vedou pouze do množiny C0.
Připomeňme, že řetězec je periodický a tedy ergodický. Z libovolného stavu i je proto dosažitelný
každý stav j, a to včetně stavu i. Existuje tedy cyklus, procházející stavem i. Z existence d periodických
tříd však plyne, že délka každého cyklu je je násobkem periody d. Nemůže tedy např. být menší než d.
Jiří Demel: Operační výzkum 16. prosince 2002, 16:04
8 Kapitola 1. Markovské řetězce
1.7.2 Periodické chování. Název periodického řetězce je odvozen z faktu, že byl-li řetězec v čase 0
ve třídě C0, pak třída, ve které se bude nacházet v obecném čase t závisí zcela jednoznačně na zbytku při
dělení času t periodou d.
Je-li např. d = 2, pak máme dvě periodické třídy. V jedné z nich se řetězec může nacházet pouze
v lichých okamžicích, ve druhé pouze v sudých okamžicích.
Podobně je-li např. d = 3, máme tři periodické třídy. V jedné z nich se řetězec může nacházet pouze
v okamžicích t dělitelných třemi, ve druhé v okamžicích, které při dělení třemi dávají zbytek 1 a konečně
ve třetí třídě se může nacházet pouze v okamžicích, které při dělení třemi dávají zbytek 2.
1.7.3 Pravděpodobnosti výskytu stavů. V periodickém řetězci neexistují limity (1.3), a tedy nemá
smysl mluvit o stacionárních pravděpodobnostech. Důvod neexistence limity je prostý: v posloupnosti
jsou nenulové hodnoty pouze na každém d-tém místě a mezi nimi jsou nuly. Taková posloupnost nemůže
konvergovat k ničemu nenulovému.
Pro praktické účely ovšem nepotřebujeme přesně tuto limitu. Potřebujeme vědět, jaké procento
času stráví řetězec v jednotlivých stavech. Nebo jinak, jaká je pravděpodobnost wi, že v náhodném
(a dostatečně vzdáleném) časovém okamžiku t najdeme řetězec ve stavu i.
Předpokládejme, že budeme náhodně volit okamžik t tak, aby všechny možné zbytky při dělení času
t periodou d měly stejnou pravděpodobnost 1/d. Pak pravděpodobnosti wi, že v náhodném okamžiku t
najdeme periodický řetězec ve stavu i, můžeme počítat naprosto stejným postupem jako v 1.6.1.
16. prosince 2002, 16:04 Jiří Demel: Operační výzkum