Przykłady łańcuchów Markowa

Ten artykuł zawiera przykłady łańcuchów Markowa i procesów Markowa w działaniu.

Wszystkie przykłady znajdują się w przeliczalnej przestrzeni stanów . Aby zapoznać się z przeglądem łańcuchów Markowa w ogólnej przestrzeni stanów, zobacz Łańcuchy Markowa w mierzalnej przestrzeni stanów .

Czas dyskretny

Gry planszowe z kostkami

Gra w węże i drabiny lub jakakolwiek inna gra, której ruchy są całkowicie zdeterminowane przez kości , jest łańcuchem Markowa, a nawet absorbującym łańcuchem Markowa . Kontrastuje to z grami karcianymi, takimi jak blackjack , gdzie karty reprezentują „pamięć” poprzednich ruchów. Aby zobaczyć różnicę, rozważ prawdopodobieństwo wystąpienia określonego zdarzenia w grze. We wspomnianych grach w kości liczy się tylko aktualny stan planszy. Następny stan planszy zależy od aktualnego stanu i następnego rzutu kośćmi. To nie zależy od tego, jak rzeczy doszły do obecnego stanu. W grze takiej jak blackjack gracz może zyskać przewagę, pamiętając, które karty zostały już pokazane (a więc których nie ma już w talii), więc następny stan (lub ręka) gry nie jest niezależny od przeszłe stany.

Łańcuchy Markowa błądzenia losowego

Błądzenie losowe z tendencją do centrum

Rozważmy błądzenie losowe po osi liczbowej, gdzie przy każdym kroku pozycja (nazwijmy ją x ) może zmienić się o +1 (w prawo) lub −1 (w lewo) z prawdopodobieństwem:

{\dfrac {x}{c+|x|}}\right)}

{\ Displaystyle P _ {\ operatorname {ruch ~ w lewo}} = {\ dfrac {1} {2}} + {\ dfrac {1}{2}}\left

{\ Displaystyle P _ {\ operatorname {ruch ~ w prawo}} = 1-P _ {\ operatorname {ruch ~ w lewo}}}

(gdzie c jest stałą większą od 0)

Na przykład, jeśli stała c , równa się 1, to prawdopodobieństwa ruchu w lewo na pozycjach x = −2,−1,0,1,2 są określone przez ${\ Displaystyle {\ dfrac {1} {6}} {\ dfrac {1} {4}} {\ dfrac {1} {2}} {\ dfrac {3} {4}} { \dfrac {5}{6}}}$ odpowiednio. Błądzenie losowe ma efekt centrowania, który słabnie wraz ze c .

Ponieważ prawdopodobieństwa zależą tylko od aktualnej pozycji (wartość x ), a nie od jakichkolwiek wcześniejszych pozycji, ten obciążony błąd losowy spełnia definicję łańcucha Markowa.

Hazard

Załóżmy, że zaczynasz z 10 $ i stawiasz 1 $ na niekończący się, uczciwy rzut monetą w nieskończoność lub do momentu, gdy stracisz wszystkie swoje pieniądze. X ${\ Displaystyle X_ {n}}$ ${\ Displaystyle X_ {0} = 10}$ liczbę dolarów, które masz po n rzutach, z , to sekwencja ${\ displaystyle \{X_{n}:n\in \mathbb {N} \}}$ jest procesem Markowa. Jeśli wiem, że masz teraz 12 $, to można by się spodziewać, że przy równym kursie będziesz miał 11 $ lub 13 $ po następnym rzucie. To przypuszczenie nie jest poprawiane przez dodatkową wiedzę, że zaczynałeś od 10 $, potem wzrosłeś do 11 $, spadłeś do 10 $, do 11 $, a następnie do 12 $. Fakt, że zgadywanie nie jest lepsze dzięki znajomości wcześniejszych rzutów, pokazuje właściwość Markowa , niepamięćową właściwość procesu stochastycznego.

Prosty model pogody

Prawdopodobieństwa warunków pogodowych (modelowanych jako deszczowe lub słoneczne), biorąc pod uwagę pogodę poprzedniego dnia, można przedstawić za pomocą macierzy przejść :

{\ Displaystyle P = {\ rozpocząć {bmatrix} 0,9 i 0,1 \\ 0,5 i 0,5 \ koniec {bmatrix}}}

Macierz P reprezentuje model pogody, w którym z 90% prawdopodobieństwem po słonecznym dniu nastąpi kolejny słoneczny dzień, a po deszczowym dniu z 50% prawdopodobieństwem nastąpi kolejny deszczowy dzień. Kolumny mogą być oznaczone jako „słonecznie” i „deszczowo”, a wiersze mogą być oznaczone w tej samej kolejności.

Powyższa macierz w postaci wykresu.

( P ) _ij to prawdopodobieństwo, że jeśli dany dzień jest typu i , nastąpi po nim dzień typu j .

Zauważ, że wiersze P sumują się do 1: to dlatego, że P jest macierzą stochastyczną .

Przewidywanie pogody

Wiadomo, że pogoda w dniu 0 (dziś) jest słoneczna. Jest to reprezentowane przez wektor stanu początkowego, w którym wpis „słoneczny” to 100%, a wpis „deszczowy” to 0%:

{\ Displaystyle \ mathbf {x} ^ {(0)} = {\ rozpocząć {bmatrix} 1 i 0 \ koniec {bmatrix}}}

Pogodę pierwszego dnia (jutro) można przewidzieć, mnożąc wektor stanu z dnia 0 przez macierz przejść:

{\ Displaystyle \ mathbf {x} ^ {(1)} = \ mathbf {x} ^ {(0)} P={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.9&0.1\end {bmacierz}}}

Zatem istnieje 90% szans, że pierwszy dzień również będzie słoneczny.

Pogodę drugiego dnia (pojutrze) można przewidzieć w ten sam sposób, na podstawie wektora stanu, który obliczyliśmy dla dnia 1:

{\ 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}}}

