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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ć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 , i .

 > 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 i oraz przyjmujemy następujące parametry:



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 .

Niech oznacza macierz przejścia naszego łańcucha Markowa. Ustalmy stan . Zauważmy, że przejście w krokach ze stanu z powrotem do tego stanu podczas -wymiarowego spaceru losowego, jest równoważne przejściom ze stanów do w krokach podczas niezależnych od siebie jednowymiarowych spacerów losowych. Właśnie korzystając z tej niezależności, dostajemy:



Korzystając z powyższego wzoru oraz z twierdzenia 10.8, można obliczyć prawdopodobieństwa oraz prawdopodobieństwa powrotu w czasie skończonym dla . Warto w tym przypadku znowu skorzystać z programu Maple. Okazuje się, że:

, ,
, ,
, ,
, ,
, .

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 oraz , zaś parametrami określającymi spacer są:



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 i 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 . Wyznaczamy najpierw oraz 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 :



Widzimy, że rzeczywiście rozkład stacjonarny niewiele różni się od wierszy macierzy .


Ćwiczenie 10.5

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



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

Przypominamy, że mamy tutaj 14 stanów:

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

Konstruujemy macierz przejścia :


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:



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:



natomiast ich nadzieje matematyczne wynoszą:



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 :


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 , gdzie jest ustaloną liczbą naturalną, natomiast . Cząsteczka porusza się zgodnie z ruchem wskazówek zegara z prawdopodobieństwem , przeciwnie do ruchu wskazówek zegara - z prawdopodobieństwem i nie zmienia położenia z prawdopodobieństwem (). 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 będą niezależnymi zmiennymi losowymi, przyjmującymi jedynie wartości całkowite. Załóżmy, że zmienna ma rozkład , natomiast zmienne mają wspólny rozkład . Określmy:


oraz dla


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

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


dla każdego

Zadanie 10.6
Niech zmienne losowe , , tworzą łańcuch Markowa. Pokaż, że zmienne , gdzie 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 , rozkłady wektorów losowych są zbieżne do rozkładu stacjonarnego , to znaczy:


dla każdego

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.