Definicja – 17.1 Łańcuch Markowa jest nieredukowalny \(\rwn \) 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)\).
Większość łańcuchów Markowa spotykanych w zastosowaniach jest nieredukowalna, jakkolwiek łatwo pokazać przykłady łańcuchów, które nie spełniają tej własności.
Spacer losowy z ekranami pochłaniającymi nie jest nieredukowalny, gdyż prawdopodobieństwo przejścia z jednego do drugiego ekranu jest równe zeru.
Dla nieredukowalnego łańcucha Markowa oznaczmy prawdopodobieństwo pierwszego powrotu do stanu \(i\) dokładnie w \(n\) krokach przez \(f_n(i)\), czyli
\[ f_n(i) = P(X_n = i,X_{n-1} \neq i, \dots , X_1 \neq i|X_0 = i). \]
Określmy \(F(i)\) jako \(\di F(i) = \sum _{n=1}^\infty f_n(i). \) Jest to więc prawdopodobieństwo pierwszego powrotu do stanu \(i\) w czasie skończonym.
Jako prawdopodobieństwo, \(F(i)\) jest nie większe niż \(1\). Będziemy mówić, że stan \(i\) jest powracający, jeżeli \(F(i) = 1\) i niepowracający, jeżeli \(F(i) < 1\).
Następujące twierdzenie jest prostym uogólnieniem twierdzenia 11.25. Pozwala ono w wielu przypadkach stwierdzić, czy stan łańcucha Markowa jest powracający, czy niepowracający. Oznaczmy:
\[ \P (i) = \sum _{n = 1}^\infty {\P }^n(i,i). \]
Dowód. Dowód polega na powtórzenia rozumowania zastosowanego w uzasadnieniu twierdzenia 11.25, które dotyczyło szczególnego łańcucha Markowa. Zauważmy, że zdefiniowane tam prawdopodobieństwa \(a_n\) oraz \(f_n\) są szczególnymi przypadkami \(\P ^n(i,i)\) oraz \(f_n(i)\). Szczegóły pozostawiamy Czytelnikowi (ćwiczenie).
Wykażemy, że albo wszystkie stany są powracające, albo wszystkie stany są niepowracające. W związku z tym mówimy, że łańcuch Markowa (nieredukowalny) jest odpowiednio powracający albo niepowracający.
Lemat – 17.3 Niech \(i, j \in M\) będą stanami nieredukowalnego łańcucha Markowa. Wtedy:
\[\sum _{n = 1}^\infty {\P }^n(i,i) < \infty \ \ \rwn \ \ \sum _{n = 1}^\infty {\P }^n(j,j) < \infty . \]
Dowód. Istnieją takie liczby \(s, t\), że \(\P ^s(i,j) > 0\) oraz \(\P ^t(j,i) > 0\). Oznaczmy te dwie ostatnie wielkości odpowiednio przez \(c\) oraz \(d\). Wybierzmy dowolną liczbę naturalną \(n\). Wtedy
\[ \P ^{n+t+s}(i,i) \ge \P ^s(i,j)\P ^n(j,j)\P ^t(j,i) = cd \P ^n(j,j). \]
Jeżeli szereg \(\sum _{n = 1}^\infty {\P }^n(i,i)\) jest zbieżny, to oczywiście \(\sum _{n = 1}^\infty {\P }^{n+t+s}(i,i)\) jest zbieżny i stosując kryterium porównawcze zbieżności szeregów widzimy, że \(\sum _{n = 1}^\infty {\P }^n(j,j)\) też jest zbieżny. Rozumowanie symetryczne kończy dowód.
Liczby \(\P (i)\) mają także nieco inną interpretację. Oznaczmy przez \(r_i\) liczbę wszystkich powrotów do stanu \(i\).
Twierdzenie – 17.4 Dla każdego \(i \in M\), \(\di E\left (r_i\right ) = \P (i)\).
Dowód. Załóżmy, że w chwili \(0\) system znajdował się w stanie \(i\). W takim razie \({\p }(i) = 1\) oraz \({\p }(j) = 0\) dla \(j \neq i\). Mamy więc
\[ P(X_n = i) = P(X_n = i|X_0 = i) = {\P }^n(i,i). \]
Wiemy, że wartość oczekiwana funkcji charakterystycznej \(I_{\{X_n = i\}}\) wynosi \({\P }^n(i,i)\). Mamy też: \(\di r_i = \sum _{n=1}^\infty I_{\{X_n = i\}}\), co właśnie oznacza tezę. \(\Box \)
Stosując twierdzenie 11.25 wykazaliśmy, że standardowy spacer losowy po prostej jest łańcuchem powracającym. Co więcej, okazało się w istocie, że dla dowolnego stanu \(i \in \Z \): \(\P ^n(i,i) = 0\) dla nieparzystych \(n\) oraz \(\P ^{2k}(i,i) = a_{2k} \cong \frac {1}{\sqrt {\pi k}}\) dla dużych \(k\).
Przykład – 17.5 Rozważmy spacer losowy \(d\)-wymiarowy opisany w przykładzie 16.5, \(d \ge 2\).
Niech \({\P }_d\) oznacza macierz przejścia naszego łańcucha Markowa. Ustalmy stan \(i = (i_1, \dots , i_d) \in \z ^d\). Bez straty ogólności można założyć, że \(i = (0, ..., 0)\). Widzimy teraz, że przejście w \(n\) krokach ze stanu \(i\) z powrotem do tego stanu podczas \(d\)-wymiarowego spaceru losowego jest równoważne przejściom ze stanów \(i_j\) do \(i_j\) w \(n\) krokach podczas jednowymiarowych spacerów losowych niezależnych od siebie. Właśnie korzystając z tej niezależności, mamy:
\[ {\P }_d^n(i,i) = {\P }^n(i_1,i_1)\cdot \dots \cdot {\P }^n(i_d,i_d) = \left ({\P }^n(0,0)\right )^d. \]
Mamy więc, że \({\P }_2^n(i,i) = \P ^n(0,0)^2 \cong \left (\frac {1}{\sqrt {\pi k}} \right )^2 = \frac {1}{\pi k}\), gdy \(n = 2k\), \({\P }_2^n(i,i) = 0\), gdy \(n = 2k-1\). Tak więc szereg \(\sum _{n=1}^\infty {\P }_2^n(i,i) = \infty \), a więc również dwuwymiarowy spacer losowy jest powracający.
Zauważmy, że dla \(d \ge 3\) \({\P }_d^n(i,i) = \P ^n(0,0)^d \cong \left (\frac {1}{\sqrt {\pi k}} \right )^d = \frac {1}{\sqrt {\pi ^d} k^{\frac {d}{2}} } \), dla \(= 2k\). więc szereg \(\sum _{n=1}^\infty {\P }_d^n(i,i) < \infty \) i dlatego łańcuch nie jest powracający.
Wiedząc, że jest on zbieżny możemy obliczyć przybliżoną wartość sumy dla \(d = 3,4,5,6\). Wielkości te wynoszą: \(0.35742\), \(0.11763\), \(0.046788\), \(0.020459\).
Możemy więc obliczać prawdopodobieństwa powrotu \(F(i)\). Wynoszą one odpowiednio: \(0.263308\), \(0.10524\), \(0.044696\), \(0.0200488\).