Dla łańcuchów pochłaniających postać kanoniczna macierzy przejścia przedstawia się następująco
![]() |
gdzie oznacza macierz jednostkową wymiaru
reprezentującą
stanów pochłaniających,
jest macierzą wymiaru
przejścia ze stanów nieistotnych do stanów pochłaniających, a
— macierzą
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
dla
(zbieżność po wyrazach);
macierz 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 krokach dąży do
przy
, a ponieważ
odpowiada stanom nieistotnym, zatem każde z pozostałych prawdopodobieństw dąży do
. Dalej zauważmy, że
![]() |
Skoro , to
, a z ciągłości wyznacznika wynika, że dla dostatecznie dużych
zachodzi
, czyli także
, więc
macierz
jest odwracalna. Stąd
![]() |
i przechodząc do granicy 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 .
Jaka jest oczekiwana liczba przejść przez stan , zakładając że stanem początkowym jest
?
Jaka jest oczekiwana liczba kroków przed absorpcją, jeśli stanem początkowym jest ?
Jakie jest prawdopodobieństwo absorpcji przez dany stan pochłaniający , jeśli stanem początkowym jest
?
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
Niech będzie macierzą fundamentalną łańcucha pochłaniającego.
Oczekiwana liczba przejść przez stan przy stanie początkowym
jest równa
.
Oczekiwana liczba kroków przed absorpcją dla łańcucha o stanie początkowym zadana jest jako suma wyrazów w
. wierszu macierzy
.
Niech będzie
macierzą prawdopodobieństw absorpcji przez stan
przy stanie początkowym
. Wtedy
.
Niech oznacza oczekiwaną liczba przejść przez stan
przy stanie początkowym
. Wprowadźmy zmienną losową
![]() |
Niech oznacza wartość średnią
przy warunku, że proces zaczął się w stanie
. Wtedy
![]() |
czyli ostatecznie . Skoro
jest
. wyrazem macierzy
, to
jest
. wyrazem macierzy
, czyli
.
Bezpośrednio z tego wzoru otrzymujemy także, że średni czas do absorpcji jest sumą wyrazów w wierszu .
Wyprowadzimy teraz wzór rekurencyjny na prawdopodobieństwo . Niech
będzie stanem początkowym nieistotnym. W pierwszym kroku łańcuch może przejść do interesującego nas stanu pochłaniającego
, do innego stanu pochłaniającego
,
, albo do któregoś ze stanów nieistotnych
z prawdopodobieństwami zadanymi przez macierz
. Prawdopodobieństwa absorpcji przez stan
ze stanu
,
oraz
są odpowiednio równe
,
oraz
. Stąd
![]() |
Skoro oraz
są odpowiednio stanem nieistotnym i pochłaniającym, więc
jest
. wyrazem macierzy
i analogicznie
jest
. wyrazem macierzy
. Zatem
![]() |
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 i jeden stan nieistotny
. Odpowiednie podmacierze macierzy
są jednoelementowe
![]() |
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 , natomiast
oczekiwana liczba kroków do absorpcji równa się
.
Rozpatrzmy teraz następujący ciąg doświadczeń tworzący
łańcuch Markowa. Bierzemy ustalonego osobnika o genotypie dominującym 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
możliwe wyniki eksperymentu, ponieważ są
genotypy. Ponumerujmy je w następujący sposób:
![]() |
Odpowiednie prawdopodobieństwa wynoszą
, gdyż zawsze ze skrzyżowania dominanty z dominantą otrzymujemy ten sam genotyp. Stąd
dla
i stan
jest pochłaniający.
oraz
, gdyż krzyżując dominantę z hybrydą otrzymujemy z prawdopodobieństwem
albo dominantę, albo hybrydę, nie możemy natomiast dostać osobnika recesywnego;
,
, 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ą
![]() |
Na jej podstawie wnioskujemy, że jeśli wybranym rodzicem była hybryda, to średni czas do absorpcji wynosi , natomiast jeśli osobnik recesywny, to
. Możemy jeszcze sprawdzić punkt
. twierdzenia wykonując mnożenie
![]() |
co oczywiście potwierdza, że z prawdopodobieństwem nasz eksperyment kończy się osobnikami o genotypie
.
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 ,
oraz
, zatem odpowiednio numerując stany dostajemy dokładnie taką samą dynamikę łańcucha pochłaniającego jak w przypadku krzyżowania z dominantą.
Zajmiemy się teraz pewnym szczególnym przypadkiem łańcuchów nieprzywiedlnych.
Łańcuch nieprzywiedlny nazwiemy regularnym, jeśli istnieje taka liczba , że z każdego stanu
,
można dojść do dowolnego stanu
,
w dokładnie
krokach.
Zauważmy, że rzut monetą jest łańcuchem regularnym, dla którego . Natomiast łatwo podać przykład łańcucha nieprzywiedlnego, który nie jest regularny. Weźmy dla przykładu łańcuch o dwóch stanach
,
, dla którego macierz przejścia ma postać
![]() |
zatem np. ze stanu do
przechodzimy zawsze w nieparzystej liczbie kroków, podczas gdy ze stanu
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
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 , to wszystkie są okresowe o okresie
.
Niech ,
będą dwoma różnymi stanami. Ponieważ stany te komunikują się, więc istnieją takie
, że
![]() |
Stosując wzór na prawdopodobieństwo całkowite
![]() |
dostajemy nierówność
![]() |
gdzie ,
oraz
. Postępując analogicznie otrzymujemy nierówność
![]() |
Stąd
![]() |
Powyższe nierówności wykazują, że własności asymptotyczne ciągów oraz
są takie same. W szczególności, jeśli stan
jest zerowy,
przy
, to także
jest zerowy. Z kolei jeśli
jest powracający, czyli
, to
ma tę samą własność. Załóżmy teraz, że
jest okresowy o okresie
. Ponieważ
, więc
(
dzieli
). Pokażemy, że
jest okresowy i jego okres
. Zauważmy, że jeśli dla pewnego
zachodzi
, to także
, zatem
, czyli
, więc
. Analogicznie
, skąd
.
W ogólnym przypadku dla łańcuchów nieprzywiedlnych asymptotykę opisuje następujące twierdzenie ergodyczne, którego dowód pomijamy.
Łańcuch Markowa jest nieprzywiedlny wtw jeśli dla każdego istnieje niezależna od
granica
![]() |
przy czym są jednoznacznym rozwiązaniem układu
![]() |
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.
Macierz łańcucha regularnego ma pojedynczą wartość własną równą
. Macierz
zbiega do macierzy stochastycznej
o wyrazach dodatnich, której wszystkie wiersze
są jednakowe. Zachodzi
.
Ponieważ dla łańcucha regularnego wszystkie wyrazy macierzy są dodatnie, więc twierdzenie to jest bezpośrednim wnioskiem z twierdzenia Frobeniusa – Perrona dla macierzy o wszystkich wyrazach dodatnich.
Niech będzie macierzą przejścia łańcucha regularnego, natomiast
jej macierzą graniczną. Można pokazać, że macierz
![]() |
jest odwracalna, co więcej
![]() |
Macierz nazywamy macierzą fundamentalną łańcucha regularnego i dzięki niej możemy wyznaczyć czasy przejścia i powrotów opisane macierzą
. Mamy
![]() |
gdzie jest macierzą o wszystkich wyrazach równych
,
to macierz, która ma na przekątnej wyrazy takie same jak
i zera poza przekątną, natomiast
jest macierzą diagonalną o wyrazach na przekątnej równych
, gdzie
oznacza rozkład stacjonarny.
W szczególności wyrazy na przekątnej
zadają średni pierwszy czas powrotu do stanu
.
Zastosujmy najpierw powyższe twierdzenia do rzutu monetą.
W tym przypadku rozkład stacjonarny znajdujemy bez trudu, gdyż dla dowolnego
, zatem
. Policzymy jeszcze macierz
, choć możemy się spodziewać rezultatu — średnio co drugi rzut powinien dawać
i co drugi
, zatem średni czas powrotu szacujemy jako
.
![]() |
co oczywiście implikuje, że średni czas powrotu wynosi rzuty, natomiast średni czas przejścia od
do
i odwrotnie wynosi
.
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 możliwe stany
,
i
. Macierz przejścia tego łańcucha ma postać
![]() |
i łatwo sprawdzimy, że jest macierzą o wszystkich wyrazach dodatnich. Zatem mamy do czynienia z łańcuchem regularnym. Policzmy jego rozkład stacjonarny
![]() |
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 potomków będzie wykazywało fenotyp dominanty, a
fenotyp recesywny. Otrzymaliśmy zatem potwierdzenie pierwotnych wyników uzyskanych przez Mendla przy krzyżowaniu groszku, gdzie średnio było
strąków zielonych i
strąków żółtych.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.