Zajmiemy się teraz opisem ciągu zależnych doświadczeń losowych. Niech D oznacza pewne doświadczenie, którego zbiór możliwych wyników W1, W2,…,Wn, n∈N, znamy. W trakcie powtarzania tego doświadczenia w próbie z numerem t∈N dostajemy wynik o numerze Xt∈1,2,…,n, przy czym prawdopodobieństwa różnych wartości WXt w ogólnym przypadku mogą zależeć od wyników wszystkich poprzednich doświadczeń. Taki obiekt nazwiemy skończonym procesem stochastycznym. Z kolei łańcuch Markowa to pewien szczególny rodzaj procesu stochastycznego, w którym wynik kolejnej próby zależy tylko od wyniku próby poprzedniej.

Podamy teraz kilka prostych przykładów:

— Rzut monetą to jeden z najprostszych możliwych procesów stochastycznych. Mamy dwa możliwe wyniki każdej próby orzeł O i reszka R, przy czym zawsze prawdopodobieństwo otrzymania każdego z tych dwóch wyników wynosi 1/2, niezależnie od tego, jakie wyniki otrzymywaliśmy w przeszłości. Wobec tego rzut monetą jest przykładem jednorodnego łańcucha Markowa.

— Rosyjska ruletka I to wersja gry, w której używa się sześciostrzałowego rewolweru z jedną kulą. Po zakręceniu bębenkiem oddaje się strzał i w pierwszej próbie wynik z prawdopodobieństwem 1/6 jest martwy M, a z prawdopodobieństwem 5/6 — żywy Z. Wynik kolejnej próby zależy od poprzedniego. Jeśli osoba, do której się strzela, została zastrzelona w poprzedniej próbie, to oczywiście w każdej następnej jest martwa z prawdopodobieństwem 1, natomiast jeśli jest żywa, to w drugiej próbie będzie martwa z prawdopodobieństwem 4/5, w trzeciej z prawdopodobieństwem 3/4, następnie 2/3, 1/2 i ostatecznie w szóstej próbie wynik jest zawsze M z prawdopodobieństwem 1. Widzimy więc, że taka wersja rosyjskiej ruletki stanowi łańcuch Markowa, ale nie jest to łańcuch jednorodny.

— Rosyjska ruletka II to inna wersja, w której za każdym razem używa się sześciostrzałowego rewolweru z jedną kulą, ale przed każdą próbą ponownie kręci się bębenkiem. Zatem przy każdej próbie otrzymywane wyniki są jednakowe: M z prawdopodobieństwem 1/6 oraz Z z prawdopodobieństwem 5/6. Mamy więc jednorodny łańcuch Markowa.

W dalszej części wykładu zajmiemy się tylko łańcuchami jednorodnymi, wobec tego nie będziemy już powtarzać określenia ,,jednorodny łańcuch Markowa”, tylko pisząc ,,łańcuch Markowa” będziemy mieli na myśli łańcuch jednorodny. Taki łańcuch Markowa możemy w jednoznaczny sposób zdefiniować podając jego stany, czyli możliwe wyniki kolejnych eksperymentów, oraz macierz przejścia P=pi⁢ji,j=1n, czyli prawdopodobieństwa pi⁢j przejścia ze stanu Wi w próbie t-1 do stanu Wj w kolejnej próbie t. Macierz przejścia ma oczywiście następujące własności:

ponieważ dla dowolnych i,j∈1,…,n liczba pi⁢j jest prawdopodobieństwem, a jeśli łańcuch znajduje się w pewnym stanie Wi w chwili t-1, to musi przejść do jakiegoś stanu Wj w chwili t. Macierze o tych własnościach nazywamy macierzami stochastycznymi. Pełny opis łańcucha Markowa możemy także przedstawić za pomocą grafu skierowanego ważonego.

W przypadku grafu ważonego każdej istniejącej krawędzi prowadzącej od wierzchołka i do j przypisujemy pewną wagę wi⁢j. Graf opisujący łańcuch Markowa budujemy w następujący sposób

• wierzchołek z numerem i, i∈1,…,n odpowiada wynikowi Wi;

• od wierzchołka z numerem i do wierzchołka z numerem j przeprowadzamy krawędź i,j, o ile pi⁢j>0, a jeśli pi⁢j=0, to takiej krawędzi nie ma;

• zbudowanej krawędzi i,j nadajemy wagę wi⁢j=pi⁢j.

Zaprezentujemy teraz macierze przejścia i grafy przejścia, por. rys. 9.1, odpowiadające wymienionym w przykładach łańcuchom: rzutowi monetą i rosyjskiej ruletce w wersji II.

Macierz przejścia P odzwierciedla dynamikę łańcucha w jednym kroku, natomiast my jak zwykle chcemy zbadać, co będzie się działo asymptotycznie, czyli czego możemy się spodziewać, jeśli będziemy nasze doświadczenia powtarzać dostatecznie długo. Do tego celu musimy obliczyć prawdopodobieństwa przejścia wyższego rzędu, czyli pi⁢jt, które opisuje przejście ze stanu Wi do stanu Wj w t krokach, czyli po wykonaniu t prób. Mamy więc pi⁢jt=P(Xt=j|X0=i). Zgodnie ze wzorem na prawdopodobieństwo całkowite dla t>1 otrzymujemy

