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 znaczenie w wycenie instrumentów finansowych.
Niech \(M\subset \r ^d\) będzie zbiorem skończonym lub przeliczalnym i niech:
\({\P } : M \times M \to \r \), \({\p } :M \to \r \).
Będziemy myśleć o \(\P \) i \(\p \) jako o skończonej lub przeliczalnej macierzy o wyrazach \(\P (i,j)\) oraz wektorze (macierzy jedno kolumnowej) o współrzędnych \({\p }(i)\), gdzie \(i,j \in M\).
Definicja – 16.1 (Jednorodny łańcuch Markowa)
Niech \(\{X_n\}\), \(n = 0,1,2, \dots \), będzie ciągiem wektorów losowych określonych na przestrzeni probabilistycznej \((\Omega , \Sigma ,P)\) i przyjmujących wartości w \(\r ^d\).
Mówimy, że \(\{X_n\}\) jest jednorodnym łańcuchem Markowa, jeżeli spełnione są następujące warunki.
1. Dla każdego \(i \in M\), \(P(X_0 = i) = {\p }(i)\).
2. Dla każdego \(n \ge 0\) zachodzi
\(\seteqnumber{0}{16.}{0}\)\begin{eqnarray*} & 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) = {\P }(i_n,i_{n+1}), & \end{eqnarray*}
dla każdego ciągu \(\{i_0,\dots ,i_{n+1} \} \subset M\), o ile \(P(X_0 = i_0, \dots , X_n = i_n) > 0\).
3. \(\di \sum _{i \in M}{\p }(i) = 1\).
4. \(\di \sum _{ j \in M}{\P }(i,j) = 1\), dla każdego \(i \in M\).
Interpretacja.
1. \(M\) – zbiór wszystkich możliwych stanów pewnego systemu.
2. \(X_n\) – stan, w którym znajduje się system w chwili czasowej \(n\).
3. Warunek, że \(X_n\) jest zmienną losową, oznacza, że faktycznie nie znamy dokładnie tego położenia.
4. Znamy rozkład prawdopodobieństwa położenia systemu w chwili zerowej,
5. 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.
6. Układ nigdy nie opuści swojej przestrzeni stanów \(M\), gdyż \(\di P(X_0 \in M) = \sum _{i \in M}{\p }_i = 1, \) a wzór na prawdopodobieństwo całkowite oraz warunek 4 implikują:
\[ P(X_{n+1} \in M) = \sum _{j \in M}P(X_{n+1} = j) \]
\[ = \sum _{j \in M} \sum _{i \in M}P(X_{n+1}= j|X_n = i)P(X_n=i) = \]
\[ \sum _{i \in M} \sum _{j \in M}\P (i,j)P(X_n=i) = \sum _{i \in M} 1 P(X_n=i) = 1. \]
W związku z powyższą interpretacją będziemy nazywać;
\(M\) – zbiorem stanów, lub przestrzenią stanów,
\(\p \) – rozkładem początkowym,
\(\P \) – macierzą przejścia łańcucha Markowa.
Rozważa się też niejednorodne łańcuchy Markowa dopuszczając możliwość, że prawdopodobieństwo przejścia zależy od chwili w której to przejście następuje. W tym kursie nie zajmujemy się jednak takimi łańcuchami i w dalszym ciągu dla prostoty wypowiedzi opuszczamy słowo „ jednorodny".
Przykład – 16.2 (kontynuacja przykładu 3.2) Kaja i Leon umówili się w sprawie sprzątania, a ponieważ Kaja sprząta dokładniej niż Leon, ustalili następujące zasady. Jeżeli w pewnym dniu sprząta Leon, to rzuca kostką i jeżeli nie wyrzuci „6", to sprząta także w następnym dniu, gdy wypadnie „6śprząta Kaja. Jeżeli sprząta Kaja, to w następnym dniu nie sprząta nikt. Jeżeli w jakimś dniu nikt nie sprząta, to o sprzątaniu w następnym dniu decyduje rzut monetą. O sprzątaniu w pierwszym dniu umowy decyduje rzut monetą.
Modelem powyższej sytuacji może być łańcuch Markowa \(\{X_n\}\), \(n = 0,1,2, ...\), w którym \(X_n\) są zmiennymi losowymi o wartościach w \(M\), gdzie:
\[ M = \{Kaja,Leon,Nikt\}, \ \ \di \p ^T = \left [\frac 12,\frac 12,0\right ], \ \ \di \P =\left [\begin {array}{ccc} 0 & 0 & 1\\ \frac 16 & \frac 56 & 0 \\ \frac 12 & \frac 12 & 0 \end {array}\right ]\]
.
Dyskutowaliśmy już poprzednio spacery losowe po prostej, patrz sekcja 11.4. Jak się okazuje są one łańcuchami Markowa.
Przykład – 16.3 (Spacery losowe po prostej) 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, \dots \) 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 \(\di p = q = \frac {1}{2}\), mówimy, że spacer losowy jest standardowy.
Spacer losowy jest rzeczywiście łańcuchem Markowa. Mianowicie, stanami są wszystkie możliwe liczby całkowite, czyli \(M = \z \subset \r \).
\(X_n\) oznacza pozycję cząsteczki w chwili \(n\).
Zdefiniujmy:
\[ \begin {array}{llc} {\p }(i) = 1 & \mbox { dla } & i = 0, \\ {\p }(i) = 0 & \mbox { dla } & i \neq 0 \end {array} \]
oraz
\[ \begin {array}{lll} {\P }(i,j) = q & \mbox { dla } & j = i-1, \\ {\P }(i,j) = p & \mbox { dla } & j = i+1, \\ {\P }(i,j) = 0 & \mbox { w innych przypadkach. } & \end {array} \]
Mamy więc: \(P(X_0 = 0) = 1\), \(P(X_0 = i) = 0\) dla \(i\neq 0\),
\(P(X_{n+1} =i-1|X_n = i) = q\), \(P(X_{n+1} =i+1|X_n = i) = p\),
\(P(X_{n+1} = i|X_n = j) = 0\) dla \(|i-j| \neq 1\).
Określony powyżej spacer losowy może być modyfikowany na różne sposoby. Na przykład, załóżmy, że cząsteczka może nie zmieniać swojego położenia z prawdopodobieństwem \(r\). Oczywiście wtedy 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 i są usytuowane w punktach, powiedzmy, \(A < 0 < B\).
Wtedy zbiór \(M\) składa się \(A+B+1\) stanów, a \((A+B+1)\)-wymiarowa macierz \(\P \) może być zdefiniowana na przykład tak:
\[ {\P } = \left [ \begin {array}{cccccc} sa & 1 - sa & 0 & 0 & \cdots & 0 \\ q & r & p & 0 & \ddots & \vdots \\ 0 & \ddots & \ddots & \ddots & \ddots & 0\\ 0 & \ddots & \ddots & \ddots & \ddots & 0\\ \vdots & \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 są jedynkami, co oznacza pełną absorbcję cząsteczki z chwilą jej dojścia do bariery.
Przykład – 16.4 Animacja pokazuje pierwszych 500 kroków wędrówki cząstki startującej z punktu 0, gdy bariery ustawione są w punktach \(A = -5\), \(B=5\), a prawdopodobieństwa wynoszą: \(p = 0.2\), \(q = 0.25\), \(r = 0.55\), \(sa = 0.1\), \(sb = 0.7\).
Można też opisać spacer losowy, używając innego podejścia.
Załóżmy, nieco ogólniej niż poprzednio, że cząsteczka startuje w chwili zero z punktu \(i\). Gdy nie uwzględniamy barier, mamy:
\[ X_0 = i, \ \mbox { oraz } \ \ X_{n} = X_{n-1} + \xi _{n}, \mbox { dla } n = 1,2,3, \dots , \]
gdzie \(\xi _1\), \(\xi _2\), \(\xi _3\), …są niezależnymi zmiennymi losowymi przyjmującymi wartości \(-1\), \(0\), \(1\) z prawdopodobieństwami odpowiednio \(q, \ r, \ p\).
Można także rozpatrywać spacery losowe na płaszczyźnie i ogólnie w przestrzeni wielowymiarowej.
Przykład – 16.5 Dla uproszczenia załóżmy, że \(p = q = \frac {1}{2}\), czyli także \(r = 0\). Dla \(i \in Z^d\) mamy:
\[ X_0 = i, \ \mbox { oraz } \ \ X_{n} = X_{n-1} + \xi _{n}, \mbox { dla } n = 1,2,3, \dots \]
Tym razem \(\xi _1\), \(\xi _2\), \(\xi _3\), …są niezależnymi wektorami losowymi przyjmującymi \(2^d\) wartości \((\ve _1, \dots , \ve _d)\), gdzie \(\ve _j = _{+}^{-} 1\), z jednakowym prawdopodobieństwem \(\di \frac {1}{2^d}\).
Zauważmy, że współrzędnymi \(d\)-wymiarowego spaceru losowego są niezależne jednowymiarowe standardowe spacery losowe.
Prezentowany powyżej mechanizm tworzenia łańcucha Markowa można istotnie uogólnić.
Twierdzenie – 16.6 Niech \(M \subset \r ^d\) będzie zbiorem skończonym lub przeliczalnym, \(B \subset \r ^k\) zbiorem borelowskim Załóżmy, że \(T:M\times B \to M\) jest odwzorowaniem spełniającym warunek mierzalności:
\[ \forall \ i, j \in M \ \ \{y \in \r ^k : T(i,y) = j \} \in {\cal B}(\r ^k). \]
Niech \(\eta ,\xi _1,\xi _2,\xi _3 \dots \) będzie ciągiem niezależnych wektorów losowych, przy czym \(\eta \) ma wartości w \(M\), a \(k\)-wymiarowe wektory \(\xi _1,\xi _2,\xi _3, \dots \) mają identyczny rozkład na zbiorze \(B\). Definiujemy:
\[ X_0 = \eta , \ \ \ \ X_{n} = T(X_{n-1},\xi _{n}), \mbox { dla } n \ge 1. \]
Dowód. Niech \(\p (i) = P(\eta = i)\) oraz \(\P (i,j) = P(T(i, \xi _n) = j )\) dla \(i, j \in M\). Wtedy:
\(\seteqnumber{0}{16.}{0}\)\begin{eqnarray*} & & P(X_{n+1} = i_{n+1}|(X_0 = i_0, \dots , X_n = i_n)) = \frac {P(X_{n+1} = i_{n+1},X_0 = i_0, \dots , X_n = i_n)}{P(X_0 = i_0, \dots , X_n = i_n)}\\ & = & \frac {P(T(i_n,\xi _{n+1}) = i_{n+1},X_0 = i_0, \dots , X_n = i_n)}{P(X_0 = i_0, \dots , X_n = i_n)} \\ & = & \frac {P(T(i_n,\xi _{n+1}) = i_{n+1}) P(X_0 = i_0, \dots , X_n = i_n)}{P(X_0 = i_0, \dots , X_n = i_n)} = P(T(i_n,\xi _{n+1}) = i_{n+1}) =\P (i_n,i_{n+1}). \end{eqnarray*}
Podobnie \(\di P(X_{n+1} = i_{n+1}|X_n = i_n) = \frac {P(T(i_n,\xi _{n+1}) = i_{n+1}) P(X_n = i_n)}{P(X_n = i_n)}\) \(= \di P(T(i_n,\xi _{n+1}) = i_{n+1}) =\P (i_n,i_{n+1})\).
Przykład – 16.7 (Urnowy model Bernoulliego)
W każdej z dwóch urn umieszczono \(k\) kul, przy czym \(k\) z nich ma kolor biały, a \(k\) ma kolor czerwony. Następnie w kolejnych momentach losujemy jednocześnie po jednej kuli z każdej urny i przekładamy je do drugiej urny. Niech \(X_n\) oznacza liczbę białych 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 na przestrzeni stanów \(M = \{0,1,2,...,k\}\) z macierzą przejścia \(\P \) mającej zerowe wyrazy oprócz
\[ {\P }(i,i-1)= \left (\frac {i}{k}\right )^2, \ \ \ \‚{\P }(i,i+1) = \left (\frac {k - i}{k}\right )^2, \ \ \ \‚{\P }(i,i) = \frac {2(k-i)i}{k^2}. \]
dla \(0< i < k\) oraz \(\P (0,1) = 1\), \(\P (k,k - 1) = 1\).
Jeżeli na początku eksperymentu w pierwszej urnie było \(b_0\) białych kul, to \(\p (b_0) = 1\) oraz \(\p (i) = 0\) dla \(i \neq b_0\).
\[ \P = \left [ \begin {array}{ccccc} 0&1&0&0&0\\ 1/16&3/8&{{9}/{16}}&0&0 \\ 0&1/4&1/2&1/4&0 \\ 0&0&{{9}/{16}}&3/8&1/16 \\ 0&0&0&1&0\end {array} \right ] , \ \ k = 4. \]
Alternatywnie powyższy łańcuch można opisać tak:
\[ X_0 = b_0, \ \ \ X_{n} = T(X_{n-1},\xi _n), n = 1,2,3, ... . \]
\(\xi _n\) są niezależnymi wektorami losowymi mającymi rozkład jednostajny na zbirze \(\{1,...,k\}^2\), \(T : M \times \{1,...,k\}^2 \to M\) jest określone jako:
\[ T(x,y) = \left \{\begin {array}{ccc} x - 1, & \mbox { gdy } & y_1 \le x , y_2 > k -x \\ x, & \mbox { gdy } & y_1 \le x, y_2 \le k - x \vee y_1 > x, y_2 > k -x\\ x+1, & \mbox { gdy } & y_1 > x, y_2 \le k - x. \end {array} \right . \]
Faktycznie, przed każdym losowaniem można (można hipotetycznie) ponumerować kule w urnach w taki sposób, że białe kule w obydwóch urnach mają początkowe numery: od 1 do \(x\) w pierwszej urnie, a więc od 1 do \(k-x\) w drugiej urnie, natomiast czarne kule mają pozostałe numery: od \(x+1\) do \(k\) w pierwszej oraz od \(k - x +1\) do \(k\) w drugiej urnie.