Lub

{\ 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{bmacierz}}}

Ogólne zasady dnia n to:

{\ Displaystyle \ mathbf {x} ^ {(n)} = \ mathbf {x} ^ {(n-1)} P}

{\ Displaystyle \ mathbf {x} ^ {(n)} = \ mathbf {x} ^ {(0)} P ^ {n}}

Stały stan pogody

W tym przykładzie prognozy pogody dla bardziej odległych dni zmieniają się coraz mniej każdego kolejnego dnia i zmierzają w kierunku wektora stanu ustalonego . Ten wektor reprezentuje prawdopodobieństwo słonecznej i deszczowej pogody we wszystkie dni i jest niezależny od początkowej pogody.

Wektor stanu ustalonego jest zdefiniowany jako:

{\ Displaystyle \ mathbf {q} = \ lim _ {n \ do \ infty} \ mathbf {x} ^ {(n)}}

ale zbiega się do ściśle dodatniego wektora tylko wtedy, gdy P jest regularną macierzą przejść (to znaczy istnieje co najmniej jeden P ⁿ ze wszystkimi wpisami niezerowymi).

Ponieważ q jest niezależne od warunków początkowych, musi pozostać niezmienione po przekształceniu przez P . To czyni go wektorem własnym (o wartości własnej 1) i oznacza, że można go wyprowadzić z P .

Mówiąc językiem laika, wektor stanu ustalonego jest wektorem, który po pomnożeniu przez P daje dokładnie ten sam wektor. W przypadku przykładu pogody możemy użyć tego do utworzenia równania macierzowego:

{\ Displaystyle {\ rozpocząć {wyrównane} P & = {\ rozpocząć {bmatrix} 0,9 i 0 .1\\0,5&0,5\end{bmatrix}}\\\mathbf {q} P&=\mathbf {q} &&{\text{(}}\mathbf {q} {\text{ nie zmienia się o }} 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}}&={\begin{bmatrix}0&0\end{bmatrix}}\\-0.1q_{1} +0,5q_{2}&=0\end{wyrównane}}}

a ponieważ są one wektorem prawdopodobieństwa, wiemy o tym

