Zagadnienia

6.1 Podstawowe definicje
6.2 Klasyfikacja stanów
6.3 Rozkłady stacjonarne i twierdzenie ergodyczne
6.4 Zadania

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.

Wykład z Rachunku Prawdopodobieństwa II

Zagadnienia

6. Łańcuchy Markowa

6.1. Podstawowe definicje

Definicja 6.1

Definicja 6.2

Stwierdzenie 6.1

Dowód:

Twierdzenie 6.1

Dowód:

Wniosek 6.1 (Równanie Chapmana-Kołmogorowa)

Dowód:

Stwierdzenie 6.2

Dowód:

Definicja 6.3

Twierdzenie 6.2

6.2. Klasyfikacja stanów

Definicja 6.4

Stwierdzenie 6.3

Dowód:

Twierdzenie 6.3

Dowód:

Twierdzenie 6.4

Stwierdzenie 6.4

6.3. Rozkłady stacjonarne i twierdzenie ergodyczne

Definicja 6.5

Definicja 6.6

Stwierdzenie 6.5

Definicja 6.7

Lemat 6.1

Dowód:

Twierdzenie 6.5

Dowód:

Twierdzenie 6.6

6.4. Zadania