Rachunek prawdopodobieństwa i statystyka/Ćwiczenia 10: Łańcuchy Markowa

From Studia Informatyczne

Ćwiczenia

Ćwiczenie 10.1

Opiszemy symulację spaceru losowego za pomocą programu Maple.

Poniższa procedura rysuje położenie cząsteczki w zależności od czasu, podczas spaceru losowego o zadanych parametrach. Funkcja empirical[q,r,p] generuje rozkład, według którego losuje się liczby 1, 2 i 3 z prawdopodobieństwami \displaystyle q, \displaystyle r i \displaystyle p.

 > Spacer := proc(N,p,q,sa,sb,M)
 > local A, B, r, PA, PC, PB, stan, krok, droga:
 > A := -N: B := N: r := 1 -p - q:
 > PA := empirical[0.,sa,1-sa]:
 > PC := empirical[q,r,p]:
 > PB := empirical[1-sb,sb,0.]:
 > stan := 0:
 > droga := stan:
 > from 1 to M do
 > if (A < stan  and stan < B) then
 > krok := random[PC](1) - 2
 > elif
 > stan = A then krok := random[PA](1) - 2
 > elif
 > stan = B then krok := random[PB](1) - 2
 > fi:
 > stan := stan + krok:
 > droga := droga,stan
 >od:}{}
 > plots[pointplot]([seq([i,droga[i+1]],
 > i = 0..nops([droga])-1)],axes=BOXED):
 > end:

Rysunek ze strony {ryssl} został utworzony poleceniem:

 > Spacer(3,0.5,0.5,0.8,0.8,20);

Wygenerujemy teraz cztery ścieżki w spacerze losowym o 300 krokach. Bariery ustawiamy w punktach \displaystyle -10 i \displaystyle 10 oraz przyjmujemy następujące parametry:


\displaystyle p = 0.5, \;q = 0.45, \;r = 0.05,\; sa = sb = 0.8.


Teraz wykonujemy cztery razy polecenie:

 > Spacer(10,0.45,0.5,0.8,0.8,300);

otrzymując następujące wyniki:









Ćwiczenie 10.2

Przyjrzymy się jeszcze raz przykładowi 10.4 przy założeniu, że \displaystyle d \ge 2.

Niech \displaystyle {\mathbf{P}}_d oznacza macierz przejścia naszego łańcucha Markowa. Ustalmy stan \displaystyle i = (i_1, \dots, i_d) \in {\Bbb Z}^d. Zauważmy, że przejście w \displaystyle n krokach ze stanu \displaystyle i z powrotem do tego stanu podczas \displaystyle d-wymiarowego spaceru losowego, jest równoważne przejściom ze stanów \displaystyle i_j do \displaystyle i_j w \displaystyle n krokach podczas niezależnych od siebie jednowymiarowych spacerów losowych. Właśnie korzystając z tej niezależności, dostajemy:


\displaystyle  {\mathbf{P}}^n_d(i)={\mathbf{P}}_d^n(i,i) = {\mathbf{P}}^n(i_1,i_1)\cdot \dots \cdot {\mathbf{P}}^n(i_d,i_d) = \left({\mathbf{P}}^n(0,0)\right)^d.


Korzystając z powyższego wzoru oraz z twierdzenia 10.8, można obliczyć prawdopodobieństwa \displaystyle {\mathbf{P}}_d^n(i) oraz prawdopodobieństwa powrotu w czasie skończonym \displaystyle F^d_n(i) dla \displaystyle d = 2, 3, 4, 5, 6. Warto w tym przypadku znowu skorzystać z programu Maple. Okazuje się, że:

\displaystyle {\mathbf{P}}_2^n(i) \approx \infty, \displaystyle F_2(0) = 1,
\displaystyle {\mathbf{P}}_3^n(i) \approx 0.3932039296, \displaystyle F_3(0) \approx 0.2822299888,
\displaystyle {\mathbf{P}}_4^n(i) \approx 0.1186363871, \displaystyle F_4(0) \approx  0.1060544682,
\displaystyle {\mathbf{P}}_5^n(i) \approx 0.04682554981, \displaystyle F_5(0) \approx 0.04473099631,
\displaystyle {\mathbf{P}}_6^n(i) \approx 0.02046077706, \displaystyle F_6(0) \approx 0.02005052768.

Powyższe wyniki można interpretować w sposób następujący: w przypadku jedno i dwuwymiarowym nie można się podczas spaceru zgubić, natomiast jest to możliwe w wyższych wymiarach, przy czym im wymiar większy, tym prawdopodobieństwo powrotu jest mniejsze.

