Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Rachunek prawdopodobieństwa II – 6. Łańcuchy Markowa – MIM UW

Zagadnienia

6. Łańcuchy Markowa

6.1. Podstawowe definicje

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, \ldots bądź 1, 2, \ldots.

Definicja 6.1

Macierz P=[p_{{ij}}]_{{(i,j)\in E\times E}} nazywamy macierzą stochastyczną, jeśli p_{{ij}}\in[0,1] dla wszystkich i, j\in E oraz \sum _{{j\in E}}p_{{ij}}=1 dla każdego i\in E.

Definicja 6.2

Załóżmy, że (\Omega,\mathcal{F},\mathbb{P}) jest przestrzenią probabilistyczną, E, P są j.w., ustalone. Jednorodnym łańcuchem Markowa o wartościach w E i macierzy przejścia P nazywamy ciąg (X_{n})_{{n=0,1,2,\ldots}} zmiennych losowych takich, że

\begin{split}\mathbb{P}(X_{{n+1}}=a_{{n+1}}|&X_{n}=a_{n},\, X_{{n-1}}=a_{{n-1}},\ldots,X_{0}=a_{0})\\
&=\mathbb{P}(X_{{n+1}}=a_{{n+1}}|X_{n}=a_{n})=p_{{a_{n}a_{{n+1}}}}\end{split}

dla wszystkich a_{0}, a_{1}, \ldots, a_{{n+1}} takich, że zdarzenie warunkujące ma dodatnie prawdopodobieństwo. Równoważnie,

\mathbb{P}(X_{{n+1}}=j|X_{0},X_{1},\ldots,X_{n})=\mathbb{P}(X_{{n+1}}=j|X_{n})=p_{{X_{n}j}}.

Liczba p_{{ij}} jest prawdopodobieństwem przejścia ze stanu i do stanu j w jednym kroku.

Przykłady:

1) Załóżmy, że X_{0}, X_{1}, X_{2}, \ldots są niezależnymi zmiennymi losowymi o tym samym rozkładzie, przyjmującymi wartości w zbiorze E, przy czym \mathbb{P}(X_{n}=j)=p_{j} dla j\in E. Wówczas

\begin{split}\mathbb{P}(X_{{n+1}}=a_{{n+1}}|X_{n}=a_{n},\ldots,X_{0}=a_{0})&=\mathbb{P}(X_{{n+1}}=a_{{n+1}})=p_{j}\\
&=\mathbb{P}(X_{{n+1}}=a_{{n+1}}|X_{n}=a_{n}),\end{split}

a zatem (X_{n})_{n} jest łańcuchem Markowa; mamy

P=\left[\begin{array}[]{ccc}p_{1}&p_{2}&\ldots\\
p_{1}&p_{2}&\ldots\\
p_{1}&p_{2}&\ldots\\
\ldots\end{array}\right].

2) (Błądzenie losowe) Załóżmy, że \xi _{1}, \xi _{2}, \ldots są niezależnymi zmiennymi losowymi o rozkładzie \mathbb{P}(\xi _{n}=1)=p, \mathbb{P}(\xi _{n}=-1)=q=1-p. Niech X_{0}=0, X_{n}=\xi _{1}+\xi _{2}+\ldots+\xi _{n} dla n\geq 1. Mamy

\begin{split}\mathbb{P}(X_{{n+1}}=a_{{n+1}}&|X_{n},X_{{n-1}},\ldots,X_{0})=\mathbb{P}(X_{n}+\xi _{{n+1}}=a_{{n+1}}|\xi _{0},\xi _{1},\ldots,\xi _{n})\\
&=\begin{cases}p&\mbox{jeśli }X_{n}=a_{{n+1}}-1,\\
q&\mbox{jeśli }X_{n}=a_{{n+1}}+1,\\
0&\mbox{w pozostałych przypadkach}\end{cases}\\
&=\mathbb{P}(X_{{n+1}}=a_{{n+1}}|X_{n}).\end{split}

3) (Błądzenie z pochłanianiem na brzegu). Załóżmy, że a,\, b\in\mathbb{Z}_{+}, (X_{n}) 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,\ldots,b-1,b\} i

P=\left[\begin{array}[]{ccccccc}1&0&0&0&\ldots&0&0\\
q&0&p&0&\ldots&0&0\\
0&q&0&p&\ldots&0&0\\
0&0&q&0&\ldots&0&0\\
\ldots\\
0&0&0&0&\ldots&0&p\\
0&0&0&0&\ldots&0&1\end{array}\right]

