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

Ć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 $q$, $r$ i $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 $-10$ i $10$ oraz przyjmujemy następujące parametry:

$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:

<flash>file=Rp.1.102.swf|width=350|height=350</flash>

<flash>file=Rp.1.103.swf|width=350|height=350</flash>

<flash>file=Rp.1.104.swf|width=350|height=350</flash>

<flash>file=Rp.1.105.swf|width=350|height=350</flash>

Ćwiczenie 10.2

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

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

${\mathbf{𝐏}}_d^n(i)={\mathbf{𝐏}}_d^n(i,i)={\mathbf{𝐏}}^n(i_1,i_1)\cdot \dots \cdot {\mathbf{𝐏}}^n(i_d,i_d)={({\mathbf{𝐏}}^n(0,0))}^d.$

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

${\mathbf{𝐏}}_2^n(i)\approx \mathrm{\infty }$, $F_2(0)=1$,

${\mathbf{𝐏}}_3^n(i)\approx 0.3932039296$, $F_3(0)\approx 0.2822299888$,

${\mathbf{𝐏}}_4^n(i)\approx 0.1186363871$, $F_4(0)\approx 0.1060544682$,

${\mathbf{𝐏}}_5^n(i)\approx 0.04682554981$, $F_5(0)\approx 0.04473099631$,

${\mathbf{𝐏}}_6^n(i)\approx 0.02046077706$, $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 $-2$ oraz $2$, zaś parametrami określającymi spacer są:

$p=0.5,q=0.3,r=0.2,sa=0.9,sb=0.1.$

Macierz przejścia ma wówczas postać:

Parser nie mógł rozpoznać (nieznana funkcja „\noalign”): {\displaystyle \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:

Parser nie mógł rozpoznać (nieznana funkcja „\noalign”): {\displaystyle \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 ${\mathbf{𝐏}}^{30}$ i ${\mathbf{𝐏}}^{50}$ wyglądają następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\noalign”): {\displaystyle \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], }

Parser nie mógł rozpoznać (nieznana funkcja „\noalign”): {\displaystyle \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 $Ax=b$. Wyznaczamy najpierw $A$ oraz $b$ tak, aby układ ten był równoważny układowi występującemu w twierdzeniu ergodycznym (twierdzenie 10.11). Otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\noalign”): {\displaystyle \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 $\pi$:

$\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 $P^{50}$.

Ćwiczenie 10.5

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

$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:

$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 $\mathbf{𝐏}$:

Parser nie mógł rozpoznać (nieznana funkcja „\noalign”): {\displaystyle \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:

$\mathbf{𝐩}=\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:

${\mathbf{𝐩}}_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{𝐩}}_{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{𝐩}}_{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ą:

$\mathbb{𝔼}(X_5)\approx 7.00000,\mathbb{𝔼}(X_{20})\approx 4.157931285,\mathbb{𝔼}(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 $X_1,\dots ,X_{200}$:

<flashwrap>file=Rp103.swf|size=small</flashwrap>

---

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 $k\frac{2\pi }{n}$, gdzie $n$ jest ustaloną liczbą naturalną, natomiast $k=0,\dots ,n-1$. Cząsteczka porusza się zgodnie z ruchem wskazówek zegara z prawdopodobieństwem $p$, przeciwnie do ruchu wskazówek zegara - z prawdopodobieństwem $q$ i nie zmienia położenia z prawdopodobieństwem $r$ ($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 ${\xi }_0,\dots ,{\xi }_n$ będą niezależnymi zmiennymi losowymi, przyjmującymi jedynie wartości całkowite. Załóżmy, że zmienna ${\xi }_0$ ma rozkład $q_0$, natomiast zmienne ${\xi }_1,\dots ,{\xi }_n$ mają wspólny rozkład $q$. Określmy:

$X_0={\xi }_0$ oraz $X_{n+1}=X_n+{\xi }_{n+1}$ dla $n=0,1,2,\dots$

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

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

$\sum _{j\in E}{\mathbf{𝐏}}^k(i,j)=1$ dla każdego $i\in E.$

Zadanie 10.6
Niech zmienne losowe $X_n$, $n=0,1,2,\dots$, tworzą łańcuch Markowa. Pokaż, że zmienne $X_0,X_k,X_{2k},\dots$, gdzie $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 $\mathbf{𝐩}$, rozkłady wektorów losowych $X_n$ są zbieżne do rozkładu stacjonarnego $\pi$, to znaczy:

$\underset{n\to \mathrm{\infty }}{\lim }{\mathbf{𝐩}}_n(i)=\pi (i)$ dla każdego $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.