czyli rekurencyjną zależność pi⁢jt od prawdopodobieństw niższego rzędu pi⁢st-1. Stąd jeśli Pt=pi⁢jti,j=1n jest macierzą przejścia wyższego rzędu, to dostajemy zależność

Wnioskujemy zatem, że rozkład łańcucha w dowolnym kroku jest jednoznacznie wyznaczony przez macierz przejścia i początkowy rozkład prawdopodobieństwa pi0=PX0=i, i=1,…,n.

W kontekście opisywanych powyżej doświadczeń genetycznych chcemy poznać asymptotykę dwóch konkretnych typów łańcuchów Markowa. Zanim jednak przejdziemy do badania asymptotyki, podamy potrzebne definicje, w tym klasyfikację stanów łańcucha.

Zaczniemy od podziału stanów łańcucha na pewne specjalne grupy.

Podzielmy teraz wszystkie stany danego łańcucha na podklasy: niech S0 oznacza klasę wszystkich stanów nieistotnych, następnie wybierzmy jakikolwiek stan istotny Wi i oznaczmy przez Si zbiór wszystkich stanów komunikujących się z Wi. Ten zbiór stanów nazywa się także czasem zbiorem stochastycznie zamkniętym. W taki sposób podzielimy łańcuch na rozłączne klasy stanów komunikujących się S1,…,SN, N≤n. Jeśli łańcuch znalazł się w pewnym momencie w stanie istotnym Wi, to już nigdy nie wyjdzie z odpowiadającej mu klasy.

Badając łańcuch Markowa sprowadzamy najpierw jego macierz do postaci kanonicznej numerując stany w taki sposób, aby na początku znalazły się stany nieistotne, a następnie poszczególne stany z kolejnych klas. Macierz ma wtedy postać

a powstałe macierze ⋮⋮⋮⋮ są macierzami stochastycznymi i każda z nich odpowiada łańcuchowi nieprzywiedlnemu.

Oznaczmy

gdzie fjt oznacza prawdopodobieństwo, że układ po wyjściu ze stanu Wj wróci do tego stanu po raz pierwszy po t krokach, a Fj to prawdopodobieństwo, że po wyjściu z tego stanu wróci do niego kiedykolwiek.

– Stan Wj nazywamy powracającym, jeśli Fj=1, natomiast niepowracającym, gdy Fj<1.

– Stan Wj nazywamy zerowym, jeśli pj⁢jt→0 przy t→∞.

– Stan Wj nazywamy okresowym o okresie dj, jeśli powrót z dodatnim prawdopodobieństwem możliwy jest w liczbie kroków równej wielokrotności dj i dj jest najmniejszą liczbą o tej własności (czyli dj jest NWD zbioru t:⁢pj⁢jt>0).

– Stan powracający, niezerowy i nieokresowy nazywamy ergodycznym.

Wymienimy teraz dwa typy łańcuchów, które są istotne z punktu widzenia doświadczeń genetycznych, jakie za ich pomocą chcemy opisywać.

Drugi typ stanowią oczywiście łańcuchy nieprzywiedlne. Każdy typ łańcucha przywiedlnego możemy analizować korzystając z własności łańcuchów pochłaniających i łańcuchów nieprzywiedlnych. Dopóki łańcuch nie trafi do któregoś ze zbiorów Si, i>0, możemy traktować łańcuch jak łańcuch pochłaniający, natomiast jak już trafi do zbioru Si, i>0, to ten zbiór tworzy łańcuch nieprzywiedlny.

Wróćmy teraz do naszych prostych przykładów i spróbujmy w ich kontekście zastosować poznane definicje.

• Rzut monetą: zauważmy, że prawdopodobieństwa przejścia z każdego z dwóch stanów łańcucha O, R do każdego z nich jest zawsze równe 1/2, bez względu na stan w kroku poprzednim, zatem Pt=P, czyli oba stany są istotne i komunikujące się, tworzą więc łańcuch nieprzywiedlny.

• Rosyjska ruletka II: stan M jest oczywiście pochłaniający, natomiast stan Z tworzy zbiór S0 i jest stanem nieistotnym, ponieważ p21=1/6, natomiast p12t=0 dla dowolnego t∈N, gdyż M=W1 jest pochłaniający, czyli łańcuch ma własności wymienione w def. 9.7, zatem stanowi łańcuch pochłaniający.

Zauważmy, że asymptotycznie te dwa typy łańcuchów (czyli nieprzywiedlny i pochłaniający) mają diametralnie różne własności. W łańcuchu nieprzywiedlnym każdy stan jest osiągany z dodatnim prawdopodobieństwem w dowolnej próbie, natomiast w łańcuchu pochłaniającym w pewnej próbie łańcuch wynosi trafia do jakiegoś stanu pochłaniającego, z którego już nie wychodzi. W przypadku rzutu monetą, ponieważ dla dowolnego t∈N∖0 zachodzi Prmt=Prm, więc bez względu na liczbę prób zawsze średnio dostajemy połowę orłów i połowę reszek. Z kolei w przypadku rosyjskiej ruletki prawdopodobieństwo pozostania żywym maleje do 0 wraz z rosnącą liczbą prób, co łatwo możemy bezpośrednio obliczyć iterując macierz przejścia

Co ciekawe, oczekiwane liczba kroków przed absorpcją wynosi 6, czyli tyle, ile maksymalna liczba kroków możliwa w wersji I. Wykażemy to poniżej.