10.1. Łańcuchy pochłaniające i ciągłe krzyżowanie z dominantą
Dla łańcuchów pochłaniających postać kanoniczna macierzy przejścia przedstawia się następująco
gdzie I oznacza macierz jednostkową wymiaru m×m reprezentującą m stanów pochłaniających, R jest macierzą wymiaru n-m×m przejścia ze stanów nieistotnych do stanów pochłaniających, a Q — macierzą n-m×n-m przejścia ze stanów nieistotnych do stanów nieistotnych. Zauważmy, że dla takich łańcuchów wygodniej jest zdefiniować postać kanoniczną inaczej niż poprzednio — zaczynamy numerowanie od stanów pochłaniających, dopiero później bierzemy pod uwagę stany nieistotne.
Z własności stanów nieistotnych i stanów pochłaniających wynika, że
-
Qt→0 dla t→∞ (zbieżność po wyrazach);
-
macierz I-Q jest odwracalna;
-
Własność 1. wynika z ogólnego twierdzenia dotyczącego łańcuchów Markowa, które orzeka, że niezależnie od stanu początkowego prawdopodobieństwo trafienia do stanu komunikującego się po t krokach dąży do 1 przy t→∞, a ponieważ Q odpowiada stanom nieistotnym, zatem każde z pozostałych prawdopodobieństw dąży do 0. Dalej zauważmy, że
Skoro Qt→0, to I-Qt→I, a z ciągłości wyznacznika wynika, że dla dostatecznie dużych t zachodzi detI-Qt≠0, czyli także detI-Q≠0, więc
macierz I-Q jest odwracalna. Stąd
i przechodząc do granicy t→∞ dostajemy wzór 3.
W przypadku łańcuchów pochłaniających interesują nas głównie następujące zagadnienia dotyczące łańcucha, dla którego stanem początkowym jest pewien nieistotny stan Wi.
[I]
-
Jaka jest oczekiwana liczba przejść przez stan Wj, zakładając że stanem początkowym jest Wi?
-
Jaka jest oczekiwana liczba kroków przed absorpcją, jeśli stanem początkowym jest Wi?
-
Jakie jest prawdopodobieństwo absorpcji przez dany stan pochłaniający Wj, jeśli stanem początkowym jest Wi?
Dla macierzy przejścia w postaci kanonicznej definiujemy następującą macierz fundamentalną
łańcucha pochłaniającego. Macierz ta zawiera wszystkie istotne informacje dotyczące zachowań asymptotycznych. W szczególności
Twierdzenie 10.1
Niech N będzie macierzą fundamentalną łańcucha pochłaniającego.
-
Oczekiwana liczba przejść przez stan Wj przy stanie początkowym Wi jest równa ηij.
-
Oczekiwana liczba kroków przed absorpcją dla łańcucha o stanie początkowym Wi zadana jest jako suma wyrazów w i. wierszu macierzy N.
-
Niech B=bij będzie n-m×m macierzą prawdopodobieństw absorpcji przez stan Wj przy stanie początkowym Wi. Wtedy B=NR.
Niech eij oznacza oczekiwaną liczba przejść przez stan Wj przy stanie początkowym Wi. Wprowadźmy zmienną losową
Niech Eix oznacza wartość średnią x przy warunku, że proces zaczął się w stanie Wi. Wtedy
|
eij=Ei∑s=0∞ζjs=∑s=0∞Eiζjs=∑s=0∞1-pijs⋅0+pijs⋅1, |
|
czyli ostatecznie eij=∑s=0∞pijs. Skoro pijs jest i,j. wyrazem macierzy Qs, to eij jest i,j. wyrazem macierzy N, czyli ηij.
Bezpośrednio z tego wzoru otrzymujemy także, że średni czas do absorpcji jest sumą wyrazów w wierszu i.
Wyprowadzimy teraz wzór rekurencyjny na prawdopodobieństwo bij. Niech Wi będzie stanem początkowym nieistotnym. W pierwszym kroku łańcuch może przejść do interesującego nas stanu pochłaniającego Wj, do innego stanu pochłaniającego Wk, k≠j, albo do któregoś ze stanów nieistotnych Wl z prawdopodobieństwami zadanymi przez macierz P. Prawdopodobieństwa absorpcji przez stan Wj ze stanu Wj, Wk oraz Wl są odpowiednio równe
1, 0 oraz blj. Stąd
|
bij=pij+∑l=m+1npilblj. |
|
Skoro Wi oraz Wj są odpowiednio stanem nieistotnym i pochłaniającym, więc pij jest i,j. wyrazem macierzy R i analogicznie pil jest i,l. wyrazem macierzy Q. Zatem
|
B=R+QB⟹B=I-Q-1R=NR. |
|
∎
Zastosujemy teraz powyższe twierdzenie do opisu asymptotyki rosyjskiej ruletki oraz do opisu doświadczenia polegającego na ciągłym krzyżowaniu z dominantą.
W przypadku rosyjskiej ruletki mamy jeden stan pochłaniający M i jeden stan nieistotny Z. Odpowiednie podmacierze macierzy P są jednoelementowe
|
Q=5/6,R=1/6,N=1-5/6-1=6,B=NR=1. |
|
Ponieważ jest tylko jeden stan pochłaniający, więc oczywiście prawdopodobieństwo znalezienia się w tym stanie po dostatecznie długim czasie wynosi 1, natomiast
oczekiwana liczba kroków do absorpcji równa się 6.
Ciągłe krzyżowanie z dominantą
Rozpatrzmy teraz następujący ciąg doświadczeń tworzący
łańcuch Markowa. Bierzemy ustalonego osobnika o genotypie dominującym DD i krzyżujemy go z nieznanym osobnikiem. W wyniku eksperymentu dostajemy potomka o genotypie zależnym od genotypu drugiego rodzica z prawdopodobieństwami wynikającymi z prawa Mendla. Mamy zatem 3 możliwe wyniki eksperymentu, ponieważ są 3 genotypy. Ponumerujmy je w następujący sposób:
Odpowiednie prawdopodobieństwa wynoszą
-
p11=1, gdyż zawsze ze skrzyżowania dominanty z dominantą otrzymujemy ten sam genotyp. Stąd p1j=0 dla j=1,2 i stan W1 jest pochłaniający.
-
p21=1/2=p22 oraz p23=0, gdyż krzyżując dominantę z hybrydą otrzymujemy z prawdopodobieństwem 1/2 albo dominantę, albo hybrydę, nie możemy natomiast dostać osobnika recesywnego;
-
p31=0=p33, p32=1, ponieważ krzyżując osobnika recesywnego z dominantą zawsze dostajemy hybrydę.
Dla tego łańcucha Markowa macierz przejścia ma postać
dla której
Policzmy macierz fundamentalną
|
N=I-Q-1=0,50-11-1=21010,5. |
|
Na jej podstawie wnioskujemy, że jeśli wybranym rodzicem była hybryda, to średni czas do absorpcji wynosi 2, natomiast jeśli osobnik recesywny, to 2+1=3. Możemy jeszcze sprawdzić punkt 3. twierdzenia wykonując mnożenie
co oczywiście potwierdza, że z prawdopodobieństwem 1 nasz eksperyment kończy się osobnikami o genotypie DD.
Zauważmy jeszcze, że dokładnie w taki sam sposób możemy opisać ciągłe krzyżowanie z osobnikiem recesywnym. Wtedy macierz przejścia ma postać
gdzie tym razem W1=RR, W2=DR oraz W3=DD, zatem odpowiednio numerując stany dostajemy dokładnie taką samą dynamikę łańcucha pochłaniającego jak w przypadku krzyżowania z dominantą.
10.2. Łańcuchy regularne i ciągłe krzyżowanie z hybrydą
Zajmiemy się teraz pewnym szczególnym przypadkiem łańcuchów nieprzywiedlnych.
Definicja 10.1
Łańcuch nieprzywiedlny nazwiemy regularnym, jeśli istnieje taka liczba k∈N∖0, że z każdego stanu Wi, i∈1,…,n można dojść do dowolnego stanu Wj, j∈1,…,n w dokładnie k krokach.
Zauważmy, że rzut monetą jest łańcuchem regularnym, dla którego k=1. Natomiast łatwo podać przykład łańcucha nieprzywiedlnego, który nie jest regularny. Weźmy dla przykładu łańcuch o dwóch stanach W1, W2, dla którego macierz przejścia ma postać
zatem np. ze stanu W1 do W2 przechodzimy zawsze w nieparzystej liczbie kroków, podczas gdy ze stanu W1 do niego samego — w parzystej. Tak zdefiniowany łańcuch jest oczywiście łańcuchem okresowym. Co więcej, można udowodnić następujące twierdzenie
Twierdzenie 10.2
W nieprzywiedlnym łańcuchu Markowa wszystkie stany są tego samego typu, tzn. jeśli choć jeden stan jest powracający, to wszystkie są powracające, jeśli choć jeden jest zerowy, to wszystkie są zerowe, a jeśli choć jeden jest okresowy o okresie d, to wszystkie są okresowe o okresie d.
Niech Wi, Wj będą dwoma różnymi stanami. Ponieważ stany te komunikują się, więc istnieją takie M,N∈N∖0, że
Stosując wzór na prawdopodobieństwo całkowite
|
piiN+M+t=∑l,s=1npilMplstpsiN |
|
dostajemy nierówność
|
piiN+M+t≥pijMpjjtpjiN=αβpjjt, |
|
gdzie α=pijM>0, β=pjiN>0 oraz t∈N∖0. Postępując analogicznie otrzymujemy nierówność
Stąd
|
1αβpiiN+M+t≥pjjt≥αβpiit-M-N. |
|
Powyższe nierówności wykazują, że własności asymptotyczne ciągów piitt∈N oraz pjjtt∈N są takie same. W szczególności, jeśli stan Wi jest zerowy, piit→0 przy t→∞, to także Wj jest zerowy. Z kolei jeśli Wi jest powracający, czyli Pi=∑t=1∞piit=∞, to Wj ma tę samą własność. Załóżmy teraz, że Wi jest okresowy o okresie di. Ponieważ piiM+N≥αβ>0, więc di/M+N (di dzieli M+N). Pokażemy, że Wj jest okresowy i jego okres dj=di. Zauważmy, że jeśli dla pewnego l zachodzi pjjl>0, to także piil+M+N>0, zatem di/l+M+N, czyli di/l, więc di≤dj. Analogicznie dj≤di, skąd di=dj.
∎
W ogólnym przypadku dla łańcuchów nieprzywiedlnych asymptotykę opisuje następujące twierdzenie ergodyczne, którego dowód pomijamy.
Twierdzenie 10.3
Łańcuch Markowa jest nieprzywiedlny wtw jeśli dla każdego j∈1,…,n istnieje niezależna od i granica
|
limt→∞pijt=pj,i,j∈1,…,n, |
|
przy czym pj są jednoznacznym rozwiązaniem układu
|
pj=∑i=1npipij,j=1,…,n,∑j=1npj=1. |
|
Taki asymptotyczny rozkład prawdopodobieństwa nazywamy rozkładem stacjonarnym.
Wynika stąd, że zachowanie asymptotyczne badanego łańcucha nie zależy od stanu początkowego — łańcuch ma własność ,,zapominania” rozkładu początkowego.
Dla łańcuchów regularnych można udowodnić twierdzenie silniejsze.
Twierdzenie 10.4
Macierz P łańcucha regularnego ma pojedynczą wartość własną równą 1. Macierz Pt zbiega do macierzy stochastycznej W o wyrazach dodatnich, której wszystkie wiersze w są jednakowe. Zachodzi wP=w.
Ponieważ dla łańcucha regularnego wszystkie wyrazy macierzy Pk są dodatnie, więc twierdzenie to jest bezpośrednim wnioskiem z twierdzenia Frobeniusa – Perrona dla macierzy o wszystkich wyrazach dodatnich.
∎
Niech P będzie macierzą przejścia łańcucha regularnego, natomiast W jej macierzą graniczną. Można pokazać, że macierz
jest odwracalna, co więcej
Macierz Z nazywamy macierzą fundamentalną łańcucha regularnego i dzięki niej możemy wyznaczyć czasy przejścia i powrotów opisane macierzą E=eiji,j=1n. Mamy
gdzie J jest macierzą o wszystkich wyrazach równych 1,
Zp to macierz, która ma na przekątnej wyrazy takie same jak Z i zera poza przekątną, natomiast D jest macierzą diagonalną o wyrazach na przekątnej równych 1/wi, gdzie w=w1,…,wn oznacza rozkład stacjonarny.
W szczególności wyrazy na przekątnej ejj zadają średni pierwszy czas powrotu do stanu Wj.
Zastosujmy najpierw powyższe twierdzenia do rzutu monetą.
W tym przypadku rozkład stacjonarny znajdujemy bez trudu, gdyż Prmt=Prm dla dowolnego t, zatem w1=w2=0,5. Policzymy jeszcze macierz E, choć możemy się spodziewać rezultatu — średnio co drugi rzut powinien dawać O i co drugi R, zatem średni czas powrotu szacujemy jako 2.
|
Z=I-Prm-W-1=I⟹E=JZpD=D, |
|
co oczywiście implikuje, że średni czas powrotu wynosi 2 rzuty, natomiast średni czas przejścia od O do R i odwrotnie wynosi 1.
Ciągłe krzyżowanie z hybrydą
W tym paragrafie omówimy doświadczenie genetyczne polegające na ciągłym krzyżowaniu z hybrydą. Przebieg doświadczenia jest analogiczny jak w omówionym już przypadku krzyżowania z dominantą, ale matematyczny opis doświadczenia prowadzi do innego typu łańcucha Markowa. W tym łańcuchu mamy także 3 możliwe stany W1=DD, W2=DR i W3=RR. Macierz przejścia tego łańcucha ma postać
|
P=0,50,500,250,50,2500,50,5 |
|
i łatwo sprawdzimy, że P2 jest macierzą o wszystkich wyrazach dodatnich. Zatem mamy do czynienia z łańcuchem regularnym. Policzmy jego rozkład stacjonarny
|
w1,w2,w3P=w1,w2,w3,w1+w2+w3=1, |
|
skąd dostajemy
Wobec tego przy ciągłym krzyżowaniu z hybrydą dostaniemy następujący wynik eksperymentu: bez względu na genotyp drugiego praprzodka po dostatecznie długim czasie średnio 3/4 potomków będzie wykazywało fenotyp dominanty, a 1/4 fenotyp recesywny. Otrzymaliśmy zatem potwierdzenie pierwotnych wyników uzyskanych przez Mendla przy krzyżowaniu groszku, gdzie średnio było 3/4 strąków zielonych i 1/4 strąków żółtych.