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

Streszczenie

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.

Słowa kluczowe: łańcuch Markowa, macierz przejścia, spacer losowy, nieredukowalność, powracanie, okresowość, ergodyczność.

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 $E\subset {\mathbb{ℝ}}^d$ będzie zbiorem skończonym lub

przeliczalnym oraz niech

$\mathbf{𝐏}:E\times E⟶\mathbb{ℝ}\text{i}\mathbf{𝐩}:E⟶\mathbb{ℝ}$

będą ustalonymi funkcjami.

Będziemy myśleć o $\mathbf{𝐏}$ i $\mathbf{𝐩}$ jako o skończonej lub przeliczalnej macierzy AG $\mathbf{𝐏}(i,j)$ oraz wektorze AG o współrzędnych $\mathbf{𝐩}(i)$, gdzie $i,j\in E$.

Definicja łańcuch Markowa

Niech będzie dany ciąg wektorów losowych $X_n$, $n=0,1,2,\dots$, zdefiniowanych na przestrzeni probabilistycznej $(\mathrm{\Omega },\mathrm{\Sigma },P)$ i przyjmujących wartości w ${\mathbb{ℝ}}^d$. Mówimy, że $\{X_n\}$ jest łańcuchem Markowa, jeżeli spełnione są następujące warunki:

$P(X_0=i)=\mathbf{𝐩}(i)$ dla każdego $i\in E$,

dla każdego $n\ge 0$ zachodzi równość:

$P(X_{n+1}=i_{n+1}|(X_0=i_0,\dots ,X_n=i_n))$ $=P(X_{n+1}=i_{n+1}|X_n=i_n)=\mathbf{𝐏}(i_n,i_{n+1}),$

dla wszystkich $i_0,\dots ,i_{n+1}\in E$,

$\sum _{i\in E}\mathbf{𝐩}(i)=1$,

$\sum _{j\in E}\mathbf{𝐏}(i,j)=1$ dla każdego $i\in E$.

Powyższe warunki mają prostą interpretację. Mianowicie, utożsamiamy zbiór $E$ ze zbiorem wszystkich możliwych stanów pewnego systemu. Wówczas $X_n$ oznacza stan, w którym znajduje się nasz system w chwili czasowej $n$. Warunek, że $X_n$ 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 $E$, gdyż:

$P(X_0\in E)=\sum _{i\in E}{\mathbf{𝐩}}_i=1,$

zaś warunek 4 implikuje następującą równość dla wszystkich $i\in E$:

$P(X_{n+1}\in E|X_n=i)=\sum _{j\in E}P(X_{n+1}=j|X_n=i)=\sum _{j\in E}\mathbf{𝐏}(i,j)=1.$

W związku z powyższą interpretacją, $E$ będziemy nazywać zbiorem stanów lub przestrzenią stanów, $\mathbf{𝐩}$ -- rozkładem początkowym, zaś $\mathbf{𝐏}$ -- 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.

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 ($1$, $2$, $3$ i tak dalej) może się przesuwać o jeden w lewo lub o jeden w prawo, z prawdopodobieństwami odpowiednio $q$ oraz $p$, przy czym $p+q=1$. Jeżeli $p=q=\frac{1}{2}$ to mówimy, że spacer losowy jest standardowy.

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

Okazuje się, że spacer losowy po prostej jest łańcuchem Markowa. Rzeczywiście, stanami są wszystkie możliwe liczby całkowite, czyli $E=\mathbb{\mathbb{Z}}\subset \mathbb{ℝ}$, natomiast $X_n$ oznacza pozycję cząsteczki w chwili $n$. Zdefiniujmy:

$\begin{array}{llc}\mathbf{𝐩}(i)=1& \text{ dla }& i=0,\\ \mathbf{𝐩}(i)=0& \text{ dla }& i\ne 0\end{array}$

oraz

