Příklady markovských řetězců - Examples of Markov chains

Tato stránka obsahuje příklady Markovovy řetězy a Markovovy procesy v akci.

Všechny příklady jsou spočítatelné státní prostor. Přehled markovských řetězců v obecném stavovém prostoru viz Markovovy řetězce na měřitelném stavovém prostoru.

Diskrétní čas

Deskové hry hrané s kostkami

Hra o hadi a žebříky nebo jakoukoli jinou hru, jejíž pohyby jsou zcela určeny kostky je markovský řetězec, opravdu absorbující Markovův řetězec. To je na rozdíl od karetních her, jako jsou blackjack, kde karty představují „paměť“ minulých tahů. Chcete-li vidět rozdíl, zvažte pravděpodobnost určité události ve hře. Ve výše zmíněných kostkových hrách záleží jen na aktuálním stavu herního plánu. Další stav desky závisí na aktuálním stavu a dalším hodu kostkami. Nezáleží na tom, jak se věci dostaly do současného stavu. Ve hře, jako je blackjack, může hráč získat výhodu tím, že si zapamatuje, které karty již byly zobrazeny (a tedy které karty již nejsou v balíčku), takže další stav (nebo kombinace) hry není nezávislý na minulé státy.

Náhodné procházky Markovovy řetězy

Náhodná procházka se středovým předpětím

Zvažte a náhodná procházka na číselné lince, kde je v každém kroku pozice (nazvěte to X) se může změnit o +1 (vpravo) nebo −1 (vlevo) s pravděpodobnostmi:

${ displaystyle P _ { mathrm {move ~ left}} = { dfrac {1} {2}} + { dfrac {1} {2}} left ({ dfrac {x} {c + | x |} }že jo)}$

${ displaystyle P _ { mathrm {tah ~ doprava}} = 1-P _ { mathrm {tah ~ doleva}}}$

(kde C je konstanta větší než 0)

Například pokud konstanta, C, se rovná 1, pravděpodobnosti pohybu doleva na pozicích X = −2, −1,0,1,2 jsou dány vztahem ${ displaystyle { dfrac {1} {6}}, { dfrac {1} {4}}, { dfrac {1} {2}}, { dfrac {3} {4}}, { dfrac {5} {6}}}$ resp. Náhodná chůze má centrující účinek, který oslabuje jako C zvyšuje.

Protože pravděpodobnosti závisí pouze na aktuální poloze (hodnota X) a nikoli na předchozích pozicích, tato vychýlená náhodná procházka splňuje definici Markovova řetězce.

Hazardní hry

Předpokládejme, že začnete s 10 $ a vsadíte 1 $ na nekonečné, spravedlivé, losování na neurčito, nebo dokud nepřijdete o všechny své peníze. Li ${ displaystyle X_ {n}}$ představuje počet dolarů, které máte po n hodí, s ${ displaystyle X_ {0} = 10}$, pak sekvence ${ displaystyle {X_ {n}: n v mathbb {N} }}$ je Markovův proces. Pokud vím, že teď máte 12 $, pak by se dalo očekávat, že se sudými kurzy budete mít po příštím losování 11 $ nebo 13 $. Tento odhad není vylepšen přidanou znalostí, že jste začali s 10 $, poté šli až na 11 $, dolů na 10 $, až 11 $ a pak na 12 $. Skutečnost, že odhad není vylepšen znalostmi dřívějších losování, ukazuje Majetek Markov, paměťová vlastnost stochastického procesu.^[1][2]

Jednoduchý model počasí

Pravděpodobnosti povětrnostních podmínek (modelovaných jako deštivé nebo slunečné), vzhledem k počasí předchozího dne, lze vyjádřit pomocí přechodová matice:^[3]

${ displaystyle P = { začátek {bmatrix} 0,9 & 0,1 0,5 & 0,5 konec {bmatrix}}}$

Matice P představuje model počasí, ve kterém je slunečný den s 90% pravděpodobností následován dalším slunečným dnem a deštivý den je s 50% pravděpodobností následován dalším deštivým dnem.^[3] Sloupce mohou být označeny jako „slunečné“ a „deštivé“ a řádky mohou být označeny ve stejném pořadí.

Výše uvedená matice jako graf.

(P)_{já j} je pravděpodobnost, že pokud je daný den typový i, bude následován dnem psaní j.

Všimněte si, že řádky P součet 1: je to proto P je stochastická matice.^[3]

Předpovídání počasí

Počasí v den 0 (dnes) je známé jako slunečné. To představuje vektor, ve kterém je „slunečný“ vstup 100% a „deštivý“ vstup je 0%:

