Zajmiemy się teraz kolejną ważną klasą procesów stochastycznych: łańcuchami Markowa.

Niech E będzie ,,przestrzenią stanów”: skończonym lub przeliczalnym zbiorem. Jego elementy będziemy oznaczać literami j, k, … bądź 1, 2, ….

Przykłady:

1) Załóżmy, że X0, X1, X2, … są niezależnymi zmiennymi losowymi o tym samym rozkładzie, przyjmującymi wartości w zbiorze E, przy czym PXn=j=pj dla j∈E. Wówczas

a zatem Xnn jest łańcuchem Markowa; mamy

2) (Błądzenie losowe) Załóżmy, że ξ1, ξ2, … są niezależnymi zmiennymi losowymi o rozkładzie Pξn=1=p, Pξn=-1=q=1-p. Niech X0=0, Xn=ξ1+ξ2+…+ξn dla n≥1. Mamy

3) (Błądzenie z pochłanianiem na brzegu). Załóżmy, że a,⁢b∈Z+, Xn jak poprzednio, przy czym po dojściu do -a bądź b proces zatrzymuje się. Otrzymany ciąg zmiennych losowych także jest łańcuchem Markowa. Mamy E=-a,-a+1,…,b-1,b i

4) (Błądzenie z odbiciem od brzegu). Niech a,⁢b∈Z+, Xn jak poprzednio, przy czym po dojściu do -a przechodzimy do -a+1, po dojściu do b przechodzimy do b-1. Wówczas otrzymany proces jest łańcuchem Markowa o macierzy przejścia jak poprzednio, tyle że pierwszy wiersz to 0,1,0,0,…,0, a ostatni - 0,0,…,0,1,0.

5) (Model dyfuzji cząstek). Danych jest n cząstek w dwóch pojemnikach: I i II. Co jednostkę czasu losowo wybrana cząstka przemieszcza się z jednego pojemnika do drugiego.

Niech Xn oznacza liczbę cząstek w pojemniku I w chwili n. Przestrzeń stanów to E=0,1,2,…,n oraz

Pozostałe pi⁢j są równe 0:

Podane niżej twierdzenie mówi, iż każda macierz stochastyczna i rozkład początkowy prowadzą do pewnego łańcucha Markowa. Twierdzenie to pozostawimy bez dowodu.

Mówimy, że stan j jest osiągalny ze stanu i, jeśli pi⁢jn>0 dla pewnego n≥1. Mówimy, że stany i oraz j się komunikują, jeśli j jest osiągalny z i oraz i jest osiągalny z j. Stan i jest nieistotny, jeśli istnieje taki stan j, że j jest osiągalny z i oraz i nie jest osiągalny z j. Jak łatwo sprawdzić, korzystając z równania Chapmana-Kołmogorowa, relacja ,,osiągalności” jest przechodnia: istotnie, jeśli j jest osiągalny z i oraz k jest osiągalny z j, to dla pewnych m, n≥1, pi⁢jm>0 i pj⁢kn>0, a zatem

Aby zilustrować powyższe definicje, odnotujmy, iż dla błądzenia losowego po liczbach całkowitych (przykład 2 powyżej), wszystkie stany wzajemnie się komunikują. Natomiast w przypadku pochłaniania na brzegu (przykład 3), stany -a+1,-a+2,…,b-1 są nieistotne.

Zbiór stanów S nazywamy zamkniętym, jeśli dla dowolnego i∈S oraz j∉S, stan j nie jest osiągalny ze stanu i (innymi słowy, startując ze stanu wewnątrz C, z prawdopodobieństwem 1 nie wychodzimy nigdy z tego zbioru). Jeśli stan k ma tę własność, że zbiór k jest zamknięty (tzn. mamy pk⁢kn=1 dla wszystkich n), to stan ten nazywamy pochłaniającym. łańcuch Markowa nazywamy nieprzywiedlnym, jeśli wszystkie stany komunikują się ze sobą. Przykładowo, łańcuch Markowa pojawiający się w modelu dyfuzji cząstek (przykład 5) jest nieprzywiedlny.