{\ Displaystyle q_ {1} + q_ {2} = 1.}

Rozwiązanie tej pary równoczesnych równań daje wektor stanu ustalonego:

{\ Displaystyle {\ rozpocząć {bmatrix} q_ {1} & q_ {2} \ koniec {bmatrix}} = {\ rozpocząć {bmatrix} 0,833 i 0,167 \ koniec {bmatrix} }}

Podsumowując, w dłuższej perspektywie około 83,3% dni jest słonecznych. Ważne jest, aby zdać sobie sprawę, że nie wszystkie procesy Markowa mają wektor stanu ustalonego. W szczególności macierz przejść musi być regularna . W przeciwnym razie wektory stanu będą oscylować w czasie bez zbieżności.

Giełda Papierów Wartościowych

Za pomocą skierowanego wykresu przedstawiono prawdopodobieństwa możliwych stanów hipotetycznej giełdy papierów wartościowych. Macierz po lewej pokazuje, w jaki sposób prawdopodobieństwa odpowiadające różnym stanom można ułożyć w macierz.

Diagram stanu dla prostego przykładu pokazano na rysunku po prawej stronie, używając skierowanego wykresu do zobrazowania przejść stanów . Stany reprezentują, czy hipotetyczna giełda wykazuje hossę , bessę , czy też stagnację w danym tygodniu. Zgodnie z wykresem, po tygodniu hossy następuje kolejny tydzień hossy w 90% przypadków, tydzień niedźwiedzia w 7,5% przypadków i tydzień stagnacji w pozostałych 2,5% przypadków. Etykietowanie przestrzeni stanów {1 = byk, 2 = niedźwiedź, 3 = stagnacja} macierz przejścia dla tego przykładu to

{\ Displaystyle P = {\ początek {bmatrix} 0,9 i 0,075 i 0,025 \\ 0,15 i 0,8 i 0,05 \\ 0,25 i 0,25 i 0,5 \ koniec {bmatrix}}.}

Rozkład po stanach można zapisać jako stochastyczny wektor rzędowy $x$ z zależnością $x (n + 1) = x (n) P$ . Więc jeśli w chwili $n$ system jest w stanie $x (n)$ , to trzy okresy później, w chwili $n + 3$ rozkład jest

{\ Displaystyle {\ rozpocząć {wyrównane} x ^ {(n + 3)} & = x ^ {(n + 2)} P = \ lewo (x ^ {(n + 1)} P \ prawo) P \ \\\&=x^{(n+1)}P^{2}=\left(x^{(n)}P\right)P^{2}\\&=x^{(n)} P^{3}\\\koniec{wyrównany}}}

Predykcja łańcuchów Markowa na 3 dyskretnych krokach na podstawie macierzy przejścia z przykładu po lewej stronie.

W szczególności, jeśli w chwili $n$ system jest w stanie 2 (niedźwiedzi), to w chwili $n + 3$ rozkład jest