${ displaystyle mathbf {x} ^ {(0)} = { begin {bmatrix} 1 & 0 end {bmatrix}}}$

Počasí 1. den (zítra) lze předpovědět:

${ displaystyle mathbf {x} ^ {(1)} = mathbf {x} ^ {(0)} P = { begin {bmatrix} 1 & 0 end {bmatrix}} { begin {bmatrix} 0,9 a 0. 1 0,5 & 0,5 end {bmatrix}} = { begin {bmatrix} 0,9 & 0,1 end {bmatrix}}}$

Existuje tedy 90% šance, že 1. den bude také slunečný.

Počasí 2. den (pozítří) lze předpovídat stejným způsobem:

${ displaystyle mathbf {x} ^ {(2)} = mathbf {x} ^ {(1)} P = mathbf {x} ^ {(0)} P ^ {2} = { begin {bmatrix } 1 & 0 end {bmatrix}} { begin {bmatrix} 0,9 & 0,1 0,5 & 0,5 end {bmatrix}} ^ {2} = { begin {bmatrix} 0,86 & 0,14 end {bmatrix} }}$

nebo

${ displaystyle mathbf {x} ^ {(2)} = mathbf {x} ^ {(1)} P = { begin {bmatrix} 0,9 & 0,1 end {bmatrix}} { begin {bmatrix} 0,9 & 0,1 0,5 & 0,5 end {bmatrix}} = { begin {bmatrix} 0,86 & 0,14 end {bmatrix}}}$

Obecná pravidla pro den n jsou:

${ displaystyle mathbf {x} ^ {(n)} = mathbf {x} ^ {(n-1)} P}$

${ displaystyle mathbf {x} ^ {(n)} = mathbf {x} ^ {(0)} P ^ {n}}$

Stabilní stav počasí

V tomto příkladu jsou předpovědi počasí ve vzdálenějších dnech stále nepřesnější a směřují k vektor v ustáleném stavu.^[4] Tento vektor představuje pravděpodobnost slunečného a deštivého počasí po všechny dny a je nezávislý na počátečním počasí.^[4]

Vektor v ustáleném stavu je definován jako:

${ displaystyle mathbf {q} = lim _ {n až infty} mathbf {x} ^ {(n)}}$

ale konverguje k přísně pozitivnímu vektoru, pouze pokud P je regulární přechodová matice (tj. existuje alespoň jedna Pⁿ se všemi nenulovými položkami).

Protože q je nezávislý na počátečních podmínkách, při transformaci pomocí musí být nezměněn P.^[4] Díky tomu je vlastní vektor (s vlastní číslo 1) a znamená, že z něj lze odvodit P.^[4] Příklad počasí:

${ displaystyle { begin {aligned} P & = { begin {bmatrix} 0,9 & 0,1 0,5 & 0,5 end {bmatrix}} mathbf {q} P & = mathbf {q} && { text {(}} mathbf {q} { text {je nezměněn}} P { text {.)}} & = mathbf {q} I mathbf {q} (PI) & = mathbf {0} mathbf {q} left ({ begin {bmatrix} 0,9 & 0,1 0,5 & 0,5 end {bmatrix}} - { begin {bmatrix} 1 & 0 0 & 1 end {bmatrix}} right) & = mathbf {0} mathbf {q} { begin {bmatrix} -0,1 & 0,1 0,5 & -0,5 end {bmatrix}} & = mathbf {0 } { begin {bmatrix} q_ {1} & q_ {2} end {bmatrix}} { begin {bmatrix} -0,1 & 0,1 0,5 & -0,5 end {bmatrix}} & = { začátek {bmatrix} 0 & 0 end {bmatrix}} - 0,1q_ {1} + 0,5q_ {2} & = 0 end {zarovnáno}}}$

a protože jsou vektorem pravděpodobnosti, víme to

${ displaystyle q_ {1} + q_ {2} = 1.}$

Řešení této dvojice simultánních rovnic dává distribuci v ustáleném stavu:

${ displaystyle { begin {bmatrix} q_ {1} & q_ {2} end {bmatrix}} = { begin {bmatrix} 0,833 & 0,167 end {bmatrix}}}$

Závěrem lze říci, že z dlouhodobého hlediska je asi 83,3% dnů slunečných.

Akciový trh

Pomocí směrovaného grafu jsou znázorněny pravděpodobnosti možných stavů, které může hypotetický akciový trh vykazovat. Matice vlevo ukazuje, jak lze uspořádat pravděpodobnosti odpovídající různým stavům v maticové formě.

