P3 - Klasifikace stavů Markovova řetězce 1. 8 Trvalé (nulové, nenulové a absorpční stavy), přechodné stavy Definice 6 Stav Markovova řetězce se nazývá trvalý [recurrent state][1], jestliže platí Tato podmínka znamená, že pokud se někdy proces nachází ve stavu i , pak se aspoň někdy v budoucnu proces opět (s určitostí) do stavu i opět dostane. Trvalé stavy mohou být jednak takové, že návrat do výchozího stavu může nastat kdykoliv nebo až po konečném nebo nekonečném počtu kroků. Speciální případem trvalého stavu je tzv. absorpční stav, ze kterého se nelze dostat (po jakémkoliv počtu kroků) do jiného stavu (tedy ani do jiného trvalého). Definice 7 Stav Markovova řetězce se nazývá absorpční [absorbing state], jestliže platí Tato podmínka znamená, že pokud se někdy sledovaný proces dostane do stavu i , pak již tento stav nikdy neopustí. Odpovídá to situaci, kdy (jednokroková) pravděpodobnost přechodu ze stavu do i do stavu i je rovna 1. Definice 8 Stav Markovova řetězce se nazývá přechodný [transient state], jestliže platí Tato podmínka znamená, že pokud se někdy proces dostane do stavu i , pak existuje kladná pravděpodobnost, že se proces do tohoto stavu i již nikdy v budoucnu nevrátí. Tato pravděpodobnost je dána právě hodnotou (1.31) Obecně není možné vypočíst pravděpodobnosti prvního průchodního stavu pro všechna n, takže není vždy zřejmé, zda určitý stav má být klasifikován jako rekurentní nebo přechodný. Poznámka 1 Ačkoliv všechny stavy v příkladě se zásobami kamer jsou trvalé, není nijak jednoduché dokázat, že Podrobnější členění trvalých stavů je založeno na pojmu střední doba návratu ve smyslu Definice 5. Zavedeme tedy Definice 9 Stav Markovova řetězce se nazývá nulový trvalý [null recurrent state], jestliže platí . a nazývá se nenulový trvalý [positive recurrent state], platí-li . 1. 9 Dosažitelnost, souslednost stavů. Rozložitelné a nerozložitelné řetězce Definice 10 Stav Markovova řetězce se nazývá dosažitelný [accesible] ze stavu , jestliže platí pro nějaké . Poznámka 2 . Dosažitelnost není symetrická vlastnost. Z okolnosti, že stav je dosažitelný ze stavu , neplyne, že by ze stavu byl naopak dosažitelný stav i. Připomeňme, že je právě podmíněná pravděpodobnost toho, že proces vycházeje ze stavu přejde po n krocích do stavu . Lze snadno ukázat, že stav je dosažitelný ze stavu právě a jen tehdy, jestliže lze dospět do stavu vycházeje ze stavu po nějakém kladném celočíselném počtu kroků. Poznámka 3 V příkladě se zásobami máme pro všechna i,j, takže každý stav je dosažitelný z každého jiného stavu. Definice 11 Stavy , Markovova řetězce se nazývají sousledné [„to communicate“], jestliže stav je dosažitelný ze stavu a současně, jestliže stav je dosažitelný ze stavu . Zřejmě tedy postačující podmínkou pro to, aby byly vzájemně dosažitelné všechny stavy Markovova řetězce[2], je , aby existovala kladná hodnota n (nezávislá na a , pro kterou by pro všechna , a současně, aby existovala kladná hodnota m, pro kterou platilo . Jsou-li stavy sousledné, umožňuje to mj. v případě rozložitelného Markovova řetězce dekomponovat množinu trvalých stavů do více podmnožin/skupin, přičemž každá skupina trvalých stavů bude obsahovat vždy jen vzájemně sousledné stavy V důsledku platnosti Chapman-Kolmogorovových rovnic (1.21), tedy toho, že platí pro a nezápornosti každé , můžeme vyvodit, že Obdobný argument lze uplatnit pro opačný vztah souslednosti obou stavů. Definice 12 Řekneme, že Markovův řetězec je nerozložitelný (ireducibilní) [irreducible], jestliže relace ekvivalence indukuje pouze jedinou třídu ekvivalentních stavů. Jinými slovy, řetězec je ireducibilní, jestliže jsou všechny stavy sousledné. Je-li v řetězci taková třída jen jedna, pak tento řetězec nazýváme nerozložitelný (ireducibilní). Tvoří-li všechny stavy řetězce uzavřenou třídu a jsou-li tyto stavy ergodické, pak se tento řetězec nazývá regulární. Jestliže pro jeden nebo i několik stavů platí (tj. setrvání ve stavu je jistý jev) a do těchto stavů existuje vstup tzn. existuje stav j nepatřící do tohoto podřetězce a takový, že , pak o těchto stavech mluvíme jako o absorpčních. Ostatní stavy řetězce pak nutně musí být transientní. Řetězce obsahující absorpční stavy nazýváme absorpční řetězce. 1. 10 Periodicita stavů Markovova řetězce Jiná klasifikace stavů Markovova řetězce je založena na tom, po jakém počtu kroků (přechodů) může nastat opakování určitého stavu. Půjde o to, že realizace některých stavů může nastat pouze po nějakém násobku kroků. V tomto smyslu zavedeme definice Definice 13A Stav Markovova řetězce se nazývá periodický [ periodic state] s periodou r, jestliže platí pro všechna Periodou stavu , někdy značenou rozumíme největší společný dělitel ze všech přirozených čísel (větší než 1) , pro který . [3] Definice 13B Stav Markovova řetězce se nazývá neperiodický [non-periodic state], jestliže neexistuje žádná perioda , vůči níž by tento stav byl periodický Definovali jsme tedy periodu stavu jako největší společný dělitel všech přirozených čísel pro které . [ Pokud pro všechna , definujeme ]. Máme-li náhodnou procházku, kde nepřipouštíme setrvání ve stavu (při jednom „přechodu“), pak každý stav má periodu 2. Pokud bychom připustili možnost setrvání v daném stavu, pak by měl každý stav periodu 1, tj.byl by neperiodický. protože bez ohledu na počáteční stav j systému, může systém dosáhnou stavu a zůstat v něm jakoukoliv dobu před návratem do stavu j. Tvrzení 2. Jsou-li stavy sousledné a jeden z nich je periodický s periodou , pak i druhý stav je periodický a má shodnou periodu. Tedy Jestliže , potom platí Tvrzení 3. Jestliže stav má periodu , pak existuje přirozené číslo N, závisející na , že pro všechna přirozená platí Tvrzení zajišťuje, že návrat do stavu i může nastat ve všech dostatečně velkých násobcích periody . Důsledek: Jestliže , potom pro všechna přirozená dostatečně velká k. Definice 14 Stav Markovova řetězce se nazývá ergodický [ergodic state], jestliže je trvalý, nenulový a neperiodický.[4] Příklad V konečném Markovově řetězci s M stavy a maticí pravděpodobností přechodu má každý stav periodu M. Většina procesů typu Markovových řetězců, se kterými se lze setkat, jsou neperiodické. Náhodné procházky jsou naopak typické periodickým chováním. 1.11 Další prostředky klasifikace trvalých a přechodných stavů Klasifikace stavů trvalé/přechodné zavedená Definicí 6 resp. Definicí 8 a založená na chování nekonečné řady , může být přenesena na chování tomuto procesu odpovídající nekonečné řady . Přesněji to vyslovuje následující věta: Věta 3A: Stav je trvalý právě tehdy, jestliže platí . Důkaz (Karlin str.66): je založen na využití Abelova lemmatu pro vytvořující funkce A) nutnost: Předpokládejme, že stav je trvalý, to znamená, že (podle definice). Potom lze na základě prvního tvrzení Abelova lemmatu tvrdit, že platí . Takže ze vztahu (8.25B) plyne . Odvoláme-li se na druhé tvrzení Abelova lemmatu, dostaneme , což dává dokazované tvrzení. B) postačitelnost: Předpokládejme, že stav je přechodný, tzn. Platí . S využitím prvního tvrzení Abelova lemmatu a s ohledem na platnost (8.25B), vyvodíme, že . Dále, s odvoláním na druhé tvrzení Abelova lemmatu dostáváme výsledek, že , což je ve zřejmém rozporu s naším předpokladem trvalosti stavu , čímž je ověřena postačitelnost. � . Opačnou situaci popisuje tvrzení Věta 3B: Stav je přechodný právě tehdy, když . Poznámka 7 Střední počet návratů do stavu , při daném je roven . takže věta 3A říká, že stav je trvalý právě tehdy, jestliže střední počet návratů je nekonečný. Jak bylo výše (Definicí 9) uvedeno, veličina je nazývána střední doba návratu (do stavu i). V závislosti na ní rozlišujeme stavy a) trvalé nulové, jestliže b) trvalé nenulové, jestliže Důsledek: Nechť je trvalý stav. Máme[5] [6]při Důkaz: Z rovnosti vyplývá . Víme, že trvalý stav je nulový právě tehdy, když platí (*) . To je splněno , kdykoliv platí (**) . □ . Složitější je důkaz ekvivalentnosti (*) a (**) Věta 4: Všechny stavy dosažitelné z trvalého stavu jsou rovněž trvalé, a to stejného typu: trvalé nulové/nenulové, periodické/neperiodické Důkaz: Nechť je nějaký stav dosažitelný z trvalého stavu . Musí tedy existovat nejmenší takové, že platí pro vhodnou posloupnost stavů . V této posloupnosti se nemůže vyskytnout stav , protože jinak by cesta k němu byla kratší. Máme . Stav musí být dosažitelný z , neboť kdyby nebyl, pak by opak měl za následek platnost nerovnosti Lze proto nalézt takové , pro které Pro pak platí . Odtud dostáváme implikace → ↔ . Vidíme, že je trvalý stav,který je nulový právě tehdy, když též je nulový stav. □ . Pokud se chceme v důkazu vyhnout operování s mocninnými řadami, lze uplatnit velmi podobné tvrzení (převzaté v textu S.Karlin-H.M.Taylor str.66) Věta 4* Nechť jsou stavy a sousledné. Pak jestliže je stav trvalý, potom je také stav trvalý. Důkaz Protože jsou stavy a sousledné, existují taková, že jakož i . Nechť . Zřejmě platí . Pokud tuto nerovnost „nasoučtujeme“, dostaneme . Odtud je zřejmé, že pokud diverguje, potom také diverguje. □ . Dále uvedeme několik tvrzení, které vypovídají o tom, že ne v každém Markovově řetězci musí, resp. mohou být obsaženy stavy všech dosud uvedených typů. O tom, že v konečném Markovově řetězci (v řetězci s konečným počtem stavů ) je okruh přípustných stavů dosti omezen , vypovídají následující dvě tvrzení: Věta 5 V konečném Markovově řetězci nemohou být přítomny nulové trvalé stavy. Důkaz: Mějme takový řetězec a předpokládejme, že je jeho trvalý nulový stav. Pro každý stav dosažitelný z platí dle důkazu Věty 1 pro všechna n: . Jestliže je nedosažitelné z , pak pro Z (5) proto plyne , Sečtením pro všechny stavy dostáváme: [7] , . Předpoklad o přítomnosti nulových stavů tedy vede ke sporu. □ . Konečný Markovův řetězec může tedy obsahovat pouze stavy trvalé nenulové a stavy přechodné. Věta 6 V konečném Markovově řetězci nemohou být všechny stavy přechodné. Důkaz: Bude doplněn později □ . Důsledkem obou předchozích vět (5,6) je závěr, že v Markovově řetězci s konečným počtem stavů musí být vždy přítomen aspoň 1 stav trvalý nenulový. Tvrzení 11 Jestliže jsou stavy trvalé, avšak náležející do odlišných tříd, potom platí (1.32) pro všechna [8] Tvrzení 12 Jestliže stav je přechodný, potom (1.33) pro všechna [9] Následující věta ukáže, že pokud je „trvalost“ vlastnost určitého stavu, potom se tento stav bude vyskytovat nekonečněkrát často s pravděpodobností 1: Věta 7: Stav je trvalý [reccurent] nebo přechodný [transient] podle toho, zda platí nebo (pozn.: jiná možnost se nemůže vyskytnout, kde definujeme jako pravděpodobnost Důkaz: Definujme veličinu předpisem Můžeme psát : , kde . Platnost tohoto vzorce je založena na rozkladu události podle doby prvního návratu. Jestliže postupujeme rekurzívně, dostáváme postupně Víme ale, že podle definice platí , z čehož máme Protože ale , máme nebo podle toho, zda nebo , resp.ekvivalentně, dle toho, zda stav je trvalý nebo přechodný. □. Věta 8: Jestliže platí souslednost stavů ( ) a pohybujeme se ve třídě trvalých stavů, pak platí . Dále definujme veličinu Jako přímý důsledek věty 6 dostaneme Důsledek Jestliže platí a jsme ve třídě trvalých stavů, pak platí Důkaz: Je snadné ukázat, že platí a protože j je rovněž trvalý stav, platí podle věty 8 , z čehož plyne . □ . To říká, že stav je přechodný právě tehdy, jestliže (vycházeje ze stavu ) existuje „reziduální“ pravděpodobnost , že se systém do stavu po jakkoliv velkém konečném počtu kroků již nevrátí. Příklad 4 Mějme Markovův proces s maticí pravděpodobností přechodu stavy 0 1 2 3 4 Je zřejmé, že stav č. 2 je absorpční (a tedy trvalý), neboť pokud jednou proces vstoupí do stavu č.2 (třetí řádek matice), pak ho již nikdy neopustí. Stavy č. 3 a 4 jsou přechodné stavy, protože, pokud proces vstoupí do stavu 3,[10] pak existuje kladná pravděpodobnost, že se do něj již nikdy nevrátí.[11] Tato pravděpodobnost je 1/3 ( že proces přejde ze stavu 3 do stavu 2 po jednom kroku). Pokud proces opustí stav 4, nemůže se již do něho nikdy později vrátit (stav 4 je zřejmě přechodný). Když proces vstoupí do stavu 2[12], nadále již v něm zůstane Stavy 0 a 1 jsou trvalé stavy. Jak bylo konstatováno dříve, k tomu, abychom to prokázali, postačí ukázat, že platí , resp. že To je však obecně obtížné, a proto je žádoucí vyvinout alternativní test: Nutná a postačující podmínka, aby byl stav trvalý je, aby pravděpodobnost daná součtem nekonečné řady konvergovala. Bohužel, i toto kritérium je obtížné použít, takže bude nutno uplatnit ještě jiné kritérium, které uvedeme později. Všimněme si ale, že matice pravděpodobností přechodu po n krocích bude mít pro tento případ vždy podobu: kde symbol *** označuje kladná čísla. Zde je intuitivně zřejmé, že pokud je proces ve stavu 0, vrátí se jednou do stavu 0 (možná projdouce stavem 1) po nějakém počtu kroků. Podobný argument platí pro stav 1. ________________________________ [1] Anglické pojmenování není obsahem ekvivalentní českému, ale v češtině vyjadřuje pojem rekurentní jev obecnější charakteristiku než je jev či stav trvalý. [2] To je ovšem dosti neobvyklá, i když možná situace. [3] Znamená to tedy, že periodický stav má nenulovou pravděpodobnost výskytu po libovolném počtu kroků, které jsou násobkem „jeho“ periody, V ostatních časových okamžicích může být pravděpodobnost jeho výskytu kladná i nulová. [4] V některých textech se do pojmu ergodicity nezahrnuje neperiodičnost stavu. [5] Protože u trvalého stavu platí , jinak obecně . [6] V obojím případě využíváme platnosti [7] První z rovností platí v důsledku toho, že stav i* je trvalý nulový. [8] Plyne to přímo z definice třídy (jsou-li aspoň 2). [9] Plyne to z toho, že pravděpodobnost výskytu procesu v přechodném stavu po velkém počtu přechodů směřuje k nule. [10] Zůstává v něm s pravděpodobností 1, přechod nikam jinam není možný [11] Do stavu 4 se nedá odnikud vstoupit, do stavu 3 pouze z něho samého a stavu 2. [12] Po jednom kroku je to možné pouze ze stavu 3, a to s pravděpodobností 1/3.