Wyznaczymy rozkłady zmiennych losowych \(X_n\) tworzących łańcuch Markowa.
\[ {\p }_n(j) = P(X_n = j) \]
dla wszystkich \(n \ge 1\) oraz \(j \in M\).
Stosując wzór na prawdopodobieństwo całkowite, mamy:
\[ {\p }_n(j) = P(X_n = j) = \sum _{i \in M}P(X_n = j|X_{n-1} = i)P(X_{n-1} = i) = \sum _{i \in M}{\P }(i,j){\p }_{n-1}(i). \]
Czyli
\[ {\p }_n = {\P }^T{\p }_{n-1}, \]
gdzie \({\P }^T\) oznacza transpozycje macierzy \(\P \).
Oznaczając \(n\)-tą potęgę macierzy \(\P \) przez \({\P }^n\), otrzymujemy wreszcie poszukiwany rozkład:
\[ {\p }_n = \left ({\P }^T\right )^n{\p }_0. \]
W szczególności, jeżeli wiemy, że \(X_0 = i\), czyli że łańcuch znajduje się w stanie \(i\) z prawdopodobieństwem 1, powyższy wzór implikuje:
\[ {\p }_n(j) = {\P }^n(i,j), \mbox { dla wszystkich } n, \]
co wyjaśnia znaczenie współczynników \({\P }^n(i,j)\) \(n\)-tej potęgi macierzy przejścia \(\P \).
Przykład – 16.8
Antoni i Bolesław, mają kapitał odpowiednio \(A\) i \(B\) złotych. Powtarzają oni tę samą grę (może 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\), a prawdopodobieństwo wygrania przez Bolesława \(q\). Zakładamy, że \(p+q \le 1\) i oznaczamy przez \(r\) prawdopodobieństwo remisu, \(r = 1 - p - q\). Oznaczmy kapitał Antoniego po zakończeniu \(n\)-tej gry przez \(X_n\).
Opisana sytuacja jest faktycznie spacerem losowym startującym w punkcie o współrzędnej \(A\) i mającym bariery pochłaniające w punktach o współrzędnych \(0\) oraz \(A+B\).
Zakładamy, że Antoni ma 8 złotych, a Bolesław 5 złotych. Bolesław gra na ogół lepiej niż Antoni: zakładamy: \(p=0.2\), \(q = 0.4\), \(r=0.4\). Grają 200 razy, chyba że jednemu z nich zabraknie wcześniej pieniędzy.
\(X_n\) – kapitał Antoniego po rozegraniu \(n\) gier.
\(X_0\) ma rozkład jednopunktowy \(\delta _8\),
\(X_1\) ma rozkład dany przez: [0, 0, 0, 0, 0, 0, 0, 0.4, 0.4, 0.2, 0, 0, 0, 0], \(E(X_1) = 7.8\).
\(X_5\) ma rozkład dany przez: [0, 0, 0, 0.102e-1, 0.512e-1, 0.128, 0.205, 0.230, 0.189, 0.115, 0.512e-1, 0.160e-1, 0.320e-2, 0.32e-3], \(E(X_3) = 7.000\)
\(X_{20}\) ma rozkład dany przez: [0.176, 0.620e-1, 0.954e-1, 0.113, 0.118, 0.112, 0.973e-1, 0.776e-1, 0.568e-1, 0.378e-1, 0.225e-1, 0.114e-1, 0.422e-2, 0.165e-1], \(E(X_{20}) = 4.1579\)
\(X_{200}\) ma rozkład dany przez: [0.969, 0.117e-4, 0.160e-4, 0.161e-4, 0.142e-4, 0.114e-4, 0.854e-5, 0.604e-5, 0.402e-5, 0.25e-5, 0.1430e-5, 0.7070-6, 0.2570e-6, 0.311e-1], \(E(X_{200}) = .4050783639\)
Niech \(A\) oznacza zbiór opisany przez zmienne losowe \(X_0, \dots X_{n-1}\), czyli \(A\) ma postać:
\[ A = \bigcup \{X_0 = i_0, \dots ,X_{n-1} = i_{n-1} \}, \]
gdzie suma jest brana po pewnym zbiorze, powiedzmy \(B\), indeksów \(i_0, \dots ,\) \(i_{n-1}\). Mamy wtedy:
Twierdzenie – 16.9
\[ P(X_{n+1} = j|(X_{n} = i \mbox { oraz } A)) = {\P }(i,j) \]
Dowód. Zauważmy najpierw, że:
\[ P(X_{n+1} = j|(X_{n} = i \mbox { 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 mamy:
\(\seteqnumber{0}{16.}{0}\)\begin{eqnarray*} 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) & = &\\ {\P }(i,j)P(X_{n} = i, X_{n-1} = i_{n-1}, \dots X_0 = i_0), & & \end{eqnarray*}
więc
\[ P(X_{n+1} = j|(X_{n} = i \mbox { oraz } A)) = {\P }(i,j). \]
\(\Box \)
Następne twierdzenie daje inną, bardziej ogólną, interpretację współczynników \({\P }^k(i,j)\) macierzy \({\P }^k\) jako prawdopodobieństw przejścia w \(k\) krokach ze stanu \(i\) do stanu \(j\).
Dowód. Dla \(k = 1\) formuła jest konsekwencją własności 2 w definicji łańcuchu Markowa.
Załóżmy dla przeprowadzenia kroku indukcyjnego, że zachodzi powyższy wzór dla pewnego \(k\). Wykażemy go dla \(k +1\). Mamy:
\[ P(X_{n+k+1} = j|X_n = i) = \frac {P(X_{n+k+1} = j,X_n = i)}{P(X_n = i)} \]
\[ = \frac {\sum _{l \in M}P(X_{n+k+1} = j,X_{n+k} = l,X_n = i)}{P(X_n = i)} \]
\[ = \frac {\sum _{l \in M}P(X_{n+k+1} = j|X_{n+k} = l,X_n = i) P(X_{n+k} = l,X_n = i)}{P(X_n = i)}. \]
Założenie indukcyjne oraz poprzednie Twierdzenie daje:
\[ P(X_{n+k+1} = j|X_n = i) \]
\[ = \frac {\sum _{l \in M}P(X_{n+k+1} = j|X_{n+k} = l) P(X_{n+k} = l|X_n = i)P(X_n = i)}{P(X_n = i)} \]
\[ =\sum _{l \in M}{\P }(l,j){\P }^k(i,l) = {\P }^{k+1}(i,j). \]
\(\Box \)
Tak więc \({\P }^k(i,j)\) jest prawdopodobieństwem przejścia w \(k\) krokach ze stanu \(i\) do stanu \(j\).
Warunek \({\P }^k(i,j) > 0\) oznacza, że takie przejście jest możliwe.
Zauważmy dalej, że dla każdych trzech stanów \(i, j, k\):
\[ {\P }^{m+n}(i,j) = \sum _{l\in M}{\P }^m(i,l){\P }^n(l,j) \ge {\P }^m(i,k){\P }^n(k,j). \]
Odpowiada to naszej intuicji, która podpowiada, że jeżeli jest możliwe przejście ze stanu \(i\) od stanu \(k\) oraz ze stanu \(k\) do stanu \(j\), to możliwe jest także przejście ze stanu \(i\) od \(j\).