{\ Displaystyle {\ rozpocząć {wyrównane} x ^ {(n + 3)} & = {\ rozpocząć {bmatrix} 0 i 1 i 0 \ koniec {bmatrix}} {\ rozpocząć {bmatrix} 0,9 i 0,075 i 0,025 \\ 0,15 i 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{wyrównane}}}

Przewidywanie łańcuchów Markowa na 50 dyskretnych krokach. Ponownie używana jest macierz przejścia z lewej strony.

Korzystając z macierzy przejść, można obliczyć na przykład długoterminowy ułamek tygodni, w których rynek znajduje się w stagnacji, lub średnią liczbę tygodni potrzebnych do przejścia ze stagnacji do hossy. Korzystając z prawdopodobieństw przejścia, prawdopodobieństwa stanu ustalonego wskazują, że 62,5% tygodni będzie w okresie hossy, 31,25% tygodni będzie w okresie niedźwiedzia, a 6,25% tygodni będzie w stagnacji, ponieważ:

{\ Displaystyle \ lim _ {N \ do \ infty} \, P ^ {N} = {\ rozpocząć {bmatrix} 0,625 i 0,3125 &0. 0625\\0,625&0,3125&0,0625\\0,625&0,3125&0,0625\koniec{bmacierz}}}

Dokładne rozwinięcie i wiele przykładów można znaleźć w internetowej monografii Meyn & Tweedie 2005.

Maszyna o skończonych stanach może być używana jako reprezentacja łańcucha Markowa. Zakładając sekwencję niezależnych i identycznie rozłożonych sygnałów wejściowych (na przykład symboli z alfabetu binarnego wybranych przez rzuty monetą), jeśli maszyna jest w stanie y w chwili n , to prawdopodobieństwo, że przejdzie do stanu x w chwili n + 1 zależy tylko od aktualnego stanu.

Czas ciągły

Proces narodzin i śmierci

Jeśli ktoś wrzuci do piekarnika sto ziaren popcornu, z których każde pęka w niezależnym czasie o rozkładzie wykładniczym , byłby to proces Markowa w czasie ciągłym . Jeśli $oznacza$ liczbę jąder, które pojawiły się do czasu t , problem można jako znalezienie liczby jąder, które pojawią się w późniejszym czasie Jedyne, co trzeba wiedzieć, to liczba jąder, które wyskoczyły przed czasem „t”. Nie trzeba wiedzieć, kiedy wyskoczyły, więc wiedza $istotna$ poprzednich czasach „t” nie jest

Opisany tutaj proces jest przybliżeniem procesu punktu Poissona – procesy Poissona są również procesami Markowa.

Zobacz też

^ Øksendal, BK (Bernt Karsten), 1945- (2003). Równania różniczkowe stochastyczne: wprowadzenie z aplikacjami (wyd. 6). Berlin: Springer. ISBN 3540047581 . OCLC 52203046 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )
^ Gagniuc, Paweł A. (2017). Łańcuchy Markowa: od teorii do implementacji i eksperymentów . USA, NJ: John Wiley & Sons. s. 1–235. ISBN 978-1-119-38755-8 .
^ ^abc ^{Van Kampen, NG}⁽ 2007). Procesy stochastyczne w fizyce i chemii . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .
^ ^a ^b ^c ^d Van Kampen, NG (2007). Procesy stochastyczne w fizyce i chemii . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .
^ „Ustalanie (stan) z procesami Markowa” . Korepetytorzy z Bloomingtona.
^ ^ab ^Gagniuc , Paul A. (2017). Łańcuchy Markowa: od teorii do implementacji i eksperymentów . Hoboken, NJ: John Wiley & Sons. s. 131–163. ISBN 9781119387572 . OCLC 982373850 .
^ SP Meyn i RL Tweedie, 2005. Łańcuchy Markowa i stabilność stochastyczna zarchiwizowane 03.09.2013 w Wayback Machine

Linki zewnętrzne

Monopol jako łańcuch Markowa

[:3-1] Øksendal, BK (Bernt Karsten), 1945- (2003). Równania różniczkowe stochastyczne: wprowadzenie z aplikacjami (wyd. 6). Berlin: Springer. ISBN 3540047581 . OCLC 52203046 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )

[:02-2] Gagniuc, Paweł A. (2017). Łańcuchy Markowa: od teorii do implementacji i eksperymentów . USA, NJ: John Wiley & Sons. s. 1–235. ISBN 978-1-119-38755-8 .

[:0-3] {Van Kampen, NG}⁽ 2007). Procesy stochastyczne w fizyce i chemii . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .

[:1-4] Van Kampen, NG (2007). Procesy stochastyczne w fizyce i chemii . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .

[5] „Ustalanie (stan) z procesami Markowa” . Korepetytorzy z Bloomingtona.

[:2-6] Gagniuc , Paul A. (2017). Łańcuchy Markowa: od teorii do implementacji i eksperymentów . Hoboken, NJ: John Wiley & Sons. s. 131–163. ISBN 9781119387572 . OCLC 982373850 .

[MCSS-7] SP Meyn i RL Tweedie, 2005. Łańcuchy Markowa i stabilność stochastyczna zarchiwizowane 03.09.2013 w Wayback Machine