8. Rozložitelné a nerozložitelné homogenní markovské řetězce 8.1. Definice: Definice dosažitelných a sousledných stavů Nechť { }0n Nn;X ∈ 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. (Symbolicky se dosažitelnost stavu j ze stavu i označuje takto: i →j a souslednost stavů i, j se označuje takto: i ↔ j.) 8.2. Příklad: Je dán homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {1, 2, ..., 5} a maticí přechodu                 = 10000 4/104/300 4/14/102/10 00001 0002/12/1 P . Nakreslete přechodový diagram a sestavte tabulku dosažitelných stavů a tabulku sousledných stavů. Řešení: Přechodový diagram Tabulka dosažitelných stavů dosažitelný stavstav 1 2 3 4 5 1 + + - - - 2 + + - - - 3 + + + + + 4 + + + + + 5 - - - - + Tabulka sousledných stavů sousledný stavstav 1 2 3 4 5 1 + + - - - 2 + + - - - 3 - - + + - 4 - - + + - 5 - - - - + 8.3. Definice: Definice třídy trvalých stavů a třídy přechodných stavů Neprázdná množina stavů JC ⊆ 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ů. 8.4. Příklad: Pro homogenní markovský řetězec z příkladu 8.2. najděte třídy trvalých a přechodných stavů. Řešení: Nejprve uvedeme matici přechodu.                 = 10000 4/104/300 4/14/102/10 00001 0002/12/1 P Nakreslíme přechodový diagram. Z diagramu je zřejmé, že když řetězec vstoupí do třídy stavů {1, 2} nebo {5}, není odtud dosažitelný žádný stav vně třídy {1, 2} resp. {5}, tedy { } { }52,1JT ∪= . Když řetězec vstoupí do třídy stavů {3, 4}, je odtud dosažitelný stav 5, tedy { }4,3JP = . 8.5. Poznámka: Poznámka o podřetězci homogenního markovského řetězce 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 8.2. , který má matici přechodu                 = 10000 4/104/300 4/14/102/10 00001 0002/12/1 P , dostaneme podřetězec s maticí přechodu           = 100 001 02/12/1 1P . 8.6. Důsledek: Důsledek pro třídu trvalých stavů a pro třídu přechodných stavů 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í. 8.7. Věta: Kritérium pro stanovení třídy trvalých stavů Množina stavů JC ⊆ je třída trvalých stavů, právě když pij = 0 pro Cj,Ci ∉∈∀ . Důkaz: Nebudeme provádět. 8.8. Definice: Definice rozložitelného a nerozložitelného homogenního markovského řetězce Homogenní markovský řetězec se nazývá nerozložitelný, jestliže všechny jeho stavy jsou sousledné. V opačném případě říkáme, že řetězec je rozložitelný. Ekvivalentní definice: HMŘ se nazývá nerozložitelný, jestliže v něm neexistuje jiná třída trvalých stavů než J. 8.9. Věta: Řetězec s konečně mnoha stavy je rozložitelný právě tehdy, má-li matice přechodu (po případném přečíslování stavů) tvar       = BA 0P P 1 , kde P1, B jsou čtvercové matice. Důkaz: viz Prášková, str. 37. 8.10. Příklad: Uvažme náhodnou procházku s pohlcujícími stěnami, tj. homogenní markovský řetězec { }0n Nn;X ∈ 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ů. Řešení: Z přechodového diagramu okamžitě vyplývá, že stavy 0 a N jsou sousledné jenom samy se sebou. Ostatní stavy 1, 2, ..., N-1 jsou sousledné, řetězec je tedy rozložitelný a { } { } { }1N,,2,1J,N0J PT −=∪= K . 0 1 1-p 1 2 1-p p N-2 1-p p 1-p p 1 p N-1 N 1-p p 8.11. Definice: Definice stavů stejného typu Řekneme, že stavy Jj,i ∈ 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. 8.12. Věta: Věta o solidaritě Jsou-li stavy i a j sousledné, pak jsou stejného typu. Důkaz: Nebudeme provádět. 8.13. Důsledek: Důsledek pro nerozložitelný homogenní markovský řetězec 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é. 8.14. Věta: Věta o stacionárním rozložení nerozložitelného HMŘ Nechť { }0n Nn;X ∈ je homogenní markovský řetězec . Pak platí: 1. Jsou-li všechny jeho stavy přechodné nebo všechny trvalé nulové, pak stacionární rozložení neexistuje. 2. Jsou-li všechny jeho stavy trvalé nenulové, pak stacionární rozložení existuje a je jediné. 2a) Jsou-li všechny stavy neperiodické, pak ( ) Jji,,0nplima ij n j ∈>= ∞→ a také ( ) Jj,0nplima j n j ∈>= ∞→ 2b) Jsou-li všechny stavy periodické, pak ( ) Jji,,0kp n 1 lima n 1k ij n j ∈>= ∑= ∞→ a také ( ) Jj,0kp n 1 lima n 1k j n j ∈>= ∑= ∞→ 8.15. Důsledek: V nerozložitelném homogenním markovském řetězci s konečně mnoha stavy stacionární rozloženi existuje. 8.16. Věta: Věta o množině stavů dosažitelných z trvalého stavu. 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.) 8.17. Poznámka: Nejprve pro jednoduchost předpokládejme, že v rozložitelném řetězci existují jen dvě třídy stavů. Znamená to, že současným přečíslováním stavů v matici přechodu lze vytvořit nulové submatice. Dostáváme pak buď matici typu       = 2 1 P0 0P P , kde P1, P2 jsou čtvercové matice obsahující pravděpodobnosti přechodu mezi třídami stavů, přičemž obě třídy jsou třídy trvalých stavů, nebo typu       = QR 0P P 1 , kde P1, Q jsou čtvercové matice, přičemž P1 obsahuje pravděpodobnosti přechodu mezi trvalými stavy, matice Q obsahuje pravděpodobnosti přechodu mezi přechodnými stavy a matice R je tvořena pravděpodobnostmi přechodu z přechodných do trvalých stavů. Je-li matice P rozložitelná na tvar       = 0P P0 P 2 1 , kde 0 jsou nulové čtvercové matice, bude systém oscilovat mezi dvěma třídami přechodných stavů a příslušná matice P bude popisovat periodický řetězec. 8.18. Poznámka: poznámka o rozkladu konečné množiny stavů J a o kanonickém tvaru matice přechodu Předpokládejme nyní, že rozložitelný HMŘ je tvořen jak trvalými, tak přechodnými stavy, přičemž má r tříd trvalých stavů. Věta 8.16. 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 Pr21 JJJJJ ∪∪∪∪= K , kde J1, J2, ..., Jr 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ů). Kanonický tvar matice P JT J J1 J2 ... Jr JP J1 P1 Ø ... Ø Ø J2 Ø P2 ... Ø Ø ... ... ... ... ... ... JT Jr Ø Ø ... Pr Ø JP R1 R2 ... Rr Q 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. 8.19. Příklad: Je dán homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {0,1, ..., 5} a maticí přechodu                     = 4/304/1000 2/102/1000 2/13/16/1000 5/105/15/25/10 0004/12/14/1 000001 P . Najděte kanonický tvar matice P. Řešení: Přechodový diagram J1 = {0}, J2 = {3, 4, 5}, JP = {1, 2}. Kanonický tvar matice přechodu:                     = 5/25/15/105/10 4/12/10004/1 004/304/10 002/102/10 002/13/16/10 000001 P . Vidíme tedy, že ( )11 =P           = 4/304/1 2/102/1 2/13/16/1 2P       = 0 4/1 1R       = 5/105/1 000 2R       = 5/25/1 4/12/1 Q . 8.20. Definice: Definice fundamentální matice nerozložitelného homogenního markovského řetězce Nechť { }0n Nn;X ∈ 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: ( )( ) 1− −−= APIZ . 8.21. Věta: Věta o výpočtu středních hodnot dob prvních vstupů 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 ( ) Jj,iij m ∈ =M . Pak ( )MZEZIM )) +−= , kde E je matice ze samých jedniček, matice Z ) obsahuje jen diagonální prvky matice Z a matice M ) obsahuje jen diagonální prvky matice M. 8.22. Příklad: Při dlouhodobém sledování velkého souboru voličů s časovým krokem 1 měsíc byly zkoumány volební preference. Rozlišujeme strany A, B, C a Ostatní. Zavedeme homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {1, 2, 3, 4}, kde Xn = 1, když náhodně vybraný volič preferuje v n-tém měsíci stranu A, Xn = 2 pro stranu B, Xn = 3 pro stranu C a Xn = 4 pro ostatní strany. Pravděpodobnosti přechodu sympatií voličů jsou uvedeny v matici přechodu:             = 92,003,0005,0 1,08,005,005,0 12,005,082,001,0 14,011,005,07,0 P . Najděte limitní matici přechodu a vypočtěte matici středních hodnot dob prvních přechodů. Řešení: Limitní matici přechodu získáme složením čtyř stacionárních vektorů. Stacionární vektor existuje, neboť již matice P2 má všechny prvky kladné. Řešením systému a = aP s podmínkou 1a 4 1j j =∑= získáme stacionární vektor: a = (0,1328; 0,0881; 0,1843; 0,5949). Znamená to, že během dlouhé doby může strana A očekávat 13,3% voličů, strana B 8,8%, strana C 18,4% a ostatní strany dohromady 59,5%. Limitní matice přechodu               = 5949,01843,00881,01328,0 5949,01843,00881,01328,0 5949,01843,00881,01328,0 5949,01843,00881,01328,0 A Interpretace 1. řádku matice A: Pokud volič v jednom měsíci preferoval stranu A, pak v následujícím měsíci ji bude s pravděpodbností 13,3% preferovat opět. Ke straně B se přikloní s pravděpodobností 8,8%, ke straně C s pravděpodobností 18,4% a s pravděpodobností 59,5% zvolí některou z ostatních stran. K výpočtu matice středních hodnot dob prvních přechodů potřebujeme fundamentální matici Z: ( )( )               −−− −− −−− − =−−= − 6895,27885,07502,01508,0 7644,26153,34354,02863,0 3986,2531,07037,47741,0 1411,22549,02999,05863,2 1 APIZ . Matice               = 6895,2000 06153,300 007037,40 0005863,2 ˆZ , matice                       = 5949,0 1 000 0 01843 1 00 00 0881,0 1 0 000 1328,0 1 ˆM . Matice ( )               =+−= 6811,18971,239231,616122,20 1686,94265,54615,486327,21 5535,85,223538,113061,25 1207,82353,18505306,7 MZEZIM )) . Interpretace 1. řádku matice M: Volič, který na začátku sledování preferoval stranu A, v průměru za 7,5 měsíce dá poprvé znovu hlas této straně. V průměru za 50 měsíců bude poprvé preferovat stranu B a v průměru za 18,2 měsíce bude poprvé preferovat stranu C. V průměru za 8,1 měsíce se poprvé přikloní k některé z ostatních stran.