Ćwiczenie 10.3

Rozważymy pewien spacer losowy z barierami i zbadamy numerycznie zachowanie się kolejnych potęg macierzy przejścia.

Tym razem bariery ustawiamy w punktach \displaystyle -2 oraz \displaystyle 2, zaś parametrami określającymi spacer są:


\displaystyle p = 0.5, \; q = 0.3,\; r = 0.2, \;sa = 0.9,\;sb = 0.1.


Macierz przejścia ma wówczas postać:


\displaystyle \mathbf{P} = \left[ \begin{array} {ccccc}  0.9& 0.1& 0.0& 0.0& 0.0 \\\noalign{\medskip} 0.3& 0.2& 0.5& 0.0& 0.0\\\noalign{\medskip} 0.0& 0.3& 0.2& 0.5& 0.0\\\noalign{\medskip} 0.0& 0.0& 0.3& 0.2& 0.5 \\\noalign{\medskip} 0.0& 0.0& 0.0& 0.9& 0.1\end{array}  \right],


zatem:


\displaystyle  \mathbf{P}^{10} \approx  \left[ \begin{array} {ccccc}  0.545& 0.115& 0.122& 0.145& 0.0731 \\\noalign{\medskip} 0.346& 0.103& 0.159& 0.252& 0.140 \\\noalign{\medskip} 0.219& 0.0956& 0.181& 0.325& 0.180 \\\noalign{\medskip} 0.157& 0.0906& 0.195& 0.353& 0.205 \\\noalign{\medskip} 0.142& 0.0909& 0.194& 0.368& 0.205\end{array}  \right].


Widzimy więc, na przykład, że prawdopodobieństwo przejścia w 10 krokach z lewej bariery do niej samej wynosi około 55, prawdopodobieństwo przejścia z lewej do prawej bariery - około 7, zaś z punktu 0 do niego samego - około 18.

Ćwiczenie 10.4

Zobaczymy, jak funkcjonuje twierdzenie ergodyczne w przypadku spaceru losowego opisanego w ćwiczeniu 10.3.

Macierze \displaystyle \mathbf{P}^{30} i \displaystyle \mathbf{P}^{50} wyglądają następująco:


\displaystyle \mathbf{P}^{30} \approx  \left[ \begin{array} {ccccc}  0.345& 0.103& 0.159& 0.254& 0.140 \\\noalign{\medskip} 0.309& 0.101& 0.165& 0.274& 0.152 \\\noalign{\medskip} 0.286& 0.0992& 0.170& 0.286& 0.159 \\\noalign{\medskip} 0.274& 0.0985& 0.172& 0.293& 0.163 \\\noalign{\medskip} 0.271& 0.0983& 0.172& 0.294& 0.164\end{array}  \right],


\displaystyle  \mathbf{P}^{50} \approx  \left[ \begin{array} {ccccc}  0.309& 0.101& 0.165& 0.274& 0.152 \\\noalign{\medskip} 0.302& 0.100& 0.167& 0.277& 0.154 \\\noalign{\medskip} 0.298& 0.100& 0.167& 0.280& 0.155 \\\noalign{\medskip} 0.296& 0.0998& 0.168& 0.281& 0.156 \\\noalign{\medskip} 0.295& 0.0998& 0.168& 0.281& 0.156\end{array}  \right].


Widzimy, że (tak jak przewiduje twierdzenie) wiersze powyższych macierzy stają się do siebie coraz bardziej podobne.

Znajdziemy teraz rozkład stacjonarny, rozwiązując odpowiedni układ równań postaci \displaystyle Ax = b. Wyznaczamy najpierw \displaystyle A oraz \displaystyle b tak, aby układ ten był równoważny układowi występującemu w twierdzeniu ergodycznym (twierdzenie 10.11). Otrzymujemy:


\displaystyle  A  = \left[ \begin{array} {ccccc} - 0.1& 0.3&0&0&0\\\noalign{\medskip} 0.1&- 0.8& 0.3&0&0\\\noalign{\medskip}0& 0.5&- 0.8& 0.3&0 \\\noalign{\medskip}0&0& 0.5&- 0.8& 0.9\\\noalign{\medskip}0&0&0& 0.5& - 0.9\\\noalign{\medskip}1&1&1&1&1\end{array}  \right], \ \  b = \left[ \begin{array} {c} 0\\\noalign{\medskip}0\\\noalign{\medskip}0\\\noalign{\medskip}0\\\noalign{\medskip}0\\\noalign{\medskip}1 \end{array}  \right].


Łatwo obliczyć (można, oczywiście, skorzystać z programu Maple), że przybliżonym rozwiązaniem naszego układu równań jest następujący wektor \displaystyle \pi:


\displaystyle  \pi \approx  \left[ \begin{array} {c}  0.30037 \\ 0.10012 \\ 0.16687\\ 0.27812\\ 0.15451\end{array}  \right].


Widzimy, że rzeczywiście rozkład stacjonarny niewiele różni się od wierszy macierzy \displaystyle P^{50}.


Ćwiczenie 10.5

Znajdziemy rozkłady i wartości oczekiwane zmiennych losowych \displaystyle X_n (dla niektórych wartości \displaystyle n), oznaczających kapitał Antoniego z przykładu 10.5. Przyjmiemy następujące założenia:


\displaystyle A = 8, \; B=5, \; p = 0.2,\; q = 0.4,


które oznaczają, że Antoni ma większy kapitał, ale Bolesław jest lepszym graczem.

Przypominamy, że mamy tutaj 14 stanów:
\displaystyle E = \{0,1,\dots, 13\}.

Stan "0" oznacza definitywną ruinę Adama, zaś stan "13" - jego całkowitą wygraną, natomiast gra startuje ze stanu "8".

Konstruujemy macierz przejścia \displaystyle \mathbf{P}:


\displaystyle  \mathbf{P} =  \left[ \begin{array} {cccccccccccccc} 1&0&0&0&0&0&0&0&0&0&0&0&0&0 \\\noalign{\medskip} 0.4& 0.4& 0.2&0&0&0&0&0&0&0&0&0&0&0 \\\noalign{\medskip}0& 0.4& 0.4& 0.2&0&0&0&0&0&0&0&0&0&0 \\\noalign{\medskip}0&0& 0.4& 0.4& 0.2&0&0&0&0&0&0&0&0&0 \\\noalign{\medskip}0&0&0& 0.4& 0.4& 0.2&0&0&0&0&0&0&0&0 \\\noalign{\medskip}0&0&0&0& 0.4& 0.4& 0.2&0&0&0&0&0&0&0 \\\noalign{\medskip}0&0&0&0&0& 0.4& 0.4& 0.2&0&0&0&0&0&0 \\\noalign{\medskip}0&0&0&0&0&0& 0.4& 0.4& 0.2&0&0&0&0&0 \\\noalign{\medskip}0&0&0&0&0&0&0& 0.4& 0.4& 0.2&0&0&0&0 \\\noalign{\medskip}0&0&0&0&0&0&0&0& 0.4& 0.4& 0.2&0&0&0 \\\noalign{\medskip}0&0&0&0&0&0&0&0&0& 0.4& 0.4& 0.2&0&0 \\\noalign{\medskip}0&0&0&0&0&0&0&0&0&0& 0.4& 0.4& 0.2&0 \\\noalign{\medskip}0&0&0&0&0&0&0&0&0&0&0& 0.4& 0.4& 0.2 \\\noalign{\medskip}0&0&0&0&0&0&0&0&0&0&0&0&0&1\end{array}  \right]


i zadajemy rozkład początkowy:


\displaystyle  \mathbf{p} =  \left[ \begin{array} {cccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}  \right],


Można teraz łatwo obliczać kolejne rozkłady korzystając z wzoru 10.1 - tak wyglądają, obliczone przy pomocy programu Maple, rozkłady po zakończeniu piątej, dwudziestej i dwusetnej gry:


\displaystyle  \mathbf{p}_5 \approx  \left[ \begin{array} {c} 0 \\ 0 \\ 0 \\ 0.0102 \\ 0.0512 \\ 0.128 \\ 0.205 \\ 0.230 \\ 0.189 \\ 0.115 \\ 0.0512 \\ 0.0160 \\ 0.00320 \\ 0.00032 \end{array}  \right],\;\; \mathbf{p}_{20} \approx  \left[ \begin{array} {c} 0.176\\ 0.0620\\ 0.0954\\ 0.113\\ 0.118\\ 0.112\\ 0.0973 \\ 0.0776\\ 0.0568\\ 0.0378\\ 0.0225\\ 0.0114 \\ 0.00422\\ 0.0165 \end{array}  \right],\;\; \mathbf{p}_{200} \approx  \left[ \begin{array} {c} 0.969\\ 0.0000117\\ 0.0000160\\ 0.0000161\\ 0.0000142\\ 0.0000114\\ 0.854\cdot 10^{-5}\\ 0.604\cdot 10^{-5}\\ 0.402\cdot 10^{-5}\\ 0.250\cdot 10^{-5}\\ 0.143\cdot 10^{-5}\\ 0.707\cdot 10^{-6}\\ 0.257\cdot 10^{-6}\\ 0.0311 \end{array}  \right],


