Rachunek prawdopodobieństwa i statystyka/Wykład 10: Łańcuchy Markowa

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Łańcuchy Markowa

Założenie o niezależności zmiennych losowych nie zawsze jest spełnione. Poznamy teraz sytuację, w której zmienne losowe są zależne, ale znamy dobrze charakter tej zależności - sytuację tę opisują tak zwane łańcuchy Markowa. Podamy podstawowe definicje i twierdzenia oraz standardowe przykłady łańcuchów Markowa.


Andriej Markow (1856-1922)
Zobacz biografię

W tym wykładzie przedstawimy jedną z najprostszych sytuacji, gdy rozważne zmienne losowe są zależne. Warto podkreślić, że łańcuchy Markowa, które będziemy za chwilę omawiać, stanowią bardzo interesujący przykład procesów stochastycznych. Ich teoria ma z kolei podstawowe znaczenie przy budowie probabilistycznych modeli wielu zjawisk przyrodniczych, technicznych, a także ekonomicznych. W szczególności, teoria procesów stochastycznych znajduje w ostatnich latach coraz większe zastosowanie przy wycenie instrumentów finansowych.

Definicje i przykłady

Niech będzie zbiorem skończonym lub przeliczalnym oraz niech



będą ustalonymi funkcjami. Będziemy myśleć o i jako o skończonej lub przeliczalnej macierzy (patrz wykład z Algebry liniowej z geometrią analityczną) oraz wektorze (patrz wykład z Algebry liniowej z geometrią analityczną) o współrzędnych , gdzie .

Definicja 10.1.[łańcuch Markowa]

Niech będzie dany ciąg wektorów losowych , , zdefiniowanych na przestrzeni probabilistycznej i przyjmujących wartości w . Mówimy, że jest łańcuchem Markowa, jeżeli spełnione są następujące warunki:

1. dla każdego ,

2. dla każdego zachodzi równość:




dla wszystkich ,


3. ,

4. dla każdego .

Powyższe warunki mają prostą interpretację. Mianowicie, utożsamiamy zbiór ze zbiorem wszystkich możliwych stanów pewnego systemu. Wówczas oznacza stan, w którym znajduje się nasz system w chwili czasowej . Warunek, że jest wektorem losowym oznacza, że faktycznie nie znamy dokładnie tego położenia, natomiast pozostałe warunki dają nam o nim pewne informacje. Po pierwsze, znamy rozkład prawdopodobieństwa położenia systemu w chwili zerowej (warunki 1 i 3). Po drugie, prawdopodobieństwo przejścia układu z jednego stanu do innego stanu, w jednostkowym odcinku czasu, zależy jedynie od samych stanów, a nie zależy od historii układu ani od konkretnej chwili, w której to przejście następuje (warunek 2). Wreszcie, układ nigdy nie opuści swojej przestrzeni stanów , gdyż:



zaś warunek 4 implikuje następującą równość dla wszystkich :



W związku z powyższą interpretacją, będziemy nazywać zbiorem stanów lub przestrzenią stanów, - rozkładem początkowym, zaś - macierzą przejścia łańcucha Markowa.

W dalszej części zaprezentujemy kilka typowych przykładów łańcuchów Markowa.

Spacer losowy

Chyba najbardziej klasycznym przykładem łańcucha Markowa jest spacer losowy po prostej.

Przykład 10.2

Wyobraźmy sobie cząsteczkę, która może się poruszać wzdłuż linii prostej według następujących reguł: w chwili zero cząsteczka znajduje się w punkcie o współrzędnej zero, natomiast w następnych momentach czasu (, , i tak dalej) może się przesuwać o jeden w lewo lub o jeden w prawo, z prawdopodobieństwami odpowiednio oraz , przy czym . Jeżeli to

mówimy, że spacer losowy jest standardowy.


Oto przykładowa animacja, prezentująca standardowy spacer losowy o 300 krokach:

<flash>file=Rp101.swf|width=500|height=500</flash>

Okazuje się, że spacer losowy po prostej jest łańcuchem Markowa. Rzeczywiście, stanami są wszystkie możliwe liczby całkowite, czyli , natomiast oznacza pozycję cząsteczki w chwili . Zdefiniujmy:



oraz



Zauważmy, że określony powyżej spacer losowy może być modyfikowany na różne sposoby. Załóżmy, na przykład, że cząsteczka może nie zmieniać swojego położenia z prawdopodobieństwem (wtedy oczywiście zakładamy, że ). Inną modyfikacją jest założenie o istnieniu jednej lub dwóch barier (ekranów), które ograniczają możliwość ruchu cząsteczki. Przykładowo, jeżeli są one usytuowane w punktach i , gdzie , to zbiór składa się stanów, zaś -wymiarowa macierz może być zdefiniowana w następujący sposób:



Liczby oraz oznaczają prawdopodobieństwa tego, że cząsteczka jest pochłaniana przez barierę lub . Dwa interesujące przypadki skrajne są wtedy, gdy liczby te są albo zerami, co oznacza pełną elastyczność barier, albo jedynkami, co oznacza pełną absorbcję cząsteczki z chwilą jej dojścia do bariery.

Przykładowy spacer losowy może wyglądać tak:

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

Tutaj ekrany ustawiono w punktach i , parametry wynoszą:



zaś wykonanych jest 30 kroków.

W poniższej animacji także ustawiono bariery w punktach oraz , ale tym razem:



<flash>file=Rp102.swf|width=500|height=500</flash>

Kolejny przykład pokazuje, iż można też opisać spacer losowy w trochę inny sposób.

Przykład 10.3

Załóżmy, nieco ogólniej niż poprzednio, że cząsteczka startuje w chwili 0 z punktu . Gdy nie uwzględniamy barier, mamy:



gdzie są niezależnymi zmiennymi losowymi, przyjmującymi wartości , ,

z prawdopodobieństwami, odpowiednio, , i .

Można także rozpatrywać spacery losowe na płaszczyźnie, a także (ogólnie) w przestrzeni wielowymiarowej.

Przykład 10.4

Dla uproszczenia załóżmy, że , czyli także, że . Dla mamy:



Tym razem są niezależnymi wektorami losowymi, przyjmującymi wartości ,

gdzie , z jednakowym prawdopodobieństwem .

Zauważmy, że współrzędnymi zdefiniowanego w powyższym przykładzie -wymiarowego spaceru losowego są niezależne jednowymiarowe standardowe spacery losowe.

Poniżej przedstawiamy dalsze przykłady łańcuchów Markowa.

Przykład 10.5

Załóżmy, że dwaj gracze, powiedzmy Antoni i Bolesław, mają kapitał, odpowiednio, i złotych. Powtarzają oni tę samą grę (może, na przykład, grają w szachy), przy czym przegrywający płaci wygrywającemu złotówkę. Gra kończy się wtedy, gdy jednemu z graczy skończą się pieniądze. Załóżmy, że w każdej grze prawdopodobieństwo wygrania przez Antoniego wynosi , zaś prawdopodobieństwo wygrania przez Bolesława wynosi . Zakładamy, że i oznaczamy przez prawdopodobieństwo remisu, czyli . Oznaczmy kapitał Antoniego po zakończeniu -tej gry przez . Zauważmy, że opisana sytuacja jest faktycznie spacerem losowym, startującym w punkcie

i mającym bariery pochłaniające w punktach oraz .

Przykład 10.6

W każdej z dwóch urn umieszczono po kul, przy czym z nich ma kolor zielony, a pozostałe - kolor czerwony. Następnie w kolejnych momentach czasu zamieniamy miejscami jednocześnie wylosowane 2 kule (po jednej z obu urn). Niech oznacza liczbę zielonych kul w pierwszej urnie (więc tym samym liczbę czerwonych kul w drugiej urnie) w chwili . Widzimy, że zmienne tworzą łańcuch Markowa z macierzą przejścia mającą zerowe wyrazy oprócz:



Badanie własności łańcuchów Markowa zaczniemy od wyznaczenia rozkładów wektorów losowych , co sprowadza się do wyznaczenia, dla wszystkich , funkcji (wektorów) takich, że:



Stosując wzór na prawdopodobieństwo całkowite, mamy:



czyli:


     (10.1)


gdzie oznacza macierz transponowaną (patrz wykład z Algebry liniowej z geometrią analityczną) do macierzy . Oznaczając -tą potęgę macierzy przez , otrzymujemy wreszcie poszukiwany rozkład:



W szczególności, jeżeli wiemy, że , czyli że łańcuch w chwili 0 znajduje się w stanie z prawdopodobieństwem 1, powyższy wzór implikuje następującą własność:



co nieco wyjaśnia znaczenie wyrazów macierzy .

Niech teraz oznacza zbiór opisany przez wektory losowe , co oznacza, że ma postać:



gdzie suma jest brana po pewnym zbiorze indeksów - zbiór tych indeksów oznaczmy przez . Wówczas:


     (10.2)


Aby udowodnić powyższą równość zauważmy, że:




gdzie obie sumy brane są po zbiorze . Z własności 2 w definicji łańcucha Markowa (definicja 10.1) otrzymujemy:







co daje wzór 10.2.

Kolejne twierdzenie prezentuje inną (bardziej ogólną) interpretację wyrazów macierzy , jako prawdopodobieństw przejścia w krokach ze stanu do stanu .

Twierdzenie 10.7.

Dla każdego oraz mamy:


     (10.3)


Dowód .

Dla (formuła 10.3) jest konsekwencją własności 2 w definicji definicji 10.1. Dla przeprowadzenia kroku indukcyjnego załóżmy, że wzór 10.3 zachodzi dla pewnego . Mamy wówczas:





Korzystając ze wzoru 10.2 oraz z założenia indukcyjnego dostajemy:





a więc dowiedliśmy wzór 10.3 dla , co kończy dowód.

End of proof.gif

Nieredukowalne łańcuchy Markowa

W dalszej części będziemy się zajmować tylko takimi łańcuchami Markowa, których każde dwa stany mogą się komunikować. Mówiąc dokładniej, będziemy zakładać, że dla każdych dwóch stanów oraz prawdopodobieństwo przejścia jest dodatnie dla pewnego . Łańcuch Markowa o tej własności nazywa się łańcuchem nieredukowalnym. Większość spotykanych w zastosowaniach łańcuchów Markowa jest nieredukowalna, jakkolwiek łatwo pokazać przykłady łańcuchów, które nie spełniają tego warunku - na przykład spacer losowy z ekranami pochłaniającymi nie jest nieredukowalny, gdyż prawdopodobieństwo przejścia z jednego do drugiego ekranu jest równe 0.

Powracanie i okresowość

Dla nieredukowalnego łańcucha Markowa, przez oznaczmy prawdopodobieństwo pierwszego powrotu do stanu w dokładnie krokach, czyli:



Określmy jako:



- jest to prawdopodobieństwo pierwszego powrotu do stanu w czasie skończonym.

Oczywiście, . Będziemy mówić, że stan jest powracający, jeżeli , zaś niepowracający - jeżeli . Można udowodnić, że albo wszystkie stany są powracające, albo wszystkie stany są niepowracające. W związku z tym mówimy, że (nieredukowalny) łańcuch Markowa jest, odpowiednio,powracający albo niepowracający.

Następujące twierdzenie, które podajemy bez dowodu, pozwala w wielu przypadkach stwierdzić, czy łańcuch Markowa jest powracający, czy niepowracający. Oznaczmy:



Twierdzenie 10.8

Niech będzie ustalonym stanem nieredukowalnego łańcucha Markowa. Wtedy:

1. stan jest powracający wtedy i tylko wtedy,gdy:



2. jeżeli jest stanem niepowracającym, to:



Liczby mają także nieco inną interpretację, którą prezentuje poniższe twierdzenie. Oznaczmy przez liczbę wszystkich powrotów do stanu .

Twierdzenie 10.9

Dla każdego :



Dowód .

Załóżmy, że w chwili system znajdował się w stanie . W takim razie:



Mamy więc:



Wiemy, że (patrz zadanie 7.15):



zatem:


End of proof.gif


Przykład 10.10

Rozważmy jednowymiarowy spacer losowy bez barier z prawdopodobieństwami (patrz przykład 10.2). Wyraźnie widać, że jest to nieredukowalny łańcuch Markowa oraz że:



Można też łatwo się przekonać (ćwiczenie), że:



Teraz:



Tę ostatnią sumę można obliczyć analitycznie, co jest zadaniem dość trudnym. Jednakże, korzystając z programu Maple wynik uzyskujemy bardzo szybko:

 > sum(binomial(2*k,k)/4^k,k=1..infinity);



Tak więc okazało się, iż jednowymiarowy standardowy spacer losowy jest powracający.

Można też pokazać, że dwuwymiarowy standardowy spacer losowy (patrz przykład 10.4) jest powracający, natomiast spacer losowy w przestrzeni o wymiarze co najmniej trzy nie jest powracający - wrócimy do tego problemu w ćwiczeniu ćwiczeniu 10.2.

Rozważmy nieredukowalny łańcuch Markowa i ustalmy pewien jego stan . Ponieważ komunikuje się z samym sobą, zatem istnieje liczba taka, że - niech oznacza zbiór wszystkich takich liczb . Zauważmy, że:



Wynika to z następującej (ogólniejszej) obserwacji: dla wszystkich stanów , oraz :



a więc, w szczególności:



Mówimy, że stan jest okresowy o okresie , jeżeli jest największym wspólnym podzielnikiem liczb ze zbioru . Można udowodnić, że w nieredukowalnym łańcuchu Markowa zachodzi dokładnie jeden z następujących warunków:

1. wszystkie stany są okresowe i mają wspólny okres,

2. żaden ze stanów nie jest okresowy.

W pierwszym z powyższych przypadków mówimy, że łańcuch Markowa jest okresowy, a jego okresem jest (wspólny) okres każdego z jego stanów.

Spacer losowy opisany w przykładzie 10.2 jest okresowy o okresie 2, natomiast jego nie posiadająca ekranów modyfikacja, dla której , nie jest okresowa. Pamiętajmy jednak, iż sam warunek nie gwarantuje jeszcze okresowości (jeżeli istnieją ekrany pochłaniające, to łańcuch nie jest nieredukowalny).

Ergodyczność

W pewnych okolicznościach możemy być zainteresowani tym, jak zachowuje się łańcuch Markowa po upływie długiego czasu. W szczególności, warto się pytać o asymptotyczny rozkład prawdopodobieństwa wektorów , o ile oczywiście taki rozkład istnieje. Poniżej prezentujemy tak zwane twierdzenie ergodyczne, które opisuje właśnie taką sytuację.

Twierdzenie 10.11

Rozważamy nieredukowalny łańcuch Markowa o skończonej liczbie stanów (to znaczy ) i macierzy przejścia . Wówczas zachodzi dokładnie jeden z następujących warunków:

1. łańcuch jest okresowy,

2. istnieje wektor o współrzędnych , , taki, że:

a) dla wszystkich ,

b) dla wszystkich :



c) wektor jest jedynym rozwiązaniem równania:



spełniającym warunek:



Jeżeli spełniony jest warunek 2 z powyższego twierdzenia, to łańcuch Markowa nazywamy ergodycznym, zaś wektor - jego rozkładem stacjonarnym. Mówiąc niezbyt precyzyjnie, ergodyczność oznacza, że dla dużych prawdopodobieństwo przejścia ze stanu do stanu w krokach jest dodatnie i zależy faktycznie od stanu końcowego , zaś nie zależy od stanu początkowego - prawdopodobieństwa te można otrzymać, rozwiązując odpowiedni układ równań liniowych.

Nie podajemy dość długiego i trudnego dowodu twierdzenia ergodycznego. Zamiast tego, w ćwiczeniu 10.4 "sprawdzimy" to twierdzenie eksperymentalnie.