Przeskocz do treści

Delta mi!

Loading

O polowaniu na pchłę i czekaniu na dwa orły, czyli trochę o łańcuchach Markowa

Katarzyna Pietruska-Pałuba

o artykule ...

  • Publikacja w Delcie: wrzesień 2013
  • Publikacja elektroniczna: 31-08-2013
  • Autor: Katarzyna Pietruska-Pałuba
    Afiliacja: Instytut Matematyki, Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (234 KB)

Zacznijmy od prostego przykładu. Pchła skacze między ziemią, kotem i człowiekiem. Za każdym razem wybiera miejsce docelowe z takim samym prawdopodobieństwem (równym math). Mogłaby tak skakać w nieskończoność, gdyby nie to, że po wskoczeniu na człowieka ginie. Ile średnio skoków pchła wykona przed śmiercią, jeżeli zaczyna na ziemi?

Zadanie rozwiążemy bez trudu, pamiętając, że średnia wartość zmiennej losowej to suma wszystkich iloczynów postaci

display-math

Po prostu wypiszemy wszystkie możliwe drogi pchły: zginie ona po 1 skoku, jeżeli od razu skoczy na człowieka, co zapisujemy math ; po 2 skokach – math (najpierw na kota, potem na człowieka), po 3 skokach – math  po 4 skokach – math  i tak dalej. Każdy taki ciąg długości math  ma prawdopodobieństwo math math a zatem średnio pchła wykona math skoków. Oznaczając math średnią ilość skoków pchły możemy wyznaczyć, sumując poniższe wyrażenie kolumnami:

pict

A zatem pchła wykona średnio 2 skoki.

Rozbudujmy ten przykład i wpuśćmy do pokoju psa. Zasady skoków pchły pozostają takie same, ale teraz prawdopodobieństwo wyboru każdego docelowego miejsca skoku to math Możemy rozwiązywać zadanie tak samo jak przedtem – będzie to nieco dłuższe, ale nadal wykonalne.

Można też nieco inaczej. W obu powyższych zagadnieniach miejsce kolejnego przeskoku zależy tylko od tego, gdzie pchła znajduje się w danej chwili, a nie od jej przeszłej podróży. Ponadto z góry wiadomo, jakie są możliwe położenia pchły, tak zwane stanymath  lub math oraz jakie są reguły poruszania się między stanami. Oznacza to, że w obu przypadkach mamy do czynienia z łańcuchem Markowa. Reguły przeskoku to prawdopodobieństwa przejścia między stanami. Prawdopodobieństwo przejścia ze stanu math do stanu math oznaczamy przez math

W zagadnieniu I mamy:

display-math

dla kompletności przyjmiemy jeszcze math  W zagadnieniu II jest podobnie:

pict

oraz math  Wygodnie jest zapisać takie prawdopodobieństwa w macierzy albo wyrysować je jako graf. Na przykład dla właściciela dwóch zwierząt macierz oraz graf będą wyglądać następująco:

display-math

obrazek


W ogólnej sytuacji powiemy, że ciąg zmiennych losowych math  tworzy jednorodny łańcuch Markowa o przestrzeni stanów math jeżeli dla dowolnego math i dowolnego ciągu stanów math mamy

display-math

Oznacza to, że dochodząc do każdego stanu, łańcuch „zapomina”, skąd przyszedł, a prawdopodobieństwa przejścia w następnym ruchu zależą tylko od położenia bieżącego. Własność tę nazywamy własnością Markowa i tak właśnie jest w powyższych przykładach.

Teraz rozwiążemy zadanie o średnim czasie życia pchły dla łańcucha Markowa o grafie jak wyżej. Niech math  oznaczają średnie czasy życia pchły startującej odpowiednio z ziemi, kota, psa, człowieka. Oczywiście, mamy math  a pozostałe czasy życia możemy związać układem równań, wykorzystując wzór na prawdopodobieństwo całkowite i własność Markowa. Na przykład, jeżeli startujemy z ziemi, to po wykonaniu jednego skoku przechodzimy do jednego ze stanów math z prawdopodobieństwem math i kontynuujemy skoki z tych nowych stanów, zapominając o przeszłości, ale za to zwiększając „odczyt licznika” o  math bo jeden skok już wykonaliśmy. Otrzymujemy układ równań:

display-math

Rozwiązując go, natychmiast dostaniemy, że math