natomiast ich nadzieje matematyczne wynoszą:


\displaystyle {\Bbb E}(X_5) \approx 7.00000,\;\; {\Bbb E}(X_{20}) \approx 4.157931285, \;\; {\Bbb E}(X_{200}) \approx 0.4050783639.


Tak więc po 200 grach mamy prawie 97 pewności, że Adam będzie bankrutem (jest też niewielka nadzieja, że wygra). Jednakże jest niezwykle mało prawdopodobne, że gra w ogóle będzie się toczyć (formalnie toczy się przez cały czas, tylko pozostaje w jednym ze stanów pochłaniających: "0" lub " 13").

Powyższą sytuację ilustruje także następująca animacja rozkładów prawdopodobieństwa zmiennych losowych \displaystyle X_1, \dots, X_{200}:




Zadanie 10.1
Napisz i uruchom program, który dla zadanej macierzy przejścia i zadanego rozkładu prawdopodobieństwa: (a) symuluje łańcuch Markowa, (b) wyznacza kolejne rozkłady prawdopodobieństwa tego łańcucha.

Zadanie 10.2
Rozważmy spacer losowy po okręgu. Załóżmy, że cząsteczka może się znajdować w punktach odpowiadającym kątom \displaystyle \displaystyle k\frac{2\pi}{n}, gdzie \displaystyle n jest ustaloną liczbą naturalną, natomiast \displaystyle k = 0, \dots, n-1. Cząsteczka porusza się zgodnie z ruchem wskazówek zegara z prawdopodobieństwem \displaystyle p, przeciwnie do ruchu wskazówek zegara - z prawdopodobieństwem \displaystyle q i nie zmienia położenia z prawdopodobieństwem \displaystyle r (\displaystyle p + q + r = 1). Wskaż macierz przejścia odpowiedniego łańcucha Markowa.

Zadanie 10.3
Znajdź macierz przejścia oraz rozkład początkowy łańcucha Markowa, który jest modelem zagadnienia opisanego w (patrz zadaniu 5.9).

Zadanie 10.4
Niech \displaystyle \xi_0, \dots , \xi_n będą niezależnymi zmiennymi losowymi, przyjmującymi jedynie wartości całkowite. Załóżmy, że zmienna \displaystyle \xi_0 ma rozkład \displaystyle q_0, natomiast zmienne \displaystyle \xi_1, \dots , \xi_n mają wspólny rozkład \displaystyle q. Określmy:


\displaystyle  X_0 = \xi_0\ oraz \displaystyle   \ X_{n+1} = X_n + \xi_{n+1} \;\; dla \displaystyle  \ n = 0,1,2, \dots


Sprawdź, że zmienne losowe \displaystyle X_n tworzą łańcuch Markowa.

Zadanie 10.5
Niech \displaystyle {\mathbf{P}} będzie macierzą przejścia pewnego łańcucha Markowa. Wykaż, że dla wszystkich potęg \displaystyle k zachodzi warunek:


\displaystyle  \sum_{ j \in E}{\mathbf{P}^k}(i,j) = 1 dla każdego \displaystyle  i \in E.

Zadanie 10.6
Niech zmienne losowe \displaystyle X_n, \displaystyle n = 0,1,2, \dots, tworzą łańcuch Markowa. Pokaż, że zmienne \displaystyle X_0, X_k, X_{2k}, \dots, gdzie \displaystyle k >1 jest ustaloną liczbą, także tworzą łańcuch Markowa.

Zadanie 10.7
Napisz procedury, które symulują łańcuchy Markowa z przykładu 10.6 oraz z zadań 10.2 i 10.3.

Zadanie 10.8
Pokaż, że dla ergodycznego łańcucha Markowa oraz dla dowolnego rozkładu początkowego \displaystyle {\mathbf{p}}, rozkłady wektorów losowych \displaystyle X_n są zbieżne do rozkładu stacjonarnego \displaystyle \pi, to znaczy:


\displaystyle  \lim_{n \rightarrow \infty}{\mathbf{p}}_n(i) = \pi(i) dla każdego \displaystyle   i \in E.

Zadanie 10.9
Znajdź rozkłady stacjonarne (o ile istnieją) dla łańcuchów Markowa z przykładu 10.6 oraz zadań 10.2 i 10.3.

Zadanie 10.10
Podaj przykład nieredukowalnego łańcucha Markowa o skończonej liczbie stanów, który nie jest ergodyczny.

Zadanie 10.11
Wykaż, że ergodyczny łańcuch Markowa jest powracający.