P4 Rozložitelné a nerozložitelné Markovovy řetězce 1.12 Rozložitelné Markovovy řetězce Skupinu vzájemně sousledných stavů nazýváme uzavřenou třídou = podřetězcem. Jestliže je v řetězci taková třída pouze jedna, nazýváme tento řetězec nerozložitelný (ireducibilní) [irreducible chain] . Tvoří-li všechny stavy řetězce uzavřenou třídu a jsou-li tyto stavy ergodické, nazýváme tento řetězec regulární [regular chain]. Definice 14 Markovův řetězec se nazývá rozložitelný [reducible chain], jestliže v něm existuje více než jedna množina (podřetězec) takovýchto sousledných stavů. Je-li řetězec nerozložitelný, znamená to, že v matici pravděpodobností přechodu lze nalézt dílčí submatice s nulovými prvky. Často se lze u konečných rozložitelných řetězců setkat s těmi podobami matice : (A) , kde jsou čtvercové submatice Oba podřetězce jsou zde tvořeny oddělenými skupinami stavů, kdy stavy jednoho podřetězce nejsou dosažitelné ze stavů druhého podřetězce (a tedy ani nemohou být s nimi sousledné).[1] (B) , kde jsou čtvercové submatice Zde matice obsahuje trvalé stavy a matice přechodné stavy. Matice zde představuje matici pravděpodobností přechodu ze stavů přechodných do stavů trvalých (opačná cesta není přirozeně možná, což je indikováno nulovou maticí v pravém horním poli). Je-li matice rozložitelná na tvar (C) ,kde obě „ “ jsou nulové čtvercové submatice, bude systém oscilovat po každém kroku mezi dvěma množinami stavů a příslušná matice bude popisovat periodický řetězec. Není-li matice P rozložitelná, jedná se o regulární řetězec, kde všechny jeho stavy tvoří uzavřený celek[2]. 1.13 Regulární Markovovy řetězce Definice 15 Matici pravděpodobností přechodu nazveme regulární, je-li pro určité konečné bez nulových prvků. Zároveň platí, že matice je regulární, jestliže není rozložitelná na tvary (A), (B),(C). Lze dokázat, že matice konverguje při k limitní matici typu , jejíž řádky tvoří shodné řádkové vektory , které nazýváme limitní stacionární vektory Věta 9 Pro regulární matici platí tyto základní vlastnosti: 1. Je-li regulární, je limitní matice a je limitní vektor, pak s rostoucím se blíží k , ať je výchozí vektor jakýkoliv: . 2. vektor jediný, pro který platí ; je tedy určen jednoznačně. 3. Platí, že . Limitní vektor je možné určit následujícím způsobem: Předpokládáme-li, že se v případě regulárních řetězců mohou všechny stavy v budoucnosti stále vyskytovat, tj. platí , existuje limitní rozdělení absolutních pravděpodobností vektoru . Potom platí (1.34) , kde vektor je limitní stacionární vektor. Složky vektoru a lze interpretovat, jako podíly (z celku 1) z celkové doby, kterou systém stráví ve stavech v průběhu dost dlouhého časového období. Protože platí (1.35A) , můžeme po limitním přechodu tento vztah psát ve tvaru (1.35B) . Rovnice této soustavy o M neznámých jsou lineárně závislé a proto nelze bez dalšího nalézt jediné řešení. Nalézt jednoznačné řešení nicméně umožňuje zavedení další přirozené podmínky, která plyne z toho, že stacionární pravděpodobnosti stavů tvoří úplnou soustavu jevů, tj. podmínky . Výpočty stacionárních pravděpodobností získáme tedy řešením soustavy rovnic , resp. (1.35C) . s dodatečnou podmínkou . V příkladě se zásobami kamer[3] lze ukázat, že matice pravděpodobností přechodu po 8 krocích má tvar: . Zaznamenejme pozoruhodnou skutečnost, že každý ze čtyř řádků má identické prvky. To znamená, že pravděpodobnost toho, že systém je po 8 týdnech ve stavu j se zdá být nezávislá na počátečním stavu zásob ! Jinými slovy, jeví se, že existuje nějaká limitní pravděpodobnost, že systém bude ve stavu j po velkém počtu přechodů a že takováto pravděpodobnost je nezávislá na počátečním rozdělení pravděpodobností stavů. Tento důležitý výsledek vztažený k dlouhodobému chování Markovových řetězců s konečným počtem stavů nyní ukážeme: Markovova řetězce a jsou rovna převráceným hodnotám středních dob návratu, tj. (1.36) pro j=0,1,...,M. Pojem stacionární v tomto případě znamená, že pravděpodobnost toho, že se proces nachází v určitém stavu, řekněme j, po velkém počtu přechodů směřuje k hodnotě , která je nezávislá na počátečním rozdělení pravděpodobnosti výskytu stavů. Je důležité dodat, že stacionární pravděpodobnost neznamená, že se proces usídlí v jednom stavu. Naopak, proces pokračuje v uskutečňování přechodů ze stavu do stavu a v jakémkoliv kroku n je pravděpodobnost přechodu ze stavu do stavu stále . Limitní mohou být také interpretovány jako stacionární pravděpodobnosti (nezaměňovat se stacionárními pravděpodobnostmi přechodu) . Jestliže počáteční absolutní pravděpodobnost toho, že jsme ve stavu je (tj. pro všechna j, pak absolutní pravděpodobnost výskytu procesu ve stavu v čase n=1,2,... je také dána těmito tj Zmiňme, že stacionární pravděpodobnosti sestávají z M+2 rovnic pro M+1 neznámých. Protože existuje jediné řešení, přinejmenším jedna rovnice musí být redundantní a může tedy být škrtnuta. Nemůže to ale být rovnice , protože řešení by evidentně také vyhovovalo ostatním M+1 rovnicím. Dále: řešení jiných M+1 stacionárních rovnic je jednoznačné až na multiplikativní konstantu, a právě díky zmíněné poslední rovnici je toto řešení „tlačeno“ k tomu, aby šlo o pravděpodobnostní rozdělení. V příkladě se zásobami kamer mohou být rovnice stacionárního stavu vyjádřeny jako Dosazení hodnot za do těchto pěti rovnic vede ke vztahům (Algebraické) řešení těchto čtyř rovnic vede k simultánnímu řešení kterýžto výsledek je (téměř) shodný s výpočtem matice . Takže po mnoha týdnech se pravděpodobnosti výskytu žádné, jedné, dvou a tří kamer v prodejně budou přibližovat k hodnotám 0,285, 0,285 0,264 a 0,166. Odpovídající střední roby návratu [expected recurrence times] jsou : týdnů týdnů týdnů týdnů ________________________________ [1] V maticích P1 a P2 mohou být vedle trvalých stavů přítomny rovněž stavy přechodné. [2] Každý stav řetězce je dosažitelný z každého jiného stavu. [3] V této části textu jsou stacionární pravděpodobnosti výše zavedené jako značeny .