7. Rozložitelné a nerozložitelné homogenní markovské řetězce 7.1. Definice: Nechť je homogenní markovský řetězec s množinou stavů J. a) Řekneme, že stav j je dosažitelný ze stavu i, když existuje n ? 1 tak, že pij(n) > 0. Pokud pij(n) = 0 pro všechna n ? 1, pak řekneme, že stav j není dosažitelný ze stavu i. b) Řekneme, že stav j je sousledný se stavem i, jestliže j je dosažitelný z i a i je dosažitelný z j. 7.2. Příklad: Je dán homogenní markovský řetězec s množinou stavů J = {1, 2, ..., 5} a maticí přechodu . Nakreslete přechodový diagram a sestavte tabulku dosažitelných stavů a tabulku sousledných stavů. 7.3. Definice: Neprázdná množina stavů se nazývá třída trvalých stavů, jestliže žádný stav vně C není dosažitelný ze žádného stavu uvnitř C. Množina stavů, která není třídou trvalých stavů, se nazývá třída přechodných stavů. 7.4. Příklad: Pro homogenní markovský řetězec z příkladu 7.2. najděte třídy trvalých a přechodných stavů. 7.5. Poznámka: Jestliže v matici přechodu P vynecháme ty řádky a sloupce, které odpovídají stavům nepatřícím do třídy trvalých stavů C, dostaneme opět stochastickou matici. Lze ji považovat za matici přechodu homogenního markovského řetězce s množinou stavů C. Nazývá se podřetězec původního řetězce. Např. pro homogenní markovský řetězec z příkladu 7.2. dostaneme podřetězec s maticí přechodu . 7.6. Důsledek: a) Řetězec nikdy neopustí třídu trvalých stavů, jakmile do ní jednou vstoupí. b) Řetězec se nikdy nevrátí do třídy přechodných stavů, jakmile ji jednou opustí. 7.7. Věta: Množina stavů je třída trvalých stavů, právě když pij = 0 pro . 7.8. Definice: Homogenní markovský řetězec se nazývá nerozložitelný, jestliže všechny jeho stavy jsou sousledné, tj. kromě množiny stavů J v něm neexistuje žádná jiná třída stavů. V opačném případě říkáme, že řetězec je rozložitelný. 7.9. Příklad: Uvažme náhodnou procházku s pohlcujícími stěnami, tj. homogenní markovský řetězec s množinou stavů J = {0,1, ..., N-1, N} a přechodovým diagramem Zjistěte, zda tento řetězec je rozložitelný. Pokud ano, najděte třídy trvalých a přechodných stavů. 7.10. Definice: Řekneme, že stavy homogenního markovského řetězce jsou stejného typu, jestliže jsou oba a) přechodné b) trvalé nenulové c) trvalé nulové d) neperiodické e) periodické s touž periodou. 7.11. Věta: Jsou-li stavy i a j sousledné, pak jsou stejného typu. 7.12. Důsledek: V nerozložitelném homogenním markovském řetězci jsou všechny stavy stejného typu. Má-li nerozložitelný homogenní markovský řetězec konečnou množinu stavů, pak jsou všechny stavy trvalé nenulové. 7.13. Věta: Nechť stav i je dosažitelný z nějakého trvalého stavu j. Pak platí: a) stav i je trvalý stav stejného typu jako stav j b) i a j jsou sousledné stavy c) fji = fij = 1 (tj. pravděpodobnost, že řetězec vycházející ze stavu j resp. i vůbec někdy vstoupí do stavu i resp. j, je rovna 1). (Znamená to, že množina stavů dosažitelných z nějakého trvalého stavu j je množina trvalých stavů a tvoří nerozložitelný podřetězec původního řetězce.) 7.14. Poznámka: Věta 7.13. umožní rozložit množinu stavů J takto: Nechť j1 je trvalý stav s nejnižším indexem a J1 je množina všech stavů dosažitelných z j1. Nechť j2 je trvalý stav s nejnižším indexem mezi těmi trvalými stavy, které nepatří do J1 a nechť J2 je množina všech stavů dosažitelných z j2 atd. Lze tedy psát , kde J1, J2, ... jsou neslučitelné množiny trvalých stavů a JP je množina stavů přechodných. Je-li J konečná množina, pak matici přechodu P lze psát v tzv. kanonickém tvaru (po eventuálním přečíslování stavů). J JT J P J J . J 1 2 . r . J J P Ř . Ř Ř r 1 1 . . J Ř P . Ř Ř 2 2 . . . . . . . . . . . . . . . . . . . . J Ř Ř . P Ř r . r . JP P P . P Ř 1 2 . r . P1, ..., Pr jsou matice obsahující pravděpodobnosti přechodu mezi třídami trvalých stavů J1, ..., Jr. Matice R1, ..., Rr obsahují pravděpodobnosti přechodu mezi třídami přechodných a trvalých stavů. Matice Q obsahuje pravděpodobnosti přechodu mezi přechodnými stavy. 7.15. Příklad: Je dán homogenní markovský řetězec s množinou stavů J = {0,1, ..., 5} a maticí přechodu P . Najděte kanonický tvar matice P. 7.16. Definice: Nechť je nerozložitelný homogenní markovský řetězec s maticí přechodu P. Limitní matici přechodu označme A. Fundamentální matici Z tohoto řetězce definujeme vztahem: Z = (I -- (P -- A))-1. 7.17. Věta: Označme mij střední hodnotu doby 1. vstupu řetězce do stavu j za předpokladu, že vychází ze stavu i. Sestavíme matici . Pak , kde E je matice ze samých jedniček, matice obsahuje jen diagonální prvky matice Z a matice obsahuje jen diagonální prvky matice M. Příklady k 7. přednášce Příklad 1.: Je dán homogenní markovský řetězec s množinou stavů J = {1, 2, 3, 4, 5, 6}. Jeho přechodový diagram (bez ohodnocení hran) má tvar: Sestrojte tabulku dosažitelných stavů a tabulku sousledných stavů. Najděte třídy trvalých a přechodných stavů. Příklad 2.: Nechť je homogenní markovský řetězec s množinou stavů J = {0, 1, 2} a maticí přechodu . Ukažte, že tento řetězec je nerozložitelný. Najděte střední hodnoty dob prvních návratů do stavů 0, 1, 2. Příklad 3.: Nechť je homogenní markovský řetězec s množinou stavů J = {0, ..., 5} a maticí přechodu . Najděte kanonický tvar P. Příklad 4.: Nechť je homogenní markovský řetězec s množinou stavů J = {0, 1, 2, 3} a maticí přechodu . Zjistěte, zda tento řetězec je rozložitelný nebo ne. Pokud ano, najděte třídy trvalých a přechodných stavů. Příklad 5.: Při analýze situace na trhu práce jednotliví pracovníci mohou "pracovat ve své profesi" (stav 1), "pracovat v jiné profesi" (stav 2), "být nezaměstnaní" (stav 3). Při sledování velkého souboru pracovníků se ukázalo, že během jednotlivých měsíců došlo ke změnám mezi uvedenými stavy následovně: ve své profesi pracovalo i v následujícím měsíci 80% pracovníků, 10% přešlo k jiné profesi a 10% se stalo nezaměstnanými. Z pracovníků pracujících mimo svou profesi 10% přešlo v následujícím měsíci ke své profesi, 70% zůstalo nadále pracovat mimo svou profesi a 20% se stalo nezaměstnanými. Z nezaměstnaných našlo práci ve své profesi 5% osob, 30% nezaměstnaných získalo práci mimo svou profesi a 65% osob zůstalo i v dalším měsíci nezaměstnanými. Najděte matici přechodu P, limitní matici A, fundamentální matici Z a matici M středních hodnot dob prvního vstupu do stavů 1, 2, 3. Příklady k 8. přednášce Příklad 1.: Jistá firma třídí svoje pohledávky po termínu splatnosti do třicetidenních intervalů. Pohledávky, které jsou nad 90 dnů po době splatnosti, jsou považovány za nedobytné. K popisu situace zavedeme homogenní markovský řetězec s množinou stavů J = {1, 2, 3, 4, 5}, kde stav 1 znamená pohledávky 0 -- 30 dní po době splatnosti, stav 2 pohledávky 31 -- 60 dní po době splatnosti, stav 3 pohledávky 61 -- 90 dní po době splatnosti, stav 4 splacené pohledávky a stav 5 nedobytné pohledávky. Dlouhodobou analýzou doby splatnosti jednotlivých pohledávek bylo zjištěno, že pravděpodobnosti přechodu jsou: p12 = 0,77, p14 = 0,23, p23 = 0,34, p24 = 0,66, p34 = 0,73 a p35 = 0,27. a) Sestavte matici přechodu a nakreslete přechodový diagram. b) Klasifikujte stavy na absorpční a neabsorpční a najděte kanonický tvar matice přechodu. c) Vypočtěte fundamentální matici a interpretujte její prvky. d) Vypočtěte matici přechodu do absorpčních stavů a interpretujte její prvky. e) Předpokládejme, že objem pohledávek po termínu splatnosti v jednotlivých třicetidenních intervalech je (4 030 000 Kč, 9 097 000 Kč, 3 377 000 Kč). Jaká je průměrná hodnota splacených a nedobytných pohledávek? Příklad 2.: Máme populaci diploidní cizosprašné rostliny, v níž sledujeme gen se dvěma alelami a, A. Z populace náhodně vybereme jedince, sprášíme ho homozygotním jedincem typu AA a v příštím kroku vybíráme z populace tvořené jejich potomky. Postup lze popsat pomocí homogenního markovského řetězce s množinou stavů J = {0,1, 2}, kde stav 0 = aa, stav 1 = Aa = aA, stav 2 = AA. a) Sestavte matici přechodu a ukažte, že řetězec je absorpční. b) Najděte kanonický tvar matice přechodu c) Vypočtěte fundamentální matici a interpretujte její prvky. d) Vypočtěte matici přechodu do absorpčních stavů a interpretujte její prvky. e) Zjistěte vektor středních hodnot počtu kroků před absorpcí. Příklad 3.: Máme populaci diploidní samosprašné rostliny, v níž sledujeme gen se dvěma alelami a, A. Z populace náhodně vybereme jedince, samosprášíme ho a v příštím kroku vybíráme z populace tvořené jejich potomky. Postup lze popsat pomocí homogenního markovského řetězce s množinou stavů J = {0,1, 2}, kde stav 0 = aa, stav 1 = Aa = aA, stav 2 = AA. Řešte tytéž úkoly jako v příkladu 2. Příklad 4.: Student vysoké školy během studia úspěšně ukončí ročník a postoupí do dalšího ročníku s pravděpodobností p, opakuje ročník s pravděpodobností r a zanechá studia s pravděpodobností q, p + q + r = 1. Pro jednoduchost předpokládáme, že pravděpodobnosti p, q, r jsou konstantní. Výsledky studia v jednotlivých ročnících lze popsat homogenním markovským řetězcem s množinou stavů J = {1, ..., 7}, přičemž stav 1 - zanechání studia, stav 2 -- úspěšné ukončení studia, stav 3 -- studium 1. ročníku , ... , stav 7 -- studium 5. ročníku. a) Sestavte matici přechodu a ukažte, že řetězec je absorpční. b) Najděte kanonický tvar matice přechodu c) Vypočtěte fundamentální matici a interpretujte její prvky. d) Jaká je pravděpodobnost, že student, který je v 1. ročníku, zanechá studia?