4) (Błądzenie z odbiciem od brzegu). Niech a,\, b\in\mathbb{Z}_{+}, (X_{n}) 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,\ldots,0], a ostatni - [0,0,\ldots,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 X_{n} oznacza liczbę cząstek w pojemniku I w chwili n. Przestrzeń stanów to E=\{ 0,1,2,\ldots,n\} oraz

p_{{i,i+1}}=\frac{n-i}{n}\mbox{ dla }i\leq n-1,\,\,\, p_{{i,i-1}}=\frac{i}{n}\mbox{ dla }i\geq 1.

Pozostałe p_{{ij}} są równe 0:

P=\left[\begin{array}[]{cccccc}0&1&0&\ldots&0&0\\
1/n&0&1-1/n&\ldots&0&0\\
0&2/n&0&\ldots&0&0\\
0&0&3/n&\ldots&0&0\\
\ldots 0&0&0&\ldots&0&1/n\\
0&0&0&\ldots&1&0\end{array}\right].
Stwierdzenie 6.1

Załóżmy, że (X_{n}) jest łańcuchem Markowa z macierzą przejścia P=[p_{{ij}}]. Wówczas dla każdej ograniczonej funkcji f:E\to\mathbb{R} i dowolnego n,

\mathbb{E}(f(X_{{n+1}})|X_{0},X_{1},\ldots,X_{n})=\mathbb{E}(f(X_{{n+1}})|X_{n})=\sum _{{j\in E}}f(j)p_{{X_{n}j}}. (*)
Dowód:

Mamy

\begin{split}\mathbb{E}(f(X_{{n+1}})|X_{0},X_{1},\ldots,X_{n})&=\sum _{{j\in E}}\mathbb{E}(f(X_{{n+1}})1_{{\{ X_{{n+1}}=j\}}}|X_{0},X_{1},\ldots,X_{n}\\
&=\sum _{{j\in E}}f(j)\mathbb{P}(X_{{n+1}}=j|X_{0},X_{1},\ldots,X_{n})\\
&=\sum _{{j\in E}}f(j)p_{{X_{n}j}}.\end{split}

Stąd równość skrajnych stron w (*). Aby otrzymać prawą równość, wystarczy powtórzyć powyższe rozumowanie z warunkowaniem tylko po zmiennej X_{n}.

Twierdzenie 6.1

Załóżmy, że (X_{n}), E, P - jak wyżej. Wówczas dla wszystkich n=0,\, 1,\, 2,\,\ldots, k=1,\, 2,\,\ldots, j\in E,

\mathbb{P}(X_{{n+k}}=j|X_{0},X_{1},\ldots,X_{n})=\mathbb{P}(X_{{n+k}}=j|X_{n})=p_{{X_{n}j}}^{{(k)}},

gdzie [p_{{ij}}^{{(k)}}]_{{i,j\in E}}=P^{k}. Macierz tę możemy interpretować jako macierz przejścia w k krokach.

Dowód:

Stosujemy indukcję ze względu na k. Dla k=1 dostajemy definicję łańcucha Markowa. Przypuśćmy, że teza zachodzi dla pewnego k\geq 1. Mamy

\begin{split}\mathbb{P}(X_{{n+k+1}}&=j|X_{0},X_{1},\ldots,X_{n})=\mathbb{E}(1_{{\{ j\}}}(X_{{n+k+1}})|X_{0},X_{1},\ldots,X_{n})\\
&=\mathbb{E}(\mathbb{E}(1_{{\{ j\}}}(X_{{n+k+1}})|X_{0},X_{1},\ldots,X_{{n+1}})|X_{0},X_{1},\ldots,X_{n})\\
&=^{{\!\!\!\!\!\!\!\!\!\mbox{z.ind.}}}\mathbb{E}(p_{{X_{{n+1}}j}}^{{(k)}}|X_{0},X_{1},\ldots,X_{n})\,\,=^{{\!\!\!\!\!\!\!\!\!\mbox{Stw.}}}\,\,\sum _{{i\in E}}p_{{ij}}^{{(k)}}p_{{X_{n}i}}=^{{\!\!\!\!\!\!\!\!\!\mbox{z.ind.}}}p_{{X_{n}j}}^{{(k+1)}}.\end{split}
Wniosek 6.1 (Równanie Chapmana-Kołmogorowa)

Dla wszystkich k,\, n\geq 1 oraz i,j\in E,

p_{{ij}}^{{k+n}}=\sum _{{i\in E}}p_{{il}}^{{k}}p_{{lj}}^{{n}}.
Dowód:

Wynika to natychmiast z równości P^{{(k+n)}}=P^{k}P^{n}.

Stwierdzenie 6.2

Przy założeniach jak wyżej, dla dowolnego n\geq 0 oraz i_{0},\, i_{1},\,\ldots,\, i_{n}\in E,

\mathbb{P}(X_{0}=i_{0},X_{1}=i_{1},\ldots,X_{n}=i_{n})=\mathbb{P}(X_{0}=i_{0})p_{{i_{0}i_{1}}}p_{{i_{1}i_{2}}}\ldots p_{{i_{{n-1}}i_{n}}}.
Dowód:

Mamy

\begin{split}\mathbb{E}(&1_{{\{ i_{0}\}}}(X_{0})1_{{\{ i_{1}\}}}(X_{1})\ldots 1_{{\{ i_{n}\}}}(X_{n}))=\mathbb{E}[\mathbb{E}(\ldots|X_{0},X_{1},\ldots,X_{{n-1}})]\\
&=\mathbb{E}[1_{{\{ i_{0}\}}}(X_{0})1_{{\{ i_{1}\}}}(X_{1})\ldots 1_{{\{ i_{n}\}}}(X_{{n-1}}))\underbrace{\mathbb{P}(X_{n}=i_{n}|X_{0},X_{1},\ldots,X_{{n-1}})}_{{p_{{X_{{n-1}}i_{n}}}=p_{{i_{{n-1}}i_{n}}}}}]\end{split}

itd.

Definicja 6.3

Rozkład zmiennej X_{0} nazywamy rozkładem początkowym. Jest on jednoznacznie wyznaczony przez ciąg (\pi _{i})_{{i\in E}} liczb nieujemnych o sumie 1.

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.

Twierdzenie 6.2

Niech E będzie zbiorem co najwyżej przeliczalnym. Wówczas dla każdej macierzy stochatycznej P oraz miary probabilistycznej \pi na E istnieje przestrzeń probabilistyczna i określony na niej łańcuch Markowa o macierzy przejścia P i rozkładzie początkowym \pi.

6.2. Klasyfikacja stanów

Mówimy, że stan j jest osiągalny ze stanu i, jeśli p_{{ij}}^{{(n)}}>0 dla pewnego n\geq 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\geq 1, p_{{ij}}^{{(m)}}>0 i p_{{jk}}^{{n}}>0, a zatem

p_{{ik}}^{{m+n}}=\sum _{{l\in E}}p_{{il}}^{{m}}p_{{lk}}^{{(n)}}\geq p_{{ij}}^{{(m)}}p_{{jk}}^{{(n)}}>0.

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,\ldots,b-1 są nieistotne.

Zbiór stanów S nazywamy zamkniętym, jeśli dla dowolnego i\in S oraz j\notin 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 p_{{kk}}^{{(n)}}=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=[p_{{ij}}]_{{(i,j)\in E\times 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 [p_{{ij}}]_{{(i,j)]inC\times 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

\left[\begin{array}[]{cccc}1/2&1/2&0&0\\
1/4&3/4&0&0\\
0&1/3&1/2&1/6\\
1/5&1/5&2/5&1/5\end{array}\right].

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 \left[\begin{array}[]{cc}1/2&1/2\\
1/4&3/4\end{array}\right].

Niech

F_{{kj}}=\mathbb{P}(\bigcup _{{n=1}}^{\infty}\{ X_{n}=j\}|X_{0}=k)

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

F_{{kj}}=\sum _{{n=1}}^{\infty}f_{{kj}}(n),

gdzie

f_{{kj}}=\mathbb{P}(X_{1}\neq j,X_{2}\neq j,\ldots,X_{{n-1}}\neq j,X_{n}=j|X_{0}=k)

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

Definicja 6.4

Stan j nazywamy powracającym, jeśli F_{{jj}}=1. Stan j nazywamy chwilowym (tranzytywnym), jeśli F_{{jj}}<1.

Niech N_{j}=\sum _{{n=1}}^{\infty}1_{{\{ X_{n}=j\}}} będzie zmienną losową zliczającą ile razy proces (X_{n}) był w stanie j (nie biorąc pod uwagę zmiennej X_{0}). Mamy następujący fakt.

Stwierdzenie 6.3

(i) Stan j jest powracający wtedy i tylko wtedy, gdy \mathbb{P}(N_{j}=\infty|X_{0}=j)=1.

(ii) Stan j jest chwilowy wtedy i tylko wtedy, gdy \mathbb{P}(N_{j}<\infty|X_{0}=j)=1.

Dowód:

Niech A_{k}=\{proces (X_{n}) był w stanie j co najmniej k razy\}. Oczywiście A_{{k+1}}\subseteq A_{k}, a zatem z twierdzenia o ciagłości

\lim _{{k\to\infty}}\mathbb{P}(A_{k}|X_{0}=i)=\mathbb{P}(\bigcap _{{k=1}}^{\infty}A_{k}|X_{0}=i)=\mathbb{P}(N_{j}=\infty|X_{0}=i).

Wykażemy, że

\mathbb{P}(A_{k}|X_{0}=i)=F_{{ij}}F_{{jj}}^{{k-1}}. (*)

Wówczas dostaniemy (stosując tę równość dla i=j), iż \mathbb{P}(N_{j}=\infty|X_{0}=j)=1 wtedy i tylko wtedy, gdy F_{{jj}}=1 (to teza (i)) oraz \mathbb{P}(N_{j}=\infty|X_{0}=j)=0 wtedy i tylko wtedy, gdy F_{{jj}}<1 (co jest równoważne tezie (ii)).

Pozostaje więc udowodnić (*). Intuicyjnie ten wynik jest jasny: jeśli mamy k razy odwiedzić stan j (przy założeniu, że startujemy z i), to musimy dojść z i do j, a potem k-1 razy powrócić do j po pewnych liczbach kroków. Formalnie, ustalmy n_{1}<n_{2}<\ldots<n_{k}. Mamy

\begin{split}\mathbb{P}&(X_{{n_{l}}}=j\mbox{ dla }l=1,2,\ldots,k,\, X_{n}\neq j\mbox{
dla }n\neq n_{l},\, n\leq n_{k}|X_{0}=i)\\
&=\mathbb{P}(X_{1}\neq j,X_{2}\neq j,\ldots,X_{{n_{1}-1}}\neq j,X_{{n_{1}}}=j|X_{0}=i)\times\\
&\quad\times\prod _{{l=2}}^{k}\big[\mathbb{P}(X_{{n_{{l-1}}+1}}\neq j,X_{{n_{{l-1}}+2}}\neq j,\ldots,X_{{n_{l}-1}}\neq j,X_{{n_{l}}}=j|X_{{n_{{l-1}}}}=j)\big]\\
&=f_{{ij}}(n_{1})\prod _{{l=2}}^{n}f_{{jj}}(n_{l}-n_{{l-1}}).\end{split}

Podstawmy m_{1}=n_{1}, m_{k}=n_{k}-n_{{k-1}}. Mamy, dla i\neq j,

\begin{split}\mathbb{P}(A_{k}|X_{0}=i)&=\sum _{{m_{1},\ldots,m_{k}\geq 1}}f_{{ij}}(m_{1})f_{{jj}}(m_{2})\ldots f_{{jj}}(m_{k})\\
&=\left(\sum _{{m_{1}=1}}^{\infty}f_{{ij}}(m_{1})\right)\prod _{{l=2}}^{k}\left(\sum _{{m_{l}=1}}^{\infty}f_{{jj}}(m_{l})\right)=F_{{ij}}F_{{jj}}^{{k-1}}.\end{split}

Uwaga: W szczególności, \mathbb{P}(N_{j}=\infty|X_{0}=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\in E, liczbę P_{j}=\sum _{{n=1}}^{\infty}p_{{jj}}^{{(n)}}. Na mocy twierdzenia Fubiniego (dla funkcji nieujemnych),

P_{j}=\sum _{{n=1}}^{\infty}\mathbb{E}(1_{{\{ j\}}}(X_{n})|X_{0}=j)=\mathbb{E}(N_{j}|X_{0}=j),

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

Twierdzenie 6.3

(i) Stan j jest chwilowy wtedy i tylko wtedy, gdy P_{j}<\infty.

(ii) Stan j jest powracający wtedy i tylko wtedy, gdy P_{j}=\infty.

Dowód:

Zauważmy, iż na mocy wzoru na prawdopodobieństwo całkowite,

p_{{jj}}^{{(k)}}=\sum _{{m=0}}^{{k-1}}f_{{jj}}(k-m)p_{{jj}}^{{(m)}},

gdzie przyjmujemy p_{{jj}}^{{(0)}}=1. Zatem, na mocy twierdzenia Fubiniego (dla funkcji nieujemnych),

\begin{split}\sum _{{k=1}}^{n}p_{{jj}}^{{(k)}}&=\sum _{{k=1}}^{n}\sum _{{m=0}}^{{k-1}}f_{{jj}}(k-m)p_{{jj}}^{{(m)}}\\
&=\sum _{{m=0}}^{{n-1}}p_{{jj}}^{{(m)}}\sum _{{k=m+1}}^{n}f_{{jj}}(k-m)\leq\sum _{{m=0}}^{n}p_{{jj}}^{{(m)}}F_{{jj}}\\
&=F_{{jj}}+F_{{jj}}\sum _{{m=1}}^{n}p_{{jj}}^{{(m)}},\end{split}

czyli, równoważnie,

(1-F_{{jj}})\sum _{{m=1}}^{n}p_{{jj}}^{{(m)}}\leq F_{{jj}}. (\Delta)

Jeśli stan j jest chwilowy, to (\Delta) daje, iż

P_{j}\leq\frac{F_{{jj}}}{1-F_{{jj}}}<\infty.

I w drugą stronę: jeśli P_{j}<\infty, czyli \mathbb{E}(N_{j}|X_{0}=j)<\infty, to \mathbb{P}(N_{j}=\infty|X_{0}=j)=0 i na mocy poprzedniego twierdzenia j jest stanem chwilowym. To dowodzi (i). Część (ii) jest konsekwencją tego, że każdy stan jest albo chwilowy, albo powracający oraz tego, że P_{j} jest albo skończone, albo nie.

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

p_{{00}}^{{(2n)}}={2n\choose n}p^{n}q^{n}\sim\frac{1}{\sqrt{\pi n}}(4pq)^{n},

na mocy wzoru Stirlinga. Ponadto, p_{{00}}^{{(2n+1)}}=0. Stąd

\sum _{{n=1}}^{\infty}p_{{00}}^{{(n)}}<\infty

wtedy i tylko wtedy,gdy p\neq 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.

Twierdzenie 6.4

Załóżmy, że łańcuch Markowa jest nieprzywiedlny. Wówczas jeśli jeden stan jest chwilowy, to wszystkie są chwilowe; jeśli jeden stan jest powracający, to wszystkie są powracające.

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

Weźmy dwa stany i, j. Istnieją liczby całowite dodatnie r, s takie, że \alpha=p_{{ij}}^{{(r)}}>0, \beta=p_{{ji}}^{{(s)}}>0. Dla n\geq 1 mamy

p_{{ii}}^{{(r+s+n)}}\geq p_{{ij}}^{{(r)}}p_{{jj}}^{{(n)}}p_{{ji}}^{{(s)}}=\alpha\beta p_{{jj}}(n)

i podobnie p_{{jj}}(r+s+n)\geq\alpha\beta p_{{ii}}^{{(n)}}. Zatem dla n>r+s,

\frac{1}{\alpha\beta}p_{{ii}}^{{(r+s+n)}}\geq p_{{jj}}^{{(n)}}\geq\alpha\beta p_{{ii}}^{{(n-r-s)}},

czyli asymptotyczne zachowanie ciągów (p_{{ii}}^{{(n)}})_{n} oraz (p_{{jj}}^{{(n)}})_{n} jest takie samo; w szczególności, \sum _{{n=1}}^{\infty}p_{{ii}}^{{(n)}}=\infty wtedy i tylko wtedy, gdy \sum _{{n=1}}^{\infty}p_{{jj}}^{{(n)}}=\infty.

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).

Stwierdzenie 6.4

Przestrzeń stanów E łańcucha Markowa możemy jednoznacznie przedstawić w postaci

E=C\cup D_{1}\cup D_{2}\cup\ldots,

gdzie C jest zbiorem stanów chwilowych, a D_{i}, i\geq 1 są nieprzywiedlnymi zamkniętymi zbiorami stanów powracających.

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 D_{i}, i\geq 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 D_{i}, i pozostaje tam na zawsze.

6.3. Rozkłady stacjonarne i twierdzenie ergodyczne

Definicja 6.5

Załóżmy, że P jest macierzą stochastyczną. Rozkład \pi na E nazywamy stacjonarnym (niezmienniczym), jeśli \pi P=\pi (tzn. dla wszystkich j\in E, \sum _{{i\in E}}\pi _{i}p_{{ij}}=\pi _{j}.

Rozkład stacjonarny ma następujące własności. Po pierwsze zauważmy, że jeśli \pi jest rozkładem stacjonarnym, to dla każdego n\geq 1, \pi P^{n}=\pi (oczywista indukcja). Innymi słowy, jeśli (X_{n}) jest łańcuchem Markowa o macierzy przejścia P i rozkładzie początkowym \pi, to dla n\geq 1, rozkład X_{n} jest równy \pi. Można nawet powiedzieć więcej: dla wszystkich n\geq 1 oraz dowolnego ciągu m_{1}<m_{2}<\ldots<m_{k} (k\geq 1 również jest dowolne) wektor (X_{{m_{1}}},X_{{m_{2}}},\ldots,X_{{m_{k}}}) ma ten sam rozkład co (X_{{n+m_{1}}},X_{{n+m_{2}}},\ldots,X_{{n+m_{k}}}). Istotnie,

\mathbb{P}(X_{{n+m_{1}}}=j_{1},X_{{n+m_{2}}}=j_{2},\ldots,X_{{n+m_{k}}}=j_{k})
=\sum _{{i\in E}}\pi _{i}p_{{ij_{1}}}^{{m_{1}+n}}p_{{j_{1}j_{2}}}^{{(m_{2}-m_{1})}}\ldots p_{{j_{{k-1}}j_{k}}}^{{(m_{k}-m_{{k-1}})}}=\pi _{{j_{1}}}p_{{j_{1}j_{2}}}^{{(m_{2}-m_{1})}}\ldots p_{{j_{{k-1}}j_{k}}}^{{(m_{k}-m_{{k-1}})}},

co nie zależy od n.

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

Definicja 6.6

Okresem stanu j nazywamy największą taką liczbę n, że powrót do stanu j jest możliwy tylko po liczbie kroków podzielnej przez n: o(j)=NWD\{ n:p_{{jj}}^{{(n)}}>0\}.

Stan nazywamy okresowym jeśli o(j)>1 i nieokresowym, jeśli o(j)=1.

Stwierdzenie 6.5

W nieprzywiedlnym łańcuchu Markowa wszystkie stany mają ten sam okres.

Wobec tego następująca definicja ma sens.

Definicja 6.7

Nieprzywiedlny łańcuch Markowa (X_{n}) nazywamy okresowym, jeśli wszystkie jego stany mają okres większy niż 1. W przeciwnym razie łańcuch nazywamy nieokresowym.

Lemat 6.1

łańcuch jest nieprzywiedlny i nieokresowy wtedy i tylko wtedy, gdy jest spełniony warunek

\forall _{{i,j\in E}}\exists _{{n_{0}}}\forall _{{n\geq n_{0}}}p_{{ij}}^{{(n)}}>0. (O)
Dowód:

Oczywiście wystarczy tylko udowodnić implikację \Rightarrow. Ustalmy i,\, j\in E oraz liczbę m taką, że p_{{ij}}^{{(m)}}>0. Z definicji nieokresowości, istnieją liczby względnie pierwsze n_{1},\, n_{2},\,\ldots,\, n_{k} takie, że p_{{jj}}^{{(n_{l})}}>0, l=1,\, 2,\,\ldots,\, k. Jeśli n jest dostatecznie duże, to

n=a_{1}n_{1}+a_{2}n_{2}+\ldots+a_{k}n_{k},\,\qquad\mbox{dla pewnych }a_{l}\in\mathbb{Z}_{+},

i mamy

p_{{jj}}^{{(n)}}\geq\prod _{{l}}p_{{jj}}^{{(a_{l}n_{l})}}\geq\prod _{l}(p_{{jj}}^{{(n_{l})}})^{{a_{l}}}>0.

Zatem

p_{{ij}}^{{(m+n)}}\geq p_{{ij}}^{{(m)}}p_{{jj}}^{{(n)}}>0

o ile m+n jest dostatecznie duże.

Twierdzenie 6.5

Załóżmy, że warunek (O) jest spełniony i istnieje rozkład stacjonarny \pi. Wówczas każdy stan jest powracalny, rozkład stacjonarny jest jednoznaczny oraz dla wszystkich i,\, j\in E,

\lim _{{n\to\infty}}p_{{ij}}^{{(n)}}=\pi _{j}.

Uwaga: Jak widać, przy założeniach twierdzenia, p_{{ij}}^{{(n)}} ,,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ł.

Dowód:

Dowód przeprowadzimy w pięciu krokach.

1. Wszystkie stany są albo powracalne, albo chwilowe. Załóżmy, że ma miejsce ta druga możliwość. Liczba \sum _{{n=1}}^{\infty}p_{{ij}}^{{(n)}} jest średnim czasem przebywania w stanie j przy założeniu startowania ze stanu i. Na mocy własności Markowa, mamy zatem

\sum _{{k=1}}^{\infty}p_{{ij}}^{{(n)}}=F_{{ij}}P_{j}<\infty,

a zatem p_{{ij}}^{{(n)}}\to 0 gdy n\to\infty. Z drugiej strony, dla każdego j\in E,

\sum _{{i\in E}}\pi _{i}p_{{ij}}^{{(n)}}=\pi _{j}

i lewa strona dąży do 0 na mocy tw. Lebesgue'a o zmajoryzowanym przejściu do granicy. Stąd \pi\equiv 0 i sprzeczność.

2. Rozważmy nową przestrzeń stanów E\times E oraz macierz przejścia P^{{\otimes 2}} na tej przestrzeni, o wyrazach p_{{(i,j)(k,l)}}=p_{{ik}}p_{{jl}} (oczywiście jest to macierz stochastyczna). Niech \pi^{{\otimes 2}}=(\pi _{i}\cdot\pi _{j})_{{(i,j)\in E\times E}} będzie rozkładem na E\times E: jest to rozkład stacjonarny dla P^{{\otimes 2}}. Niech (X_{n}^{{\prime}},X_{n}^{{\prime\prime}}) będzie łańcuchem Markowa z tą macierzą przejścia: (X_{n}^{{\prime}}) oraz (X_{n}^{{\prime\prime}}) to dwa niezależne łańcuchy Markowa o macierzach przejścia P, startujące ze stanów i, j, odpowiednio. Ponieważ będziemy zmieniać te punkty startowe, wygodnie nam będzie pracować na miarach probabilistycznych \mathbb{P}_{{ij}}=\mathbb{P}(\cdot|X_{0}^{{\prime}}=i,X_{0}^{{\prime\prime}}=j). Jak łatwo sprawdzić, warunek (O) jest spełniony; zatem na mocy kroku 1., z każdego stanu (i,j) można dojść do każdego innego; w szczególności do stanu (k,k). Zatem dla wszystkich i,\, j\in E, \mathbb{P}_{{ij}}(X_{n}^{{\prime}}=X_{n}^{{\prime\prime}} dla pewnego n)=1.

3. Niech \tau=\inf\{ n:X_{n}^{{\prime}}=X_{n}^{{\prime\prime}}\}. Definiujemy

(Y_{n}^{{\prime}},Y_{n}^{{\prime\prime}})=\begin{cases}(X_{n}^{{\prime}},X_{n}^{{\prime\prime}})&\mbox{dla }n<\tau,\\
(X_{n}^{{\prime}},X_{n}^{{\prime}})&\mbox{dla }n\geq\tau.\end{cases}

Z powyższej dyskusji wynika, że dla wszystkich i,\, j\in E,

\lim _{{n\to\infty}}\mathbb{P}_{{ij}}(Y_{n}^{{\prime}}\neq Y_{n}^{{\prime\prime}})=0.

Sprawdzimy teraz, że (Y_{n}^{{\prime}}), (Y_{n}^{{\prime\prime}}) są łańcuchami Markowa (względem miary probabilistycznej \mathbb{P}_{{ij}}) z macierzą przejścia P. Ograniczymy się tylko do procesu (Y_{n}^{{\prime\prime}});w przypadku (Y_{n}^{{\prime}}) przekształcenia są analogiczne.

\begin{split}\mathbb{P}_{{ij}}(Y_{{n+1}}^{{\prime\prime}}=k|X_{s}^{{\prime}},X_{s}^{{\prime\prime}},s\leq n)&=\mathbb{P}_{{ij}}(Y_{{n+1}}^{{\prime\prime}}=k,\tau<n|X_{s}^{{\prime}},X_{s}^{{\prime\prime}},s\leq n)\\
&\,\,\,+\mathbb{P}_{{ij}}(Y_{{n+1}}^{{\prime\prime}}=k,\tau\geq n|X_{s}^{{\prime}},X_{s}^{{\prime\prime}},s\leq n)\\
&=\mathbb{P}_{{ij}}(X_{{n+1}}^{{\prime}}=k|X_{s}^{{\prime}},X_{s}^{{\prime\prime}},s\leq n)1_{{\{\tau<n\}}}\\
&\,\,\,+\mathbb{P}_{{ij}}(X_{{n+1}}^{{\prime\prime}}=k|X_{s}^{{\prime}},X_{s}^{{\prime\prime}},s\leq n)1_{{\{\tau\geq n\}}}\\
&=\mathbb{P}_{{ij}}(X_{{n+1}}^{{\prime}}=k|X_{s}^{{\prime}},s\leq n)1_{{\{\tau<n\}}}\\
&\,\,\,+\mathbb{P}_{{ij}}(X_{{n+1}}^{{\prime\prime}}=k|X_{s}^{{\prime\prime}},s\leq n)1_{{\{\tau\geq n\}}}\\
&=p_{{X_{n}^{{\prime}}k}}1_{{\{\tau<n\}}}+p_{{X_{n}^{{\prime\prime}}k}}1_{{\{\tau\geq n\}}}=p_{{Y_{n}^{{\prime\prime}}k}}\end{split}

i wystarczy obłożyć obie strony warunkową wartością oczekiwaną względem ciągu Y_{0}^{{\prime\prime}},Y_{1}^{{\prime\prime}},\ldots,Y_{n}^{{\prime\prime}}.

4. Pokażemy, że dla i,\, j,\, k\in E, |p_{{ik}}^{{(n)}}-p_{{jk}}^{{(n)}}|\to 0. Mamy |\mathbb{P}(A)-\mathbb{P}(B)|\leq\mathbb{P}(A\setminus B)+\mathbb{P}(B\setminus A), więc

\begin{split}|p_{{ik}}^{{(n)}}-p_{{jk}}^{{(n)}}|&=|\mathbb{P}_{{ij}}(Y_{n}^{{\prime}}=k)-\mathbb{P}_{{ij}}(Y_{n}^{{\prime\prime}}=k)|\\
&\leq\mathbb{P}_{{ij}}(Y_{n}^{{\prime}}=k,Y_{n}^{{\prime\prime}}\neq k)+\mathbb{P}_{{ij}}(Y_{n}^{{\prime}}\neq k,Y_{n}^{{\prime\prime}}=k)\\
&\leq\mathbb{P}_{{ij}}(Y_{n}^{{\prime}}\neq Y_{n}^{{\prime\prime}})\to 0.\end{split}

5. Mamy, dla wszystkich k\in E, \sum _{{i\in E}}\pi _{i}p_{{ik}}^{{(n)}}=\pi _{k}, skąd, na mocy poprzedniej części oraz twierdzenia Lebesgue'a,

\pi _{k}-p_{{jk}}^{{(n)}}=\sum _{{i\in E}}\pi _{i}(p_{{ik}}^{{(n)}}-p_{{jk}}^{{(n)}})\to 0.

Jednoznaczność rozkładu stacjonarnego jest oczywista: \pi _{k} jest wyznaczony jako granice p_{{ik}}^{{(n)}}.

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

Twierdzenie 6.6

Jeśli E jest zbiorem skończonym i zachodzi warunek (O), to istnieje rozkład stacjonarny i zachodzi teza poprzedniego twierdzenia.

6.4. Zadania

1. Niech E będzie pewnym zbiorem przeliczalnym. Dany jest ciąg (X_{n}) niezależnych zmiennych losowych oraz ciąg funkcyjny (f_{n}), f_{n}:E\times\mathbb{R}\to E. Definiujemy ciąg (Y_{n}) wzorem

Y_{{n+1}}=f(Y_{n},X_{n}),\  n=0,1,2,\ldots,

gdzie Y_{0} jest pewną zmienną losową o wartościach w E. Dowieść, że (Y_{n}) jest łańcuchem Markowa.

2. Dany jest łańcuch Markowa (X_{n}) na pewnej przestrzeni E oraz różnowartościowa funkcja f:E\to E. Wykazać, że (f(X_{n})) jest łańcuchem Markowa. Co jeśli f nie jest różnowartościowa?

3. Dany jest ciąg (X_{n}) niezależnych zmiennych losowych o tym samym rozkładzie P(X_{n}=\pm 1)=\frac{1}{2}. Rozstrzygnąć, które z podanych niżej procesów są łańcuchami Markowa:

U_{0}=0,\quad U_{n}=X_{1}+X_{2}+\ldots+X_{n},n\geq 1,
W_{n}=X_{0}X_{1}\cdot X_{2}\cdot\ldots X_{n},\, n\geq 0,
V_{n}=(-1)^{{U_{n}}},\, n\geq 0,
Y_{n}=X_{n}\cdot X_{{n+1}},\, n\geq 0,
Z_{n}=\frac{X_{n}+X_{{n+1}}}{2},\, n\geq 0.

4. Dany jest ciąg (X_{n}) niezależnych zmiennych losowych o tym samym rozkładzie \mathbb{P}(X_{n}=1)=p=1-\mathbb{P}(X_{n}=-1), p\in(0,1). Niech S_{n}=X_{1}+X_{2}+\ldots+X_{n}, n=1,2,\ldots. Udowodnić, że ciągi

Y_{n}=|S_{n}|,\  Z_{n}=\max _{{k\leq n}}S_{k}-S_{n}

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 (X_{n})_{n} na przestrzeni E=\{ 1,2,3,4\} dana jest następująco:

\mathbb{P}=\left(\begin{array}[]{cccc}0&\frac{1}{2}&\frac{1}{2}&0\\
\frac{1}{4}&\frac{1}{2}&0&\frac{1}{4}\\
\frac{2}{3}&0&0&\frac{1}{3}\\
0&\frac{2}{3}&\frac{1}{3}&0\end{array}\right).
  • a) Jakie jest prawdopodobieństwo dojścia w dwóch krokach ze stanu 1 do stanu 2?

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

  • c) Zakładając, że X_{0}=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 (X_{n}) jest łańcuchem Markowa.

(i) Czy dla dowolnego n\geq 0, liczb 0\leq i_{0}<i_{1}<\ldots<i_{k}=n oraz stanów a_{0}, a_{1}, \ldots, a_{{k+1}} mamy

\begin{split}\mathbb{P}(X_{{n+1}}&=a_{{k+1}}|X_{{i_{k}}}=a_{k},X_{{i_{{k-1}}}}=a_{{k-1}},\ldots,X_{{i_{0}}}=a_{0})\\
&=\mathbb{P}(X_{{n+1}}=a_{{k+1}}|X_{{i_{k}}}=a_{k})?\end{split}

(ii) Czy dla dowolnego n\geq 0, liczb 0\leq i_{0}<i_{1}<\ldots<i_{k}=n oraz zbiorów A_{0}, A_{1}, \ldots, A_{{k+1}} mamy

\begin{split}\mathbb{P}(X_{{n+1}}&\in A_{{k+1}}|X_{{i_{k}}}\in A_{k},X_{{i_{{k-1}}}}\in A_{{k-1}},\ldots,X_{{i_{0}}}\in A_{0})\\
&=\mathbb{P}(X_{{n+1}}\in A_{{k+1}}|X_{{i_{k}}}\in A_{k})?\end{split}

11. Dany jest łańcuch Markowa (X_{n}) o macierzy przejścia P, której każdy wiersz jest taki sam. Udowodnić, że zmienne X_{0}, X_{1}, \ldots są niezależne.

12. Dany jest łańcuch Markowa (X_{n}) startujący ze stanu i. Niech \tau=\inf\{ n\geq 1:X_{n}\neq i\}. Udowodnić, że \tau ma rozkład geometryczny.

13. Rozważamy błądzenie losowe po \mathbb{Z}^{2}: stan (i,j)\in\mathbb{Z}^{2} komunikuje się w jednym kroku z każdym ze stanów (i\pm 1,j), (i,j\pm 1) z prawdopodobieństwem 1/4. Udowodnić, że wszystkie stany są powracalne. Udowodnić, że nie istnieje rozkład stacjonarny.

14. Niech \alpha będzie ustaloną liczbą dodatnią. Dany jest łańcuch Markowa na E=\{ 1,\, 2,\,\ldots\} startujący z 1, o następujących prawdopodobieństwach przejścia: stan k\in E prowadzi w jednym kroku do 1 z prawdopodobieństwem (k+1)^{{-\alpha}} oraz do k+1 z prawdopodobieństwem 1-(k+1)^{{-\alpha}}. Czy łańcuch jest okresowy? Czy jest nieprzywiedlny? Dla jakich \alpha łańcuch jest powracalny? Dla jakich \alpha istnieje rozkład stacjonarny?

15. Dany jest spójny graf (W,K) o skończonej liczbie wierzchołków oraz łańcuch Markowa o wartościach w V taki, że z każdego wierzchołka x\in V można w jednym kroku dojść do jednego z wierzchołków sąsiadujących z x. Niech n(x) oznacza liczbę sąsiadów x. Udowodnić, że \pi _{x}=n(x)/(2|K|) jest rozkładem stacjonarnym.

16. W modelu dyfuzji (przykład 5) powyżej) z n=20, załóżmy, że w chwili 0 nie ma żadnej cząstki w pojemniku I. Wyznaczyć przybliżone prawdopodobieństwo tego, że w chwili 10000 nie będzie żadnej cząstki w I pojemniku.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.