A stavový diagram jednoduchý příklad je znázorněn na obrázku vpravo a pomocí namířeného grafu k obrázku přechody stavu. Státy představují, zda hypotetický akciový trh vykazuje a býčí trh, medvědí trh, nebo stagnující tržní trend během daného týdne. Podle obrázku býčí týden následuje další býčí týden 90% času, medvědí týden 7,5% času a stagnující týden dalších 2,5% času. Označením stavového prostoru {1 = býk, 2 = medvěd, 3 = stagnující} je přechodová matice pro tento příklad

${ displaystyle P = { begin {bmatrix} 0,9 & 0,075 & 0,025 0,15 & 0,8 & 0,05 0,25 & 0,25 & 0,5 end {bmatrix}}.}$

Distribuci přes stavy lze zapsat jako a stochastický řádek vektor X se vztahem X^(n + 1) = X⁽ⁿ⁾P. Takže pokud včas n systém je ve stavu X⁽ⁿ⁾, poté o tři časová období později n + 3 distribuce je

${ displaystyle { begin {zarovnáno} x ^ {(n + 3)} & = x ^ {(n + 2)} P = left (x ^ {(n + 1)} P right) P & = x ^ {(n + 1)} P ^ {2} = left (x ^ {(n)} P right) P ^ {2} & = x ^ {(n)} P ^ {3} konec {zarovnáno}}}$

Predikce Markovových řetězců ve 3 samostatných krocích na základě matice přechodu z příkladu doleva.^[5]

Zejména pokud včas n systém je ve stavu 2 (medvěd), tedy v čase n + 3 distribuce je

${ displaystyle { begin {aligned} x ^ {(n + 3)} & = { begin {bmatrix} 0 & 1 & 0 end {bmatrix}} { begin {bmatrix} 0,9 & 0,075 & 0,025 0,15 & 0. 8 & 0,05 0,25 & 0,25 & 0,5 end {bmatrix}} ^ {3} [5pt] & = { begin {bmatrix} 0 & 1 & 0 end {bmatrix}} { begin {bmatrix} 0,7745 & 0. 17875 & 0,04675 0,3575 & 0,56825 & 0,07425 0,4675 & 0,37125 & 0,16125 end {bmatrix}} [5pt] & = { begin {bmatrix} 0,3575 & 0,56825 & 0,07425 end {bmatrix }}. end {zarovnáno}}}$

Predikce Markovových řetězců na 50 diskrétních krocích. Opět se používá přechodová matice zleva.^[5]

Pomocí přechodové matice je možné vypočítat například dlouhodobý zlomek týdnů, během nichž trh stagnuje, nebo průměrný počet týdnů, které bude potřeba k přechodu ze stagnujícího na býčí trh. Použitím pravděpodobností přechodu pravděpodobnosti ustáleného stavu naznačují, že 62,5% týdnů bude na býčím trhu, 31,25% týdnů bude na medvědím trhu a 6,25% týdnů bude stagnovat, protože:

${ displaystyle lim _ {N to infty} , P ^ {N} = { begin {bmatrix} 0,625 & 0,3125 & 0,0625 0,625 & 0,3125 & 0,0625 0,625 & 0,3125 & 0,0625 konec {bmatrix}}}$

Důkladný vývoj a mnoho příkladů lze najít v online monografii Meyn & Tweedie 2005.^[6]

A konečný stavový stroj lze použít jako reprezentaci Markovova řetězce. Za předpokladu posloupnosti nezávislé a identicky distribuované vstupní signály (například symboly z binární abecedy vybrané pomocí losování mincí), pokud je stroj ve stavu y v čase n, pak pravděpodobnost, že přejde do stavu X v čase n + 1 závisí pouze na aktuálním stavu.

Kontinuální čas

Proces narození a smrti

Pokud někdo v troubě vyskočí sto jader popcornu, každé jádro vyskočí na nezávislé exponenciálně distribuované čas, pak by to bylo kontinuální Markovův proces. Li ${ displaystyle X_ {t}}$ označuje počet jader, která se časem objevila t, problém lze definovat jako nalezení počtu jader, která se objeví později. Jediné, co člověk potřebuje vědět, je počet jader, která se objevila před časem „t“. Není nutné to vědět když vyskočili, takže věděli ${ displaystyle X_ {t}}$ pro předchozí časy „t“ není relevantní.

Zde popsaný proces je aproximací a Proces Poissonova bodu - Poissonovy procesy jsou také Markovovy procesy.

Viz také

• Mark V. Shaney
• Interagující částicový systém
• Stochastické mobilní automaty

Reference

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Příklady markovských řetězců“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Červen 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

externí odkazy

• Monopol jako markovský řetězec