A jeśli człowiek ma gorszy refleks i szansa na to, że zabije pchłę, która na niego wskoczyła, wynosi math Jeżeli pchła przeżyje kontakt z człowiekiem, to przerażona (czy pchła się boi?) nie zastanawia się już, co ma zrobić (czy pchła się zastanawia?) i zeskakuje na ziemię. Dla opisania ruchu pchły dodamy osobny stan math (po angielsku nazywany cemetery state), do którego można dojść tylko z  math  i z którego nie można już wyjść. Graf będzie teraz taki.

obrazek

Uważny Czytelnik zauważy, że powyższy graf nie do końca odpowiada omawianej sytuacji. Graf ten uwzględnia dodatkowy krok między wskoczeniem na człowieka a śmiercią pchły, którego w rzeczywistości nie dodaje się do czasu jej życia.

Postępując jak wcześniej, wypiszemy układ równań na czasy dojścia do math odpowiadający grafowi 2:

display-math

Zwróćmy uwagę, że teraz zamiast math  będziemy mieli math Rozwiązując ten układ, dostaniemy math ; math Liczba math  nie jest jednak średnim czasem życia pchły – czas życia będzie o  math mniejszy, bo przecież dodaliśmy jeden krok na przejście math  Zatem pchła średnio wykona 5 skoków, zanim zginie.

Rozważymy teraz pozornie zupełnie inne zagadnienie. Adaś i Bolek obserwują wyniki kolejnych rzutów niesymetryczną monetą, dla której prawdopodobieństwo wyrzucenia orła to math Założyli się o czekoladę: Adaś wygra, jeżeli dwa orły pod rząd wypadną, zanim Bolek doczeka się serii trzech reszek, a Bolek – jeśli to trzy reszki pojawią się wcześniej. Jakie jest prawdopodobieństwo tego, że wygra Adaś?

Czy wiesz, Czytelniku, czemu ta gra z prawdopodobieństwem 1 zakończy się po skończonej liczbie rzutów?

Zastanówmy się, gdzie można w tym zagadnieniu dopatrzeć się łańcucha Markowa. Otóż będziemy rozważali tylko takie końcówki ciągów, które mogą być kontynuowane jako rozstrzygające grę math  albo math

Na przykład, jeżeli wykonano 5 rzutów, w których po kolei wypadło math to układ będzie w stanie math  bo math  jest początkiem pożądanego ciągu math  Gdyby natomiast wynikiem było math  to układ byłby w stanie math – byłaby to wygrana Bolka i koniec zabawy. Możliwe stany układu są więc następujące: math a prawdopodobieństwa przejścia to

display-math

Musimy jeszcze dopowiedzieć, że po pierwszym rzucie z prawdopodobieństwem math wchodzimy w stan math  a z prawdopodobieństwem math – w stan math i to określa pierwszy krok. Adaś wygra, jeżeli uda się dojść do stanu math  Graf układu wygląda następująco.

obrazek

Analogicznie jak w zadaniu o średnim czasie życia pchły, możemy ułożyć układ równań, w którym powiążemy prawdopodobieństwa wygranej Adasia przy starcie ze stanów math  oznaczone odpowiednio przez math Wykonujemy krok w przód, patrzymy, gdzie dotarliśmy, korzystamy ze wzoru na prawdopodobieństwo całkowite, a następnie z własności Markowa (tj. zapominamy, skąd przyszliśmy), i rozważamy prawdopodobieństwa wygranej Adasia przy starcie z nowych położeń. Na przykład, ze stanu math  przechodzimy z prawdopodobieństwem math do stanu math  i z prawdopodobieństwem math do stanu math Otrzymujemy układ równań:

display-math

przy czym mamy math  i  math  Rozwiązaniem układu są liczby:

display-math

Ponieważ po pierwszym kroku znajdziemy się w stanie math  lub math (z prawdopodobieństwem odpowiednio math i  math), to prawdopodobieństwo wygranej Adasia wynosi

display-math

Może Adaś nie lubi czekolady?

Pozostawiamy Czytelnikowi do samodzielnego rozwiązania zadanie: jeżeli moneta jest symetryczna, to jaki będzie średni czas trwania gry? (Odpowiedź)

O tym, co się dzieje z łańcuchami Markowa po długim czasie, dowiesz się Czytelniku z drugiej części artykułu (Delta 12/2013).

Notice: Undefined index: story_alias_uuid in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 23 Notice: Undefined index: story_alias_uri in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 24