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) (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) Pravděpodobnost přechodu ze stavu do stavu po n krocích je (1.11B) 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ě k 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 Doba návratu. střední doba prvního návratu Dalším důležitým indikátorem povahy náhodného procesu představovaného Markovovým řetězcem, je doba 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) opět dostat, je užitečné definovat Definice 5 Střední dobou návratu pro daný stav rozumíme střední hodnotu počtu kroků, po kterých lze do tohoto stavu dospět (s příslušnými pravděpodobnostmi ), tedy (1.18) . Přímý výpočet tedy předpokládá znalost všech pravděpodobností po libovolném počtu kroků. To 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 prstí přechodu po n krocích dostaneme jako výpočet n-té mocniny matice prstí 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 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ů.