P2 – Základní charakteristiky stavů Markovova řetězce 1.4 Pravděpodobnost průchodu stavem, resp. přechodu do jiného stavu Významnou úlohu při popisu vlastností markovských řetězců hraje doba průchodu daným stavem ( též doba návratu) (po jednom, resp. po n krocích), resp. doba přechodu do tohoto stavu z jiného stavu (po jednom, resp.n krocích). Podle dříve zavedeného značení příslušných pravděpodobností přechodu po n krocích, resp. návratu do stavu po n krocích značíme (pro j-tý stav) , resp. . Jak dále ukážeme, tyto charakteristiky mají velkou důležitost při klasifikaci stavů řetězce. S ohledem na již zavedené pojmy připomeňme, že Pravděpodobnost návratu do stavu po n krocích je (1.11A) , přičemž (konvence) Pravděpodobnost přechodu ze stavu do stavu po n krocích je (1.11B) , přičemž (konvence) Výpočet těchto pravděpodobnosti se provádí na základě znalosti matice pravděpodobností přechodu po jednom resp. n krocích . Charakter jednotlivých stavu je významně ovlivněn, jak dále ukážeme, chováním posloupnosti ,resp. . Poznamenejme současně, že ani u poměrně jednoduchých tvarů matic pravděpodobností přechodu nemusí být takový výpočet snadnou záležitostí, zvláště existuje-li větší počet možností přechodů. 1.5 Pravděpodobnost prvního průchodu stavem, resp. prvního přechodu do jiného stavu Velmi často je důležité vyslovit tvrzení též o počtu přechodů, které proces uskuteční při přechodu ze stavu do stavu poprvé. Tato délka je nazývána dobou prvního přechodu ze stavu do stavu . Jestliže , pak je tato doba právě rovna počtu přechodů, které se uskuteční, než se proces vrátí do výchozího stavu . V tomto případě se mluví o době návratu [ reccurence time ] . Obecně jsou doby prvního přechodu náhodnými veličinami a mají tedy s tímto spojená pravděpodobnostní rozdělení. Tato pravděpodobnostní rozdělení přirozeně závisí na pravděpodobnostech přechodu procesu ze stavu do stavu. Definice 5 Uvažujme libovolný , pevně zvolený stav . Definujme pro každé přirozené číslo hodnotu (1.12A) Jinými slovy je pravděpodobnost toho, že - vycházeje ze stavu - první návrat do stavu se uskuteční právě po n krocích. Pro n=0 přijímáme konvencí Uvažujme libovolné dva pevně zvolené stavy , . Definujme pro každé přirozené číslo hodnotu (1.12B) Jinými slovy je pravděpodobnost toho, že - vycházeje ze stavu - první přechod ze stavu do stavu se uskuteční právě po n krocích. Pro n=0 přijímáme konvencí Mějme nyní pevně dán stav . Mezi oběma veličinami a lze nalézt rekurzívní vztah, přičemž další mohou být spočteny jako (1.13) pro , s dodefinováním pro všechna . Rovnice (1.13) je odvozena rozkladem události, ze které se spočte podle času prvního návratu do stavu i . Opravdu: uvažujme všechny možné realizace procesu, pro které a první návrat do stavu i se vyskytne právě v k-tém přechodu. Nazvěme tuto událost . Události (k=1,2,...,n) jsou zřejmě vzájemně neslučitelné.[1] Pravděpodobnost události, že první návrat je v k-tém přechodu je podle definice . Ve zbývajících n-k přechodech se zabýváme pouze těmi realizacemi, pro které . S využitím Markovské vlastnosti (1.3) dostaneme pro vztah (1.14) Připomeňme, že přijímáme konvenci . Můžeme proto psát (1.15) . Odtud ,( neboť zřejmě ) až (1.16) Analogicky k (1.13) lze ukázat, že i pravděpodobnosti vyhovují následujícím rekursívním vztahům: , ( neboť zřejmě ) ............................................ (1.17) ( neboť zřejmě ) Znamená to, že pravděpodobnost doby prvního přechodu ze stavu do stavu po n krocích lze spočíst rekurzívně pomocí jednokrokových pravděpodobností přechodu (známe-li je). 1.6 Střední doba čekání (na přechod), střední doba prvního návratu V analýze Markovových řetězců hrají důležitou roli dvě další charakteristiky, které umožňují mj. blíže kategorizovat jednotlivé stavy, jak uvidíme v další části. Definice 6 Označme střední dobu čekání (na přechod ze stavu do stavu ) Ta je definována následovně: (1.18A) , pokud , (1.18B) , pokud , Poznámka/tvrzení: Kdykoliv, když platí pro součet řady , pak vyhovuje jednoznačně rovnici . Druhým indikátorem povahy náhodného procesu představovaného Markovovým řetězcem, je doba prvního návratu do daného stavu určená jako počet kroků, po kterých lze z výchozího stavu opět do tohoto stavu dospět. Vzhledem k tomu, že nezřídka existuje více způsobů, jak se do daného stavu (průchodem přes ostatní stavy systému) opět dostat, je užitečné definovat Definice 7 Když , pak průměrná doba prvního průchodu stavem se nazývá střední doba návratu. Střední dobou prvního návratu pro daný stav rozumíme střední hodnotu počtu kroků, po kterých lze ze stavu do tohoto stavu opět dospět (s příslušnými pravděpodobnostmi ), tedy (1.19) . Přímý výpočet tedy předpokládá znalost všech pravděpodobností po libovolném počtu kroků. To ale nemusí být obecně nijak snadné. V dalším nicméně ukážeme, že v některých případech, kdy existují limitní (stacionární) pravděpodobnosti po ustálení procesu, lze tuto dobu vypočíst vcelku snadno právě z hodnot těchto limitních pravděpodobností. 1.7 Chapman-Kolmogorovovy rovnice V předchozím byly zavedeny n-krokové pravděpodobnosti přechodu (po n-krocích) . Tyto pravděpodobnosti přechodu mohou být užitečné tehdy, jestliže proces je ve stavu i a pravděpodobnost, že proces bude po n obdobích ve stavu j, je žádoucí znát. Chapman-Kolmogorovovy rovnice poskytují metodu pro výpočty těchto pravděpodobností přechodu po n-krocích: (1.21) pro všechna i,j,n a . Tyto rovnice pouze ukazují, že během cesty ze stavu do stavu v n krocích bude proces v nějakém mezilehlém stavu přesně po (menším než ) krocích. Takže je právě podmíněná pravděpodobnost toho, že – vycházeje ze stavu – proces dospěje do stavu po krocích a potom do stavu po krocích. Tedy, shrneme-li tyto podmíněné pravděpodobnosti přes všechna možné stavy musíme dospět k hodnotě Speciální případy a vedou k výrazům: (1.22) (1.23) pro všechna . Tím se stává zřejmým, že pravděpodobnosti přechodu po n-krocích mohou být získány z jednokrokových pravděpodobností přechodu rekurzivně. Pro speciální případ n = 2 dostaneme: Všimněme si, že jsou prvky matice . Avšak musíme rovněž zmínit, že tyto prvky získáme tak, že násobíme matici přechodu po 1 kroku samu se sebou: (1.24) . Obecněji pro libovolné konečné n dostaneme (1.25) . Takže matici pravděpodobností přechodu po n krocích dostaneme jako výpočet n-té mocniny matice pravděpodobností přechodu po jednom kroku. Pro hodnoty n, které nejsou příliš velké, může být matice pravděpodobností přechodu po n krocích spočtena způsobem zde popsaným. Avšak, pokud je n hodně velké, mohou být takové výpočty často obtížné a navíc, v důsledku zaokrouhlovacích chyb může dojít nepřesnostem. ________________________________ [1] Zřejmě, jestliže se první návrat do téhož stavu uskuteční po k-tém kroku, nemůže již tento první návrat následovat v žádném z pozdějších kroků.