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

Ł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 $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 10.1.[ł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:

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

2. 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$,

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

4. $\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.

{{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 ($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:

animacja 101.gif

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:

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

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

animacja 102.gif

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.