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 (patrz wykład z Algebry liniowej z geometrią analityczną) $\mathbf{𝐏}(i,j)$ oraz wektorze (patrz wykład z Algebry liniowej z geometrią analityczną) 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:

<flash>file=Rp101.swf|width=500|height=500</flash>

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$

<flash>file=Rp102.swf|width=500|height=500</flash>

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

Przykład 10.3

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.

Przykład 10.4

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.

Przykład 10.5

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

Przykład 10.6

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:

$\mathbf{𝐏}(i,i-1)={\left(\frac{i}{k}\right)}^2,\mathbf{𝐏}(i,i+1)={\left(\frac{k-i}{k}\right)}^2,\mathbf{𝐏}(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{ dla }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}$      (10.1)

gdzie ${\mathbf{𝐏}}^T$ oznacza macierz transponowaną (patrz wykład z Algebry liniowej z geometrią analityczną) 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)$      (10.2)

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

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

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

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

Dowód .

Dla $n=1$ (formuła 10.3) jest konsekwencją własności 2 w definicji definicji 10.1. Dla przeprowadzenia kroku indukcyjnego załóżmy, że wzór 10.3 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 10.2 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 10.3 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 10.8

Niech $i\in E$ będzie ustalonym stanem nieredukowalnego łańcucha Markowa. Wtedy:

1. stan $i$ jest powracający wtedy i tylko wtedy,gdy:

$\mathbf{𝐏}(i)=\mathrm{\infty }$,

2. 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 10.9

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{ oraz }\mathbf{𝐩}(j)=0\text{dla }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 7.15):

$\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)$

Przykład 10.10

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

${\mathbf{𝐏}}^n(i,i)={\mathbf{𝐏}}^n(0,0)\text{dla każdego }i\in \mathbb{\mathbb{Z}}$

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

${\mathbf{𝐏}}^n(0,0)=\{\begin{array}{rl}0,& \text{ gdy }n=2k-1\\ [2mm]\frac{(\genfrac{}{}{0ex}{}{2k}{k})}{2^{2k}},& \text{ gdy }n=2k.\end{array}$

Teraz:

$\mathbf{𝐏}(i)=\sum _{n=1}^{\mathrm{\infty }}{\mathbf{𝐏}}^n(i,i)=\sum _{n=1}^{\mathrm{\infty }}{\mathbf{𝐏}}^n(0,0)=\sum _{k=1}^{\mathrm{\infty }}\frac{(\genfrac{}{}{0ex}{}{2k}{k})}{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:

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

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:

1. wszystkie stany są okresowe i mają wspólny okres,

2. ż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 10.2 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 10.11

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:

1. łańcuch jest okresowy,

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

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

b) dla wszystkich $i,j\in E$:

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

c) 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 10.4 "sprawdzimy" to twierdzenie eksperymentalnie.