Ustálený markovský řetězec
- Autor:
- Šárka Voráčová
- Téma:
- Pravděpodobnost
Petriho síť na obrázku modeluje markovský řetězec s diskrétním časem (DTMC). Systém je v jednom ze čtyř stavů, pokud je žeton v příslušném místě. Napište matici přechodu P a určete rozložení pravděpodobnosti stavů po n krocích (=odpalech), pokud je systém na začátku ve stavu P0, tj.
a0 = (1, 0, 0, 0)
Proces vykazuje jedinou náhodnost a to při cestě z místa P0. S pravděpodobností 0,5 se může dostat do míst P1 nebo P3. Proto má matice přechodu P v prvním řádku na druhém a třetím místě hodnotu 0,5. V ostatních řádcích je 1 na místě jisté cesty.
Matice P je stochastická, řádkové součty jsou 1. Rozložení pravděpodonosti po n krocích získáme z matice přechodu P a z počátečního rozdělení a0. Platí
an = a0 . Pn
Zjistíme, že se zvyšujícím se počtem kroků systém konverguje k rozložení pravděpodobnostian = (0,29; 0,29; 0,29; 0,14)
Říkáme, že systém je ustálený. Limitní rozdělení pravděpodobnosti v takovém případě můžeme vypočítat i jako řešení homogenní soustavy lineárních rovnica = aP.
1.Postup: Pokud je matice P malá, se spoustou 0, je možné řešení vypočítat přímo dosazením, jako v tomto případě. Označme složky hledaného ustáleného rozložení pravděpodobnosti xi, tj. a = (x1, x2, x3, x4). Dosazením do vektorové rovnice a = aPPorovnáním odpovídajících složek dostaneme čtyři závislé rovnice
x1 = x3 x2 = 0.5x1+ x4 x3 = x2 x4 = 0.5x1
Odtud x1 = x2 = x3 = 2x4 a všechna řešení musí být tvaru (2t, 2t, 2t, t). Z nich vybereme to, jehož složky dávají v součtu jistotu, tj. . Limitní rodělení pravděpodobnosti jePoznámka: Po rozepsání vektorové rovnice do složek, můžeme všechny rovnic přepsat do okénka Wolfram Alpha i s přidanou normalizační podmínkou x1=x3, x2=x1/2+x4, x3=x2,x4=x1/2, x1+x2+x3+x4=1.
2. postup: V systému s více stavy již musíme použít výpočetní software a příkaz pro Gaussovu eliminaci. V GeoGebře použijeme příkaz
SchodovityTvar(P).
Kde E je jednotková matice příslušného rozměru. V appletu výše je matice PT - E pojmenovaná PtminusE, její převedení na ekvivalentní jednodušší tvar PtminusEs. Nyní již můžeme rozepsat zpět do rovnic a zapsat jednoparametrický systém řešení, ze kterého vybereme jediné řešení, které splňuje podmínku pro rozdělení pravděpodobnosti. Součet všech složek vektoru a musí být 1.
Limitní rodělení pravděpodobnosti je
Úloha 2: Ustálený DTMC s pěti stavy
Markovský řetězec s pěti stavy je dán maticí přechodu P a počátečním rozložením pravděpodobností a0. Z jedničky na pozici P(5,5) vidíme, že pátý stav je absorpční. Jelikož je to jediný absorpční stav dosažitelný ze všech ostatních stavů, je systém ustálený, jak se můžete přesvědčit z výpočtu an změnou posuvníku pro krok n.
Stacionární řešení
Určete stacionární řešení z matice PTminES upravené ekvivalentními úpravami na schodovitý tvar.
Limitní rozdělení pravděpodobnosti an
Změnou posuvníku n získáte rozdělení pravděpodobnosti stavů po n krocích ve vektroru an. Odhadněte jeho limitu pro n→∞.