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: T1. 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: . T2. vektor jediný, pro který platí ; je tedy určen jednoznačně. T3. 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 . Dodatek: T3*. Pro limitní vektor a libovolnou n-tou mocninu matice prsti přechodu platí . Ověření vlastnosti T3*: Protože podle (1.35B) platí dostaneme postupně : □ . Důležitá poznámka: Pro limitní matici platí a současně pro i,j,s = 1,2,,...M (shoda po řádcích) , tedy matice má rovněž stejné řádky. Rozšířením máme: , tedy matice má rovněž stejné řádky. Pro limitní matici A tedy platí . V příkladě 5 se zásobami max. 3 kamer[1] 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á (po zaokrouhlení) identické prvky. To znamená, že pravděpodobnost toho, že systém je po 8 týdnech ve stavu 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 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í určitých Markovových řetězců s konečným počtem stavů nyní ukážeme: Hodnoty vektoru limitních pravděpodobností Markovova řetězce jsou rovny převráceným hodnotám středních dob návratu příslušného stavu, 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 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 , pak absolutní pravděpodobnost výskytu procesu ve stavu v čase .. 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í kterýchkoliv jiných M+1 stacionárních rovnic je jednoznačné až na multiplikativní konstantu, přičemž 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 (1.37) Dosazení konkrétních hodnot za do těchto pěti rovnic vede ke vztahům (1.38) (Algebraické) řešení těchto čtyř rovnic vede k simultánnímu řešení kterýžto výsledek je již (téměř) shodný s výpočtem prvků matice . Takže po mnoha týdnech provozu prodejny 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í doby návratu [expected recurrence times] jsou : týdnů týdnů týdnů týdnů Interpretace tohoto výsledku je názorná: Průměrná doba v týdnech , kdy se proces vrátí ze stavu úplného vyprodání kamer do téhož stavu je 3,51 týdnů. Shodou okolností jde o stejnou dobu, která představuje průměrnou dobu uplynulou od stavu 1 kamera na prodejně do stejného stavu. V případě návratu do stavu 2 kamer (ze stejného východiska) je tato doba již 3,79 týdnů, zatímco průměrná doba návratu do stavu plné zásoby 3 kamer, pokud ho sledujeme opět ze stejně “plného stavu“ nepatrně přesahuje 6 týdnů. 1.14 Fundamentální matice regulárního řetězce Pomocí limitní matice definujeme fundamentální matici regulárního řetězce, která umožňuje stanovit střední dobu prvého přechodu do určitého stavu . U regulárního řetězce je střední doba setrvání v systému neomezená, neboť každý stav se může opakovat libovolně často.[2] Proto tato charakteristika není zkoumána. Fundamentální matici regulárního řetězce definujeme takto: (1.41) Pro výraz lze použít rozvoje , konvergují-li mocniny k nule. Tato podmínka je splněna, protože . Dále je možno dokázat platnost vztahu a tudíž i vztahu (1.41) . Fundamentální matice má řadu vlastností, kterých lze využít při zkoumání středního počtu průchodů procesu určitým stavem. Uveďme některé vlastnosti fundamentální matice : Věta 9 s tvrzeními T4 Důkaz vlastnosti T4 (DM) v důsledku toho, že platí komutativita V3 : □ . T5 , kde je sloupcový vektor, jehož složky jsou tvořeny samými jedničkami. Důkaz vlastnosti T5 (DM) Pro j-tý prvek vektoru platí: , tedy Pro j-tý prvek vektoru platí: , tedy (protože jak matice , tak limitní matice mají jedničkové řádkové součty). □ . T6 pro řádkový vektor . Důkaz vlastnosti T6 (DM) , protože (vlastnost limitní matice) a stejně tak . □ . T7 Důkaz vlastnosti T7 (VK) Převedením členů na příslušné strany rovnice získáme vztah . □ □. Střední doba prvního přechodu v regulárním řetězci Při realizaci regulárního řetězce se mohou průběžně v čase vyskytovat všechny stavy. Proto nabývají významu charakteristiky udávající střední dobu prvého přechodu do určitého stavu. Označme střední dobu prvního přechodu ze stavu i do stavu k jako . Střední dobu prvého „přechodu“ pro případ (jde vlastně o střední dobu prvého návratu) můžeme vyjádřit jako (1.42) . Setrvá-li proces s pravděpodobností ve stavu , stráví zde jednu časovou jednotku (s pravděpodobností ). Přejde-li s pravděpodobností do stavu trvá první návrat (první přechod z do ) v průměru . V ostatních případech můžeme střední dobu prvního přechodu z i do j vyjádřit jako (1.43) , kde přechod ze stavu do stavu může s pravděpodobností proběhnout hned v prvém kroku (za jednu časovou jednotku) nebo všemi možnými kombinacemi z do , a to buď v jednom kroku nebo ve větším počtu kroků. Úpravou rovnice (1.43) můžeme přejít na tvar (1.43A) . Vyjádříme-li střední dobu prvého přechodu mezi jednotlivými stavy systému pomocí maticového vyjádření, dostáváme (1.44) , kde je matice obsahující jen diagonální prvky matice a je matice tvořená samými jedničkami. Lze tedy psát Vyjádříme-li v explicitním tvaru, dostaneme (1.45) , kde matice je matice obsahující pouze diagonální prvky fundamentální matice . Při stanovení prvků diagonální matice užijeme vztah , kde jsou složky limitního vektoru . Výpočty jednotlivých charakteristik ukážeme dále na příkladě: Příklad Trh práce VK příklad 2.3 Při analýze pracovního trhu mohou jednotliví pracovníci buď - pracovat ve své vlastní profesi - pracovat v jiné profesi - ocitnout se mezi nezaměstnanými Při statistickém sledování souboru pracovníků se ukázalo, že během jednotlivých měsíců došlo ke změnám mezi jednotlivými následovně: Ve své profesi pracovalo i v následujícím měsíci 80% pracovníků, 10% přešlo k jiným povoláním a 10% se stalo nezaměstnanými. Z pracovníků pracujících mimo svou profesi přišlo 10% v následujícím měsíci ke své profesi, 70% zůstalo i nadále pracovat mimo svou profesi a 20% přišlo v následujícím měsíci o práci. Z nezaměstnaných našlo práci ve své profesi 5% osob, 30% nezaměstnaných získalo práci mimo svou profesi a 65% zůstalo i v dalším měsíci nezaměstnanými. Ze zadání úlohy plyne, že matice pravděpodobností přechodu má tvar . Úlohou je stanovit limitní matici , fundamentální matici a matici středních dob prvého přechodu . Ze zadání úlohy je zřejmé, že matice pravděpodobností přechodu je regulární. Limitní vektor a stanovíme řešením soustavy rovnic , kde s respektování podmínky . pro stanovení limitního vektoru a dostaneme po dosazení prvků matice soustavu rovnic: . Jednu z prvních tří rovnic vynecháme a spolu se čtvrtou rovnici řešíme pro neznámé . Dostaneme limitní vektor Limitní matice má přirozeně všechny řádky stejné: Jsou tvořeny prvky limitního vektoru, tedy . K výpočtu fundamentální matice použijeme vztah (1.41) , kde . Zde je vidět, že ne všechny prvky fundamentální matice musí být kladné. Matice totiž jistým způsobem zachycuje „odchylky“ od limitní matice . Matici středních dob prvého přechodu do stavů dostaneme užitím vztahu (1.45) , v němž je jednotková matice, jsou matice obsahující jen diagonální prvky matice a je matice tvořená samými jedničkami, konkrétně tedy . . Při určení prvků diagonální matice M* na hlavní diagonále vycházíme z toho, že pro střední doby prvého návratu platí , kde jsou složky limitního vektoru . Dosazením příslušných matic do vztahu (1.45) dostaneme matici středních dob prvého přechodu M ve tvaru Jestliže tedy pracovník pracuje ve své profesi (stav 1), pak v průměru za 8 měsíců se stane nezaměstnaným. Aparátu, který poskytuje teorie Markovových řetězců, lze často s úspěchem využít při projektování systémů řízení zásob. Postup prezentujeme na dalším příkladě: ________________________________ [1] V této části textu jsou stacionární pravděpodobnosti výše zavedené jako značeny . [2] To je nesprávně řečené a neodpovídá to pojmu trvalého stavu ! Místo toho by mělo být řečeno, že vždy existuje kladná pravděpodobnost přechodu do trvalého stavu v jakkoliv vzdálené budoucnosti.