$\begin{array}{lll}\mathbf{𝐏}(i,j)=q& \text{ dla }& j=i-1,\\ \mathbf{𝐏}(i,j)=p& \text{ dla }& j=i+1,\\ \mathbf{𝐏}(i,j)=0& \text{ dla }& j\notin \{i-1,i+1\}.\end{array}$

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 $r$ (wtedy oczywiście zakładamy, że $p+q+r=1$). 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 $A$ i $B$, gdzie $A<0<B$, to zbiór $E$ składa się $A+B+1$ stanów, zaś $(A+B+1)$-wymiarowa macierz $\mathbf{𝐏}$ może być zdefiniowana w następujący sposób:

$\mathbf{𝐏}=\left[\begin{array}{cccccc}sa& 1-sa& 0& 0& \cdots & 0\\ q& r& p& 0& \ddots & ⋮\\ 0& \ddots & \ddots & \ddots & \ddots & 0\\ 0& \ddots & \ddots & \ddots & \ddots & 0\\ ⋮& \ddots & 0& q& r& p\\ 0& \cdots & 0& 0& 1-sb& sb\end{array}\right].$

Liczby $sa$ oraz $sb$ oznaczają prawdopodobieństwa tego, że cząsteczka jest pochłaniana przez barierę $A$ lub $B$. 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:

tutaj rysunek 101.eps

Tutaj ekrany ustawiono w punktach $-3$ i $3$,

parametry wynoszą:

$p=q=0.5,r=0,sa=sb=0.8,$

zaś wykonanych jest 30 kroków.

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

$p=0.1,q=0.15,r=0.75,sa=sb=0.4.$

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

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

$X_0=i\text{ oraz }{X}_{n+1}=X_n+{\xi }_{n+1}\text{ dla }n=0,1,2,\dots ,$

gdzie ${\xi }_1,{\xi }_2,{\xi }_3,\dots$ są niezależnymi zmiennymi losowymi, przyjmującymi wartości $-1$, $0$, $1$ z prawdopodobieństwami, odpowiednio, $q$, $r$ i $p$.

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

Dla uproszczenia załóżmy, że $p=q=\frac{1}{2}$, czyli także, że $r=0$. Dla $i=(i_1,\dots ,i_d)\in {\mathbb{\mathbb{Z}}}^d$ mamy:

$X_0=i\text{ oraz }{X}_{n+1}=X_n+{\xi }_{n+1}\text{ dla }n=0,1,2,\dots$

Tym razem ${\xi }_1,{\xi }_2,{\xi }_3,\dots$ są niezależnymi wektorami losowymi, przyjmującymi $2^d$ wartości $({\epsilon }_1,\dots ,{\epsilon }_d)$, gdzie ${\epsilon }_j=\pm 1$, z jednakowym prawdopodobieństwem $\frac{1}{2^d}$.

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

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

Załóżmy, że dwaj gracze, powiedzmy Antoni i Bolesław, mają kapitał, odpowiednio, $A$ i $B$ 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 $p$, zaś prawdopodobieństwo wygrania przez Bolesława wynosi $q$. Zakładamy, że $p+q\le 1$ i oznaczamy przez $r$ prawdopodobieństwo remisu, czyli $r=1-p-q$. Oznaczmy kapitał Antoniego po zakończeniu $n$-tej gry przez $X_n$. Zauważmy, że opisana sytuacja jest faktycznie spacerem losowym, startującym w punkcie $A$ i mającym bariery pochłaniające w punktach $0$ oraz $A+B$.

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\mathbf{P}}(i,i-1)= \left(\frac{i}{k}\right)^2, \ \ \ \ {\mathbf{P}}(i,i+1) = \left(\frac{k - i}{k}\right)^2, \ \ \ \ {\mathbf{P}}(i,i) = \frac{2(k-i)i}{k^2}. }

Badanie własności łańcuchów Markowa zaczniemy od wyznaczenia rozkładów wektorów losowych $X_n$, co sprowadza się do wyznaczenia, dla wszystkich $n\ge 1$, funkcji (wektorów) ${\mathbf{𝐩}}_n:E⟶\mathbb{ℝ}$ takich, że:

${\mathbf{𝐩}}_n(j)=P(X_n=j)\text{<mrow data-mjx-texclass="ORD">dla</mrow>}j\in E.$

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

${\mathbf{𝐩}}_n(j)=P(X_n=j)=\sum _{i\in E}P(X_n=j|X_{n-1}=i)P(X_{n-1}=i)$ $=\sum _{i\in E}\mathbf{𝐏}(i,j){\mathbf{𝐩}}_{n-1}(i),$

czyli:

${\mathbf{𝐩}}_n={\mathbf{𝐏}}^T{\mathbf{𝐩}}_{n-1},$

gdzie ${\mathbf{𝐏}}^T$ oznacza macierz transponowaną AG do macierzy $\mathbf{𝐏}$. Oznaczając $n$-tą potęgę macierzy $\mathbf{𝐏}$ przez ${\mathbf{𝐏}}^n$, otrzymujemy wreszcie poszukiwany rozkład:

${\mathbf{𝐩}}_n={\left({\mathbf{𝐏}}^T\right)}^n{\mathbf{𝐩}}_0.$

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

${\mathbf{𝐩}}_n(j)={\mathbf{𝐏}}^n(i,j)\text{ dla wszystkich }n,$

co nieco wyjaśnia znaczenie wyrazów ${\mathbf{𝐏}}^n(i,j)$ macierzy ${\mathbf{𝐏}}^n$.

Niech teraz $A$ oznacza zbiór opisany przez wektory losowe $X_0,\dots X_{n-1}$, co oznacza, że $A$ ma postać:

$A=\bigcup \{X_0=i_0,\dots ,X_{n-1}=i_{n-1}\},$

gdzie suma jest brana po pewnym zbiorze indeksów $i_0,\dots ,i_{n-1}$ -- zbiór tych indeksów oznaczmy przez $B$. Wówczas:

$P(X_{n+1}=j|(X_n=i\text{ oraz }A))=\mathbf{𝐏}(i,j).$

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

$P(X_{n+1}=j|(X_n=i\text{ oraz }A))=\frac{P(X_{n+1}=j,X_n=i,A)}{P(X_n=i,A)}$ $=\frac{\sum P(X_{n+1}=j,X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0)}{\sum P(X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0)},$

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

$P(X_{n+1}=j,X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0)$ $=P(X_{n+1}=j|(X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0))$ $\cdot P(X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0)$ $=P(X_{n+1}=j|X_n=i)P(X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0)$ $=\mathbf{𝐏}(i,j)P(X_n=i,X_{n-1}=i_{n-1},\dots ,X_0=i_0),$

co daje wzór (Uzupelnic eq:markov1|).

Kolejne twierdzenie prezentuje inną (bardziej ogólną) interpretację wyrazów ${\mathbf{𝐏}}^n(i,j)$ macierzy ${\mathbf{𝐏}}^n$, jako prawdopodobieństw przejścia w $n$ krokach ze stanu $i$ do stanu $j$.

Twierdzenie

Dla każdego $n\ge 1$ oraz $i,j\in E$ mamy:

$P(X_{k+n}=j|X_k=i)={\mathbf{𝐏}}^n(i,j).$

Dowód. Dla $n=1$ formuła (Uzupelnic eq:markov2|) jest konsekwencją własności 2 w definicji Uzupelnic dlm|. Dla przeprowadzenia kroku indukcyjnego załóżmy, że wzór (Uzupelnic eq:markov2|) zachodzi dla pewnego $n$. Mamy wówczas:

$P(X_{k+(n+1)}=j|X_k=i)=\frac{P(X_{k+n+1}=j,X_k=i)}{P(X_k=i)}$ $=\frac{\sum _{l\in E}P(X_{k+n+1}=j,X_{k+n}=l,X_k=i)}{P(X_k=i)}$ $=\frac{\sum _{l\in E}P(X_{k+n+1}=j|X_{k+n}=l,X_k=i)P(X_{k+n}=l,X_k=i)}{P(X_k=i)}.$

Korzystając ze wzoru (Uzupelnic eq:markov1|) oraz z założenia indukcyjnego dostajemy:

$P(X_{k+(n+1)}=j|X_k=i)$ $=\frac{\sum _{l\in E}\mathbf{𝐏}(l,j)P(X_{k+n}=l|X_k=i)P(X_k=i)}{P(X_k=i)}$ $=\sum _{l\in E}{\mathbf{𝐏}}^n(i,l)\mathbf{𝐏}(l,j)={\mathbf{𝐏}}^{n+1}(i,j),$

a więc dowiedliśmy wzór (Uzupelnic eq:markov2|) dla $n+1$, co kończy dowód. {$◻$}

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 $i$ oraz $j$ prawdopodobieństwo przejścia $P^k(i,j)$ jest dodatnie dla pewnego $k=k(i,j)$. Ł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 $f_n(i)$ oznaczmy prawdopodobieństwo pierwszego powrotu do stanu $i$ w dokładnie $n$ krokach, czyli:

$f_n(i)=P(X_n=i,X_{n-1}\ne i,\dots ,X_1\ne i|X_0=i).$

Określmy $F(i)$ jako:

$F(i)=\sum _{n=1}^{\mathrm{\infty }}{f}_n(i)$

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

Oczywiście, $F(i)\le 1$. Będziemy mówić, że stan $i$ jest powracający, jeżeli $F(i)=1$, zaś niepowracający -- jeżeli $F(i)<1$. 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:

$\mathbf{𝐏}(i)=\sum _{n=1}^{\mathrm{\infty }}{\mathbf{𝐏}}^n(i,i).$

Twierdzenie

Niech $i\in E$ będzie ustalonym stanem nieredukowalnego łańcucha Markowa. Wtedy: [#] stan $i$ jest powracający wtedy i tylko wtedy,

gdy: $\mathbf{𝐏}(i)=\mathrm{\infty },$ jeżeli $i$ jest stanem niepowracającym, to: $F(i)=\frac{\mathbf{𝐏}(i)}{1+\mathbf{𝐏}(i)}.$

Liczby $\mathbf{𝐏}(i)$ mają także nieco inną interpretację, którą prezentuje poniższe twierdzenie. Oznaczmy przez $r_i$ liczbę wszystkich powrotów do stanu $i$.

Twierdzenie

Dla każdego $i\in E$: $\mathbb{𝔼}\left(r_i\right)=\mathbf{𝐏}(i).$

Dowód. Załóżmy, że w chwili $0$ system znajdował

się w stanie

$i$

. W takim razie:

$\mathbf{𝐩}(i)=1\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}\mathbf{𝐩}(j)=0\text{<mrow data-mjx-texclass="ORD">dla</mrow>}j\ne i.$

Mamy więc:

$P(X_n=i)=P(X_n=i|X_0=i)={\mathbf{𝐏}}^n(i,i).$

Wiemy, że (patrz zadanie Uzupelnic zfch|):

$\mathbb{𝔼}(I_{\{X_n=i\}})=P(X_n=i),$

zatem:

$\mathbb{𝔼}(r_i)=\mathbb{𝔼}(\sum _{n=1}^{\mathrm{\infty }}{I}_{\{X_n=i\}})=\sum _{n=1}^{\mathrm{\infty }}P(X_n=i)=\sum _{n=1}^{\mathrm{\infty }}{\mathbf{𝐏}}^n(i,i)=\mathbf{𝐏}(i).$

{$◻$}

Rozważmy jednowymiarowy spacer losowy bez barier z prawdopodobieństwami $p=q=\frac{1}{2}$ (patrz przykład Uzupelnic markov1|). Wyraźnie widać, że jest to nieredukowalny łańcuch Markowa oraz że:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathbf{P}^n(i,i) = {\mathbf{P}}^n(0,0) \;\; \textrm{dla każdego } i \in {\Bbb Z}.}

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle {\mathbf{P}}^n(0,0) = \left\{\begin{array} {rl} 0, & \mbox{ gdy } n = 2k - 1\\[2mm] \frac{\left(\begin{array} {@{}c@{}}2k\\k\end{array} \right)}{\displaystyle 2^{2k}}, & \mbox{ gdy } n = 2k. \end{array} \right. }

Teraz:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle {\mathbf{P}}(i) = \sum_{n=1}^\infty{\mathbf{P}}^n(i,i)=\sum_{n=1}^\infty{\mathbf{P}}^n(0,0) = \sum_{k=1}^\infty \frac{\left(\begin{array} {@{}c@{}}2k\\k\end{array} \right)}{\displaystyle 2^{2k}}. }

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

{active}{1d}{sum(binomial(2*k,k)/4^k,k=1..infinity);}{}

$\mathrm{\infty }$

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 Uzupelnic markov3|) jest powracający, natomiast spacer losowy w przestrzeni o wymiarze co najmniej trzy nie jest powracający -- wrócimy do tego problemu w ćwiczeniu Uzupelnic cwsl|.

Rozważmy nieredukowalny łańcuch Markowa i ustalmy pewien jego stan $i\in E$. Ponieważ $i$ komunikuje się z samym sobą, zatem istnieje liczba $n\ge 1$ taka, że ${\mathbf{𝐏}}^n(i,i)>0$ -- niech $N_i$ oznacza zbiór wszystkich takich liczb $n$. Zauważmy, że:

$m,n\in N_i⟹m+n\in N_i.$

Wynika to z następującej

(ogólniejszej) obserwacji: dla wszystkich stanów $i$, $j$ oraz $k$:

${\mathbf{𝐏}}^{m+n}(i,j)=\sum _{l\in E}{\mathbf{𝐏}}^m(i,l){\mathbf{𝐏}}^n(l,j)\ge {\mathbf{𝐏}}^m(i,k){\mathbf{𝐏}}^n(k,j),$

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

${\mathbf{𝐏}}^{m+n}(i,i)\ge {\mathbf{𝐏}}^m(i,i){\mathbf{𝐏}}^n(i,i)>0.$

Mówimy, że stan $i$ jest okresowy o okresie $\nu >1$, jeżeli $\nu$ jest największym wspólnym podzielnikiem liczb ze zbioru $N_i$. Można udowodnić, że w nieredukowalnym łańcuchu Markowa zachodzi dokładnie jeden z następujących warunków: [#] wszystkie stany są okresowe i mają wspólny okres,

ż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 Uzupelnic markov1| jest okresowy o okresie 2, natomiast jego nie posiadająca ekranów modyfikacja, dla której $p+q<1$, nie jest okresowa. Pamiętajmy jednak, iż sam warunek $p+q=1$ 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 $X_n$, o ile oczywiście taki rozkład istnieje. Poniżej prezentujemy tak zwane twierdzenie ergodyczne, które opisuje właśnie taką sytuację.

Twierdzenie

Rozważamy nieredukowalny łańcuch Markowa o skończonej liczbie stanów $k$ (to znaczy $\mathrm{\#}E=k$) i macierzy przejścia $\mathbf{𝐏}$. Wówczas zachodzi dokładnie jeden z następujących warunków:

łańcuch jest okresowy,

istnieje wektor $\pi$ o współrzędnych ${\pi }_1$, , ${\pi }_k$ taki, że:

${\pi }_i>0$ dla wszystkich $i\in E$,

dla wszystkich $i,j\in E$:

$\underset{n\to \mathrm{\infty }}{\lim }{\mathbf{𝐏}}^n(i,j)={\pi }_j,$

wektor $\pi$ jest jedynym rozwiązaniem równania:

${\mathbf{𝐏}}^{T}x=x,$ spełniającym warunek: $\sum _{i\in E}{x}_i=1.$

Jeżeli spełniony jest warunek 2 z powyższego twierdzenia, to łańcuch Markowa nazywamy ergodycznym, zaś wektor $\pi$ -- jego rozkładem stacjonarnym. Mówiąc niezbyt precyzyjnie, ergodyczność oznacza, że dla dużych $n$ prawdopodobieństwo przejścia ze stanu $i$ do stanu $j$ w $n$ krokach jest dodatnie i zależy faktycznie od stanu końcowego $j$, zaś nie zależy od stanu początkowego $i$ -- 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 Uzupelnic cetw| "sprawdzimy" to twierdzenie eksperymentalnie.