Rozważmy nieredukowalny łańcuch Markowa i ustalmy pewien jego stan \(i \in M\). Określamy:
\[ N_i = \{n: {\P }^n(i,i)> 0\}. \]
Ponieważ \(i\) komunikuje się z samym sobą, to \(N_i \neq \emptyset \).
Jeżeli \(m,n\in N_i\), to także \(m + n \in N_i\), gdyż \({\P }^{m+n}(i,i) \ge {\P }^m(i,i){\P }^n(i,i) >0.\)
Lemat – 17.7 Dla każdych stanów \(i, j \in M\) \(\nu _i = \nu _j\).
Dowód. Ponieważ łańcuch jest nieredukowalny, to istnieją takie liczby \(n, m\), że \(\P ^n(i,j) > 0\) oraz \(\P ^m(j,i) > 0\). W takim razie \(\P ^{n+m}(i,i) \ge \P ^n(i,j)\P ^m(j,i) > 0\), a więc \(n+m \in N_i\). Podobnie \(n+m \in N_j\). Niech \(t\in N_i\). Wtedy \(P^{n+t+m}(j,j) \ge \P ^n(i,j)\P ^t(i,i)\P ^m(j,i) >0\), a więc \(n+t+m \in N_j\). Więc \(\nu _j\) dzieli zarówno \(n+t+m\) jak i \(n+m\), czyli \(\nu _j\) dzieli \(t\). Ponieważ \(\nu _i\) jest największym wspólnym dzielnikiem \(N_i\), to \(\nu _j \ge \nu _i\). Podobnie dowodzimy, że \(\nu _i \ge \nu _j\).
Wykazaliśmy więc, że w nieredukowalnym łańcuchu Markowa: albo wszystkie stany są okresowe i mają wspólny okres, albo żaden ze stanów nie jest okresowy. W pierwszym z tych przypadków mówimy, że łańcuch Markowa jest okresowy, a jego okresem jest okres każdego jego stanu. W drugim przypadku mówimy, że łańcuch jest nieokresowy.
Standardowy spacer losowy po prostej jest okresowy a jego okres wynosi 2. Natomiast spacer losowy, dla którego \(p + q < 1\) i który nie posiada ekranów, nie jest okresowy. Nawet istnienie ekranów wraz z warunkiem \(p + q = 1\) nie gwarantuje okresowości.
Gdy \(k > 1\) urnowy model Bernoulliego, Przykład 16.7, jest nieokresowy.
Najpierw udowodnimy lemat.
Lemat – 17.9 \(n_1,...,n_r \in \N \), \(NWD(n_1,...,n_r) = 1 \imp \di \exists n_0 \ \forall n \ge n_0 \ \exists x_1,...,x_r \in \N \ n = \sum _{i=1}^rx_in_i\).
Dowód lematu. Miech \(f : \z ^r \ni x \to \sum _{i=1}^rx_in_i \in \z \). Istnieje więc takie \(x^0 \in \z ^r\), że \(f(x^0)\) jest najmniejszą wartością w zbiorze \(\{f(x): x \in \z ^r, f(x) \ge 1\}\). Zauważmy, że \(d = f(x^0)\) dzieli wszystkie liczby \(f(x)\) (piszemy \(d|f(x)\)). Mianowicie, dla ustalonego \(x\) mamy \(f(x) = kd + \vr \), \(0 \le \vr < d\), \(k \in \z \). Wtedy \(f(x - k x^0) = f(x) - kf(x^0) = \vr < f(x^0)\), więc zachodzi \(\vr = 0\). W szczególności \(d = f(x^0)\) dzieli wszystkie liczby \(n_1,...,n_r\), więc \(d = 1\).
Niech \(\mathbf {1} = (1,...,1)\) i niech \(n \ge 1\). Niech \(\vr \) będzie resztą z dzielenia \(n\) przez \(f(\mathbf {1})\). Stąd \(n = kf(\mathbf {1}) + \vr = kf(\mathbf {1}) + \vr f(x^0) = f(k \mathbf {1} + \vr x^0)\). Gdy \(n\) dąży do nieskończoności, także \(k\) dąży do nieskończoności, a dla dużych \(k\) wektor \(k \mathbf {1} + \vr x^0 \in \N ^r\). .
Dowód twierdzenia. (1) \(\imp \) (2). Ustalmy stany \(i, j \in M\). Ponieważ \(i\) nie jest okresowy istnieją takie liczby \(n_1,...,n_r \in N_i\), że \(NWD(n_1,...,n_r) = 1\). Z udowodnionego lematu i z własności zbioru \(N_i\) wnioskujemy, że wszystkie dostatecznie duże \(n \in N_i\), czyli dla takich \(n\) mamy \({\P }^n(i,i) > 0\). Niech \(k = k(i,j)\ge 1\) będzie takie, że \({\P }^k(i,j) > 0\). Wtedy \({\P }^{n+k}(i,j) \ge {\P }^n(i,i){\P }^k(i,j) > 0\) dla odpowiednio dużych \(n\), powiedzmy dla \(n \ge n(i,j)\). Ponieważ jednak zbiór stanów \(M\) jest skończony, to biorąc \(n_0 = \max \{n(i,j): i,j \in M\}\) mamy tezę.
(3) \(\imp \) (1). Oczywiste.
W pewnych okolicznościach możemy być zainteresowani w zachowaniu się łańcucha Markowa po upływie długiego czasu. W szczególności, warto się pytać o asymptotyczny rozkład wektorów \(X_n\). Poniższe twierdzenie opisuje właśnie taką sytuację w najprostszym szczególnym przypadku. Znane są jednak wyniki dużo ogólniejsze.
Twierdzenie – 17.10 (Twierdzenie ergodyczne) Rozważamy nieredukowalny łańcuch Markowa określony na skończonej przestrzeni stanów \(M\), \(\sharp M = k\). Jeżeli łańcuch jest nieokresowy, to istnieje wektor \(\pi \) o współrzędnych \(\pi _1\), …, \(\pi _k\) taki, że
1. \(\pi _i > 0\) dla wszystkich \(i \in M\),
2. Dla każdych \(i, j \in M\),
\[ \lim _{n \rightarrow \infty }{\P }^n(i,j) = \pi _j. \]
Wtedy też
3. Wektor \(\pi \) jest jedynym rozwiązaniem równania
\[ {\P }^T x = x \]
spełniającym warunek \(\sum _{i\in M}x_i = 1\).
Wektor ten nazywa się rozkładem stacjonarnym.
4. Dla każdego \(i \in M\) \(\di \lim _{n\to \infty } P(X_n=i) = \pi _i\).
Ergodyczność Jeżeli łańcuch jest nieokresowy, to dla dużych \(n\) prawdopodobieństwo przejścia ze stanu \(i\) do stanu \(j\) w \(n\) krokach jest dodatnie i faktycznie zależy od stanu końcowego \(j\) oraz nie zależy od stanu początkowego \(i\). Prawdopodobieństwa te można otrzymać, rozwiązując odpowiedni układ równań liniowych. Taka lub podobna własność nazywa się ergodycznością. Często wtedy mówimy, że łańcuch jest ergodyczny.
Dowód. Wykorzystamy wnioski z Twierdzenie Frobeniusa-Perrona1.
Zauważmy jednak najpierw, że macierz przejścia dowolnego łańcucha Markowa ma wartość własną \(\lambda _1 =1\), a wektorem własnym macierzy odpowiadającym \(\lambda _1\) jest \(\mathbf {1} = (1,...,1)^T\), co łatwo wynika z faktu, że \(\sum _{j \in M}\P (i,j) = 1\) dla każdego \(i \in M\) (ćwiczenie). Oczywiście \(\lambda _1\) jest także wartością własną macierzy \(\P ^T\), a więc istnieje taki niezerowy wektor \(\pi \), \(\P ^T\pi = \pi \).
Ponieważ łańcuch jest nieokresowy, więc na podstawie Twierdzenie 17.8 wiemy, że istnieje potęga \({\P }^n\) macierzy \(\P \) mająca wszystkie wyrazy dodatnie. Twierdzenie Frobeniusa-Perrona gwarantuje wtedy, że wszystkie pozostałe wartości własne macierzy \(\P \) są na moduł mniejsze niż 1 oraz, że wektor \(\pi \) ma wszystkie współrzędne dodatnie. Można założyć (dzieląc przez odpowiednią stałą), że \(\pi _1 + ... + \pi _k = 1\). Wiadomo także, że wtedy:
\[ \lim _{n\to \infty } \P ^n = \frac {\mathbf {1}\pi ^T}{\pi ^T \mathbf {1}} = \left [ \begin {array}{ccccc} \pi _1 & \pi _2 & \cdots & \cdots & \pi _k \\ \pi _1 & \pi _2 & \cdots & \cdots & \pi _k \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \pi _1 & \pi _2 & \cdots & \cdots & \pi _k \end {array} \right ], \]
co oznacza, że \(\di \lim _{n \rightarrow \infty }{\P }^n(i,j) = \pi _j\).
\(P(X_n = i) = \p _n(i) = \sum _{j=1}^k \P ^n(j,i)\p (j) \to \sum _{j=1}^k \pi _i\p (j) = \pi _i\) dla \(n \to \infty \).
Przykład – 17.11
Syzyf wtacza kamień na górę wysokości 4000 m. Pod koniec każdego dnia, z równymi prawdopodobieństwami: udało mu się pokonać kolejne 1000 m, lub kamień wysunął mu się z rąk i stoczył do stóp góry. Jednakże w chwili, gdy ma już dotrzeć do szczytu, złośliwy Zeus zawsze strąca mu kamień na dół. Oszacować prawdopodobieństwo, ze po 10 000 dniach pracy Syzyf będzie znajdował się dokładnie w połowie góry.
Pracę Syzyfa opisuje łańcuch Markowa \(X_n\) przyjmujący wartości w przestrzeni stanów \(M = \{0, 1, 2, 3\}\). Początkowy rozkład zmiennej \(X_0\), \(\p _0\), jest jednopunktowy = \(\delta _0\). Natomiast macierz przejścia ma postać:
\[ \P = \left [ \begin {array}{cccc} \frac {1}{2} & \frac {1}{2} & 0 & 0\\[1mm] \frac {1}{2} & 0 & \frac {1}{2} & 0\\[1mm] \frac {1}{2} & 0 & 0 & \frac {1}{2}\\[1mm] 1 & 0 & 0 & 0 \end {array} \right ]. \]
Jak widać, każde dwa stany się komunikują; z dowolnego stanu można z dodatnim prawdopodobieństwem przejść do każdego innego stanu. Widać też, że stan 0 nie jest okresowy (bo można w nim pozostać), więc łańcuch nie jest okresowy.
Zachodzi więc warunek 2 w Twierdzeniu Ergodycznym. Należy więc teraz rozwiązać układ równań liniowych: 5 równań o 4 niewiadomych.
\[ \P ^Tx = x, \ \ x_1+x_2+x_3+x_4 =1, \]
mamy pewność, że ma on rozwiązanie i to dokładnie jedno. Łatwo się przekonać, że jest nim układ:
\[ x_1 = \frac {8}{15}, \ x_2 = \frac {4}{15}, \ x_3 = \frac {2}{15}, x_4 = \frac {1}{15}. \]
To oznacza, że dla dużych \(t\), w szczególności dla \(t = 10\,000\), macierz \(\P ^t\) ma w przybliżeniu postać.
\[ \P ^t \cong \left [ \begin {array}{cccc} \frac {8}{15} & \frac {4}{15} & \frac {2}{15} & \frac {1}{15}\\[1mm] \frac {8}{15} & \frac {4}{15} & \frac {2}{15} & \frac {1}{15}\\[1mm] \frac {8}{15} & \frac {4}{15} & \frac {2}{15} & \frac {1}{15}\\[1mm] \frac {8}{15} & \frac {4}{15} & \frac {2}{15} & \frac {1}{15} \end {array} \right ]. \]
Tak więc odpowiedź na pytanie brzmi: \(\di P^{10000}(i,2) = \frac {2}{15}\).
Zgodnie z Twierdzeniem Frobeniusa-Perrona macierz przejścia ergodycznego łańcucha Markowa ma wartość własną równą 1, a pozostałe wartości własne mają moduły mniejsze od 1.
Na przykład, dla powyższej macierzy wynoszą one: \(1, -\frac 12, \frac {i}{2}, -\frac {i}{2}\).
Dla modelu urnowego Bernoulliego, Przykład 16.7:
k = 4: \(1, -\frac 18, \frac 12, \frac 18, -\frac 14\).
k= 10: \(1, 1/10, 1/5, 31/50, 23/50, -2/25, 1/50, -1/25, 4/5, -1/10, 8/25\).
Dla łańcucha (nie jest nieredukowalny) z przykładu 16.8:
\(-.149, .949, .901, -.101, -.0234, .823, .332, .468, .199, .601, .721, .0787, 1., 1.\)
Przykład – 17.12 (Kontynuacja przykładów 3.2 oraz 16.2.) Wyraźnie widać, że łańcuch określony w przykładzie 16.2 jest ergodyczny, a jego stan stacjonarny
\[\pi = \left [\begin {array}{c} 1/5 \\ 3/5 \\ 1/5 \end {array} \right ].\]
Tak więc po dłuższym okresie obowiązywania umowy Leon będzie sprzątał w danym dniu z prawdopodobieństwem bliskim \(\frac 35\). Ćwiczenie 3.1 wskazują, że okres ten wynosi około 10 dni.
Powracanie i ergodyczność Gdy spełnione są założenia twierdzenia ergodycznego to dla każdego \(i \in M\) mamy \(\P ^n(i,i) \approx \pi _i > 0\) dla dużych \(n\), więc \(\P (i) = \sum _{i=1}^\infty \P ^n(i,i) = \infty \), więc na podstawie twierdzenia 17.2 łańcuch jest powracający.
Oznacza to też, że zmienne losowe \(\tau _i\) określające liczbę powrotów do stanu \(i\) mają nieskończone wartości oczekiwane.
1 K. Wójcik, Stosowana algebra liniowa, UJ 2018/2019, wykłady 8 – 10