Uwaga: Załóżmy, że C jest zamkniętym zbiorem stanów łańcucha Markowa o macierzy przejścia P=pi⁢ji,j∈E×E. Wówczas możemy rozpatrzyć łańcuch Markowa ,,zawężony” do C: jako nową przestrzeń stanów bierzemy zbiór C, a macierz przejścia zadana jest przez pi⁢j(i,j)]inC×C (wykreślamy z macierzy P wiersze i kolumny odpowieadające stanom nienależącym do C). Przykładowo, załóżmy, że macierz przejścia łańcucha na E=1,2,3,4 wynosi

Jak łatwo zauważyć, zbiór C=1,2 jest zamknięty i indukuje łańcuch Markowa o wartościach w tym zbiorze i macierzy przejścia 1/21/21/43/4.

Niech

będzie prawdopodobieństwem tego, że startując z k łańcuch dojdzie kiedyś do stanu j. Mamy

gdzie

jest prawdopodobieństwem że startując z k łańcuch dochodzi do j po raz pierwszy w chwili n.

Niech Nj=∑n=1∞1{Xn=j} będzie zmienną losową zliczającą ile razy proces Xn był w stanie j (nie biorąc pod uwagę zmiennej X0). Mamy następujący fakt.

Uwaga: W szczególności, P(Nj=∞|X0=i)=0 jeśli j jest stanem chwilowym. Zatem w przypadku stanu chwilowego, proces odwiedza go skończenie wiele razy niezależnie od punktu startowego.

Podane niżej twierdzenie charakteryzuje stany chwilowe i powracające w terminach macierzy przejścia. Wprowadźmy, dla każdego j∈E, liczbę Pj=∑n=1∞pj⁢jn. Na mocy twierdzenia Fubiniego (dla funkcji nieujemnych),

czyli Pj jest średnim czasem przebywania łańcucha w stanie j (przy założeniu startowania z tego stanu), nie licząc zmiennej X0.

Przykład: Zbadamy błądzenie losowe po liczbach całkowitych. Mamy

na mocy wzoru Stirlinga. Ponadto, p002⁢n+1=0. Stąd

wtedy i tylko wtedy,gdy p≠1/2. Zatem 0 jest stanem powracającym wtedy i tylko wtedy, gdy p=1/2.

W przypadku gdy wszystkie stany komunikują się wzajemnie, stany muszą być tego samego typu.

Możemy więc mówić o łańcuchach określonego typu: chwilowych i powracających.

Na zakończenie - następujący fakt dotyczący struktury stanów łańcucha Markowa ze względu na stany chwilowe i powracające (bez dowodu).

Przy danym rozbiciu przestrzeni E jak w powyższym stwierdzeniu, z prawdopodobieństwem 1 łańcuch Markowa zachowuje się następująco. Jeśli startuje on w zbiorze Di, i≥1, to nigdy go nie opuszcza i odwiedza wszystkie elementy tego zbioru; jeśli startuje on w zbiorze C, to albo pozostaje tam na zawsze (co może mieć miejsce tylko wtedy, gdy C ma nieskończenie wiele elementów), albo po skończonej liczbie kroków trafia do jednego ze zbiorów Di, i pozostaje tam na zawsze.

Rozkład stacjonarny ma następujące własności. Po pierwsze zauważmy, że jeśli π jest rozkładem stacjonarnym, to dla każdego n≥1, π⁢Pn=π (oczywista indukcja). Innymi słowy, jeśli Xn jest łańcuchem Markowa o macierzy przejścia P i rozkładzie początkowym π, to dla n≥1, rozkład Xn jest równy π. Można nawet powiedzieć więcej: dla wszystkich n≥1 oraz dowolnego ciągu m1<m2<…<mk (k≥1 również jest dowolne) wektor Xm1,Xm2,…,Xmk ma ten sam rozkład co Xn+m1,Xn+m2,…,Xn+mk. Istotnie,

co nie zależy od n.

łańcuch o takiej własności nazywamy stacjonarnym.

Wobec tego następująca definicja ma sens.

Uwaga: Jak widać, przy założeniach twierdzenia, pi⁢jn ,,przestaje zależeć od i” o ile n jest duże. Innymi słowy, po dużej liczbie kroków łańcuch ,,zapomina”, z jakiego stanu wystartował.

Na zakończenie zaprezentujemy następujący fakt. Dowodzi się go używając podobnej argumentacji jak w poprzednim twierdzeniu. Szczegóły pozostawiamy czytelnikowi.

1. Niech E będzie pewnym zbiorem przeliczalnym. Dany jest ciąg Xn niezależnych zmiennych losowych oraz ciąg funkcyjny fn, fn:E×R→E. Definiujemy ciąg Yn wzorem

gdzie Y0 jest pewną zmienną losową o wartościach w E. Dowieść, że Yn jest łańcuchem Markowa.

2. Dany jest łańcuch Markowa Xn na pewnej przestrzeni E oraz różnowartościowa funkcja f:E→E. Wykazać, że f⁢Xn jest łańcuchem Markowa. Co jeśli f nie jest różnowartościowa?

3. Dany jest ciąg Xn niezależnych zmiennych losowych o tym samym rozkładzie PXn=±1=12. Rozstrzygnąć, które z podanych niżej procesów są łańcuchami Markowa:

4. Dany jest ciąg Xn niezależnych zmiennych losowych o tym samym rozkładzie PXn=1=p=1-PXn=-1, p∈0,1. Niech Sn=X1+X2+…+Xn, n=1,2,…. Udowodnić, że ciągi

są łańcuchami Markowa.

5. Rzucamy kostką tak długo, aż pojawi się ciąg 16 lub 66. Jakie jest prawdopodobieństwo, że ciąg 16 pojawi się wcześniej?

6. Rzucamy symetryczną monetą aż do momentu, gdy wyrzucimy serię 4 orłów. Obliczyć wartość oczekiwaną liczby przeprowadzonych rzutów.

7. Macierz przejścia łańcucha Markowa Xnn na przestrzeni E=1,2,3,4 dana jest następująco:

• a) Jakie jest prawdopodobieństwo dojścia w dwóch krokach ze stanu 1 do stanu 2?

• b) Zakładając, że X0=1 p.n. obliczyć prawdopodobieństwo tego, że Xn będzie w stanie 2 przed stanem 4.

• c) Zakładając, że X0=3 p.n. obliczyć wartość oczekiwaną czasu dojścia do stanu 2.

• d) Wyznaczyć rozkład stacjonarny. Czy łańcuch jest okresowy? Czy jest nieprzywiedlny?
  

8. Po wierzchołkach pięciokąta ABCDE porusza się pionek. W chwili początkowej znajduje się w punkcie A, a w każdym kolejnym ruchu przesuwa się w sposób niezależny od poprzednich ruchów z prawdopodobieństwem 1/2 do jednego z sąsiednich wierzchołków. Obliczyć

a) prawdopodobieństwo, że pionek powróci do punktu A przed dotarciem do punktu C,

b) wartość oczekiwaną liczby ruchów, jakie wykona pionek przed powrotem do punktu A.

9. Naukowiec mający r parasoli wędruje między domem a biurem, zabierając ze sobą parasol (jeśli jest on pod ręką) wtedy, gdy pada (prawdopodobieństwo p), lecz nie przy bezdeszczowej pogodzie (prawdopodobieństwo q=1-p). Niech stanem łańcucha Markowa będzie liczba parasoli znajdujących się pod ręką, bez względu na to, czy naukowiec jest w domu, czy w miejscu pracy. Skonstruować macierz przejścia i znaleźć rozkład stacjonarny. Znaleźć przybliżone prawdopodobieństwo zmoknięcia naukowca w danym (odległym) dniu, a następnie wykazać, że 5 parasoli jest w stanie ochronić go w 95⁢% przed zmoknięciem (dla dowolnego p).

10. Proces Xn jest łańcuchem Markowa.

(i) Czy dla dowolnego n≥0, liczb 0≤i0<i1<…<ik=n oraz stanów a0, a1, …, ak+1 mamy