9. Absorpční homogenní markovské řetězce
9.1. Definice: Definice absorpčního stavu
Nechť { }0n Nn;X ∈ je homogenní markovský řetězec s množinou stavů J.
Řekneme, že stav Jj∈ je absorpční stav, jestliže pjj = 1 (tzn., že ze stavu j není dosažitelný žádný jiný stav). Když řetězec
vstoupí do absorpčního stavu, pak řekneme, že je absorbován.
9.2. Věta: Věta o vztahu mezi absorpčním stavem a trvalým stavem
Každý absorpční stav je trvalým stavem.
Důkaz: Plyne přímo z definice trvalého stavu.
9.3. Definice: Definice absorpčního homogenního markovského řetězce
Homogenní markovský řetězec s konečnou množinou stavů se nazývá absorpční, jestliže každý jeho trvalý stav je absorpční.
9.4. Příklad: Nechť { }0n Nn;X ∈ je homogenní markovský řetězec s množinou stavů J = {0,1, ..., 5} a maticí přechodu




















=
100000
001000
010000
4/304/1000
0003/103/2
000010
P . Zjistěte, zda jde o absorpční řetězec.
Řešení:
Přechodový diagram
JT = {3,4}∪ {5}, JP = {0, 1, 2}.
Stavy 3 a 4 jsou trvalé, ale nejsou absorpční. Řetězec tedy není absorpční.
0 1
2/3
1
2
1/3
3
3/4
1/4
4
1
1
5
1
9.5. Definice: Definice fundamentální matice absorpčního řetězce
Nechť { }0n
Nn;X ∈ je absorpční řetězec s konečnou množinou stavů, který má r absorpčních a s neabsorpčních stavů. Stavy
přečíslujeme tak, aby po množině JA r absorpčních stavů následovala množina JN s neabsorpčních stavů. Matici přechodu P
přepíšeme do kanonického tvaru 





=
QR
0I
P , kde
I je jednotková matice řádu r,
0 je nulová matice typu r x s,
R je matice typu s x r obsahující pravděpodobnosti přechodu z neabsorpčních do absorpčních stavů a
Q je čtvercová matice řádu s obsahující pravděpodobnosti přechodu mezi neabsorpčními stavy.
Matice ( ) 1−
−= QIM (kde I je jednotková matice řádu s) se nazývá fundamentální matice absorpčního řetězce. Inverzní
matice existuje, pokud Qn
konverguje k 0.
Vysvětlení: Prvek mij matice M udává střední hodnotu počtu kroků, které řetězec stráví v neabsorpčním stavu j před
přechodem do absorpčního stavu, pokud vyšel z neabsorpčního stavu i. Matici M se též říká matice středních dob přechodu.
Přesnost výpočtu střední doby mij můžeme posoudit pomocí rozptylu sij
2
střední doby přechodu. Matici S tvořenou rozptyly
sij
2
vypočítáme podle vzorce kv)ˆ2( MIMMS −−= , kde matice Mkv obsahuje mij
2
.
9.6. Poznámka: Význam součtu prvků v i-tém řádku fundamentální matice M
Střední hodnotu počtu kroků, které řetězec stráví v neabsorpčních stavech, když vychází z neabsorpčního stavu i a skončí
v absorpčním stavu, vypočítáme jako součet prvků v i-tém řádku fundamentální matice M. Maticový zápis: t = Me, kde e je
sloupcový vektor typu s x 1 ze samých jedniček.
Přesnost vypočtené střední hodnoty doby do absorpce posoudíme pomocí rozptylu. Vektor rozptylů se počítá podle vzorce:
kv)( ttI2Mrt −−= , kde vektor tkv obsahuje druhé mocniny prvků vektoru t.
9.7. Příklad: Dva hráči A a B dali dohromady do hry vklad 4 Kč. Hráč A hází mincí. Když padne líc, vyhrává 1 Kč, když
rub, prohrává 1 Kč. Hra trvá tak dlouho, až je jeden z hráčů zruinován.
a) Popište situaci pomocí homogenního markovského řetězce. Najděte matici přechodu a nakreslete přechodový diagram.
b) Ukažte, že řetězec je absorpční.
c) Najděte fundamentální matici a interpretujte její prvky.
b) Vypočtěte střední hodnotu a rozptyl počtu kroků, které řetězec stráví v neabsorpčních stavech.
Řešení:
ad a) Zavedeme homogenní markovský řetězce { }0n Nn;X ∈ s množinou stavů J = {0,1, 2, 3, 4}, přičemž Xn = j, když v ntém
kroku hry má hráč A právě j Kč.
Matice přechodu:
















=
10000
2/102/100
02/102/10
002/102/1
00001
P
Přechodový diagram:
ad b) JT = {0}∪ {4}, JP = {1, 2, 3}. Trvalé stavy 0 a 4 jsou absorpční, řetězec je tedy absorpční.
0 1
1
1/2
2
1/2
1/2
3
1/2
1/2
4
1/2
1
ad c) Matici přechodu v kanonickém tvaru získáme tak, že nejprve zapíšeme pravděpodobnosti přechodu vztahující se
k absorpčním stavům 0 a 4 a poté pravděpodobnosti přechodu vztahující se k neabsorpčním stavům 1, 2, 3.
Původní matice přechodu:
















=
10000
2/102/100
02/102/10
002/102/1
00001
P
Matice přechodu v kanonickém tvaru:
















=
02/102/10
2/102/100
02/1002/1
00010
00001
P
Pro výpočet fundamentální matice M potřebujeme matici Q obsahující pravděpodobnosti přechodu mezi neabsorpčními
stavy:
321










−
−−
−
=−










=
12/10
2/112/1
02/11
,
02/10
2/102/1
02/10
QIQ , ( )










=−=
−
2/312/1
121
2/112/3
3
2
1
1
QIM
Interpretace: Podívejme se např. na druhý řádek matice M. Má-li hráč A v daném okamžiku 2 Kč, pak lze očekávat, že
před skončením hry bude mít v průměru jedenkrát 1 Kč, dvakrát 2 Kč a jedenkrát 3 Kč.
ad d) Podle poznámky 9.6. dostáváme:
t = Me =










=










⋅










3
4
3
1
1
1
2/312/1
121
2/112/3 Interpretace: Má-li hráč A v daném okamžiku buď 1 Kč nebo 3 Kč, tak v průměru
po třech krocích hra skončí. Má-li hráč A v daném okamžiku 2 Kč, pak v průměru
po čtyřech krocích hra skončí.










=










−










⋅










=−−=
8
8
8
9
16
9
3
4
3
221
232
122
kv)( ttI2Mrt
Vidíme, že všechny střední hodnoty dob do absorpce jsou vypočteny se stejnou přesností.
9.8. Věta: Věta o pravděpodobnostech přechodu do absorpčních stavů
Označme bij pravděpodobnost, že řetězec vycházející z neabsorpčního stavu i bude absorbován ve stavu j.
Sestavíme matici B = ( ) AN Jj,Jiijb ∈∈
.
Pak B = MR, kde M je fundamentální matice absorpčního řetězce a R je matice v levém dolním rohu matice přechodu P
v kanonickém tvaru.
Důkaz: Nechť i je neabsorpční a j absorpční stav. Stavu j může být dosaženo 1. krokem s pravděpodobností pij nebo
přechodem do neabsorpčního stavu k s pravděpodobností pik a odtud přechodem do absorpčního stavu j s pravděpodobností
bkj. Tedy ∑∈
+=
NJk
kjikijij bppb . Maticově: B = R + QB, B – QB = R, (I – Q)B = R, B = (I – Q)-1
R = MR.
9.9. Definice: Definice matice přechodu do absorpčních stavů daného absorpčního řetězce
Matice B se nazývá matice přechodu do absorpčních stavů daného absorpčního řetězce.
9.10. Příklad: Pro zadání z příkladu 9.7. vypočtěte matici přechodu do absorpčních stavů a interpretujte její prvky. Pro
připomenutí: Dva hráči A a B dali dohromady do hry vklad 4 Kč. Hráč A hází mincí. Když padne líc, vyhrává 1 Kč, když
rub, prohrává 1 Kč. Hra trvá tak dlouho, až je jeden z hráčů zruinován.
Řešení:
Matice přechodu v kanonickém tvaru:
















=
02/102/10
2/102/100
02/1002/1
002/110
00001
P , tedy










=
2/10
00
02/1
R . Již jsme vypočetli, že










=
2/312/1
121
2/112/3
M , tedy B = MR =










=










⋅










4/34/1
2/12/1
4/14/3
2/10
00
02/1
2/312/1
121
2/112/3
.
Interpretace: Má-li hráč A v daném okamžiku 1 Kč, pak bude s pravděpodobností 3/4 zruinován on a s pravděpodobností
1/4 bude zruinován hráč B. Má-li hráč A v daném okamžiku 2 Kč, pak bude s pravděpodobností 1/2 zruinován on a
s pravděpodobností 1/2 bude zruinován hráč B. Má-li hráč A v daném okamžiku 3 Kč, pak bude s pravděpodobností 1/4
zruinován on a s pravděpodobností 3/4 bude zruinován hráč B.
9.11. Poznámka: Charakteristiky absorpčního řetězce můžeme v MATLABu vypočítat pomocí funkce absorb.m:
function [P0,M,B,t,rt]=absorb(P)
% Funkce pro vypocet zakladnich charakteristik absorpcniho retezce
% Autor: Hana Tužilová
% function [P0,M,B,t]=absorb(P)
% vstupni parametr: matice prechodu P
% vystupni parametry: P0 ... matice prechodu v kanonickem tvaru
% M ... fundamentalni matice
% B ... matice prechodu do absorpcnich stavu
% t ... vektor strednich hodnot poctu kroku pred
% absorpci
% rt ... vektor rozptyu poctu kroku pred
% absorpci
D=diag(P); % identifikace absorpcnich stavu
j=find(D==1);
n=length(P);
T=1:n;
T(j)=[];
T=[j',T];
A=zeros(n); % sestaveni kanonickeho tvaru matice P
T=(0:n:(n^2-n))+T;
A(T)=1;
P0=A'*P*A;
m=length(j); % vypocet ostatnich charakteristik
Q=P0((m+1):n,(m+1):n);
M=eye(n-m)/(eye(n-m)-Q);
R=P0((m+1):n,1:m);
B=M*R;
t=M*ones(n-m,1);
tkv=t.*t;
rt=(2*M-eye(n-m))*t-tkv;
Použijeme-li tuto funkci na řešení příkladu 9.10., dostaneme výsledky:
Pk =
1.0000 0 0 0 0
0 1.0000 0 0 0
0.5000 0 0 0.5000 0
0 0 0.5000 0 0.5000
0 0.5000 0 0.5000 0
M =
1.5000 1.0000 0.5000
1.0000 2.0000 1.0000
0.5000 1.0000 1.5000
B =
0.7500 0.2500
0.5000 0.5000
0.2500 0.7500
t =
3.0000
4.0000
3.0000
rt =
8.0000
8.0000
8.0000
9.12. Příklad: Jistá firma třídí svoje pohledávky po termínu splatnosti do 30 denních intervalů. Pohledávky, které jsou
nad 90 dnů po době splatnosti, jsou považovány za nedobytné. K popisu situace zavedeme homogenní markovský řetězec
s množinou stavů J = {1, 2, 3, 4, 5}, kde
stav 1 znamená pohledávky 0 – 30 dní po době splatnosti,
stav 2 pohledávky 31 – 60 dní po době splatnosti,
stav 3 pohledávky 61 – 90 dní po době splatnosti,
stav 4 splacené pohledávky a
stav 5 nedobytné pohledávky.
Dlouhodobou analýzou doby splatnosti jednotlivých pohledávek bylo zjištěno, že pravděpodobnosti přechodu jsou:
p12 = 0,77, p14 = 0,23, p23 = 0,34, p24 = 0,66, p34 = 0,73 a p35 = 0,27.
Úkoly:
a) Sestavte matici přechodu.
b) Klasifikujte stavy na absorpční a neabsorpční a najděte kanonický tvar matice přechodu.
c) Vypočtěte fundamentální matici a interpretujte její prvky.
d) Vypočtěte matici přechodu do absorpčních stavů a interpretujte její prvky.
e) Zjistěte vektor středních hodnot počtu kroků před absorpcí.
f) Předpokládejme, že objem pohledávek po termínu splatnosti v jednotlivých 30 denních intervalech je (4 030 000 Kč,
9 097 000 Kč, 3 377 000 Kč). Jaká je průměrná hodnota splacených a nedobytných pohledávek?
Řešení:
ad a)
1 2 3 4 5 Přechodový diagram:
















=
10000
01000
27,073,0000
066,034,000
023,0077,00
5
4
3
2
1
P
ad b) Řetězec má tři přechodné stavy, a to 1, 2, 3 a dva trvalé stavy, a to 4 a 5. Oba jsou absorpční, tedy řetězec je absorpční.
Kanonický tvar matice přechodu:
4 5 1 2 3
















=
00027,073,0
34,000066,0
077,00023,0
00010
00001
3
2
1
5
4
P ,










=
27,073,0
066,0
023,0
R ,










=
000
34,000
077,00
Q .
ad c) Vypočteme fundamentální matici absorpčního řetězce:
1 2 3
( )










=−=
−
100
34,010
26,077,01
3
2
1
1
QIM
Interpretace 1. řádku: pohledávka zařazená do stavu 1 v něm v průměru stráví 1 x 30 = 30 dnů než bude splacena nebo
zařazena mezi nedobytné pohledávky. Pohledávka zařazená do stavu 1 stráví v průměru 0,77 x 30 = 23,1 dne ve stavu 2 než
bude splacena nebo zařazena mezi nedobytné pohledávky. Pohledávka zařazená do stavu 1 stráví v průměru 0,26 x 30 = 7,8
dne ve stavu 3 než bude splacena nebo zařazena mezi nedobytné pohledávky.
ad d) Vypočteme matici přechodu do absorpčních stavů:
4 5










=










⋅










==
27,073,0
0918,09082,0
0707,09293,0
3
2
1
27,073,0
066,0
023,0
100
34,010
26,077,01
MRB .
Interpretace 1. řádku: pohledávka zařazená do stavu 1 bude s pravděpodobností 0,9293 splacena a s pravděpodobností
0,0707 se stane nedobytnou.
ad e) Vypočteme vektor středních hodnot počtu kroků před absorpcí:










=




















==
1
34,1
03,2
3
2
1
1
1
1
100
34,010
26,077,01
Met
Interpretace:
2,03 x 30 = 60,9 – pohledávce zařazené do stavu 1 bude v průměru trvat 60,9 dne než bude splacena nebo zařazena mezi
nedobytné pohledávky.
1,34 x 30 = 40,2 – pohledávce zařazené do stavu 2 bude v průměru trvat 40,2 dne než bude splacena nebo zařazena mezi
nedobytné pohledávky.
1 x 30 = 30 – pohledávce zařazené do stavu 3 bude v průměru trvat 30 dnů než bude splacena nebo zařazena mezi nedobytné
pohledávky.
ad f) Připomínáme, že objem pohledávek po termínu splatnosti v jednotlivých 30 denních intervalech je
(4 030 000 Kč, 9 097 000 Kč, 3 377 000 Kč). Průměrná hodnota splacených a nedobytných pohledávek:
( ) ( )203181614472184
27,073,0
0918,09082,0
0707,09293,0
337700090970004030000 =










Průměrná hodnota splacených pohledávek je tedy 14 472 184 Kč a nedobytných pohledávek je 2 031 816 Kč.
9.13. Využití markovských řetězců v genetice
Výskyt sledované vlastnosti u jedinců určitého typu je dán dvojicí alel A, a. Každý jedinec může mít dvojici
alel AA (dominantní homozygot), aa (recesivní homozygot), aA=Aa (hybridní jedinec). Základním
předpokladem genetiky je, že při křížení dostává potomek jednu alelu od každého z rodičů, přičemž tyto
alely se vybírají náhodně a nezávisle na sobě. Pomocí homogenních markovských řetězců budeme
modelovat rozmnožovací cyklus diploidních rostlin.
Situace 1 – křížení diploidní cizosprašné rostliny
Z populace diploidní cizosprašné rostliny náhodně vybereme jedince, zkřížíme ho
a) s dominantním homozygotem,
b) s recesivním homozygotem,
c) s hybridem.
V příštím kroku pokusu náhodně vybereme jedince z populace jeho potomků, opět ho zkřížíme
a) s dominantním homozygotem,
b) s recesivním homozygotem,
c) s hybridem atd.
Všechny tři možnosti budeme modelovat pomocí HMŘ, vždy najdeme matici přechodu a stacionární
rozložení. V případě, že se bude jednat o absorpční řetězec, najdeme jeho fundamentální matici a matici
přechodu do absorpčních stavů.
Zavedeme HMŘ { }Nn;Xn ∈ s množinou stavů { }3,2,1J = , přičemž Xn = 1, když v n-tém kroku pokusu
získáme dominantního jedince, Xn = 2, když v n-tém kroku pokusu získáme recesivního jedince a Xn = 3,
když v n-tém kroku pokusu získáme hybridního jedince.
a) Křížení s dominantním homozygotem
Stanovení matice přechodu:
AA x AA ⇒AA, AA, AA, AA
aa x AA⇒ aA, aA, aA, aA
aA x AA ⇒ aA, AA, aA, AA
Řetězec má jediný trvalý stav (stav 1 = AA), který je absorpční, jde tedy o absorpční řetězec.
Výpočet stacionárního rozložení:
aP = a, a1 + a2 + a3 = 1
( ) ( )321321 aaa
21021
100
001
aaa =










1a1aaa
0aa
2
1
aaa
2
1
a
0aaa
2
1
a
1321
232332
3131
=⇒=++
=⇒=⇒=+
=⇒=+
a = (1, 0 ,0)
Znamená to, že při křížení diploidní cizosprašné rostliny s dominantním homozygotem získáme po
dostatečně velkém počtu kroků vždy dominantního homozygota.
Výpočet fundamentální matice:
Matice přechodu P je zadána přímo v kanonickém tvaru 





=
QR
0I
P , kde 





=
210
10
Q , 





=
21
0
R .
2 3
Fundamentální matice 





=













−





=
−
20
21
3
2
210
10
10
01
1
M .
Interpretace 1. řádku matice M: Pokud se řetězec v daném okamžiku nachází ve stavu 2 (tj. aa – recesivní
homozygot), tak v průměru se před absorpcí ve stavu dominantního homozygota ocitne 1x ve stavu
recesivního homozygota a 2x ve stavu hybrida.
Interpretace 2. řádku matice M: Pokud se řetězec v daném okamžiku nachází ve stavu 3 (tj. aA - hybrid), tak
v průměru se před absorpcí ve stavu dominantního homozygota ocitne 2x ve stavu hybrida.
Výpočet matice přechodu do absorpčních stavů:






=











==
1
1
21
0
20
21
MRB
Je-li řetězec v daném okamžiku ve stavu 2 (tj. recesivní homozygot) nebo ve stavu 3 (tj. hybrid), tak
s pravděpodobností 1 bude absorbován ve stavu dominantního homozygota.
b) Křížení s recesivním homozygotem
Stanovení matice přechodu:
AA x aa ⇒aA, aA, aA, aA
aa x aa⇒ aa, aa, aa, aa
aA x aa ⇒ aa, aA, aa, aA
Řetězec má jediný trvalý stav (stav 2 = aa), který je absorpční, jde tedy o absorpční řetězec.
Výpočet stacionárního rozložení:
aP = a, a1 + a2 + a3 = 1
( ) ( )321321 aaa
21210
010
100
aaa =










1a1aaa
0aaa
2
1
a
0aaa
2
1
a
2321
1331
3232
=⇒=++
=⇒=+
=⇒=+
a = (0, 1 ,0)
Znamená to, že při křížení diploidní cizosprašné rostliny s recesivním homozygotem získáme po dostatečně
velkém počtu kroků vždy recesivního homozygota.
Výpočet fundamentální matice:
2 1 3
Kanonický tvar matice P:










=
21021
100
001
3
1
2
P
, tedy 





=
210
10
Q , 





=
21
0
R .
1 3
Fundamentální matice 





=













−





=
−
20
21
3
1
210
10
10
01
1
M .
Interpretace 1. řádku matice M: Pokud se řetězec v daném okamžiku nachází ve stavu 1 (tj. AA –
dominantní homozygot), tak v průměru se před absorpcí ve stavu recesivního homozygota ocitne 1x ve stavu
dominantního homozygota a 2x ve stavu hybrida.
Interpretace 2. řádku matice M: Pokud se řetězec v daném okamžiku nachází ve stavu 3 (tj. aA - hybrid), tak
v průměru se před absorpcí ve stavu recesivního homozygota ocitne 2x ve stavu hybrida.
Výpočet matice přechodu do absorpčních stavů:






=











==
1
1
21
0
20
21
MRB
Je-li řetězec v daném okamžiku ve stavu 1 (tj. dominantní homozygot) nebo ve stavu 3 (tj. hybrid), tak
s pravděpodobností 1 bude absorbován ve stavu recesivního homozygota.
c) Křížení s hybridním jedincem
Stanovení matice přechodu:
AA x aA ⇒aA, aA, AA, AA
aa x aA⇒ aa, aa, aA, aA
aA x aA ⇒ aa, aA, aA, AA
Všechny stavy řetězce jsou trvalé, ale žádný není absorpční, řetězec tedy není absorpční.
Výpočet stacionárního rozložení:
aP = a, a1 + a2 + a3 = 1
( ) ( )321321 aaa
214141
21210
21021
aaa =










4
1
aa,
2
1
a1aa
2
1
a
2
1
1aaa
aa2aa
4
1
a
2
1
aa2aa
4
1
a
2
1
213333321
32232
31131
===⇒=++⇒=++
=⇒=+
=⇒=+
a = (0,25, 0,25, 0,5)
Znamená to, že při křížení diploidní cizosprašné rostliny s hybridním jedincem získáme po dostatečně
velkém počtu kroků s pravděpodobností 0,25 dominantního jedince, s pravděpodobností 0,25 recesivního
jedince a s pravděpodobností 0,5 hybridního jedince.
Výpočet středních hodnot dob prvních vstupů:
( )MZEZIM
))
+−= , kde E je matice ze samých jedniček, matice Z
)
obsahuje jen diagonální prvky matice
( )( ) 1−
−−= APIZ (A je limitní matice přechodu) a matice M
)
obsahuje jen diagonální prvky matice M.
Přitom diagonální prvky matice M jsou převrácené hodnoty složek stacionárního vektoru.
Výpočtem zjistíme, že










=
266
248
284
M .
Interpretace 1. řádku matice M: Když řetězec vychází ze stavu dominantního homozygota, tak v průměru
bude trvat 4 kroky, než se do něj vrátí. V průměru bude trvat 8 kroků, než se dostane do stavu recesivního
homozygota a v průměru bude trvat 2 kroky, než se dostane do stavu hybrida.
Situace 2 – křížení diploidní samosprašné rostliny
Z populace diploidní samosprašné rostliny náhodně vybereme jedince, samosprášíme ho, z populace jeho
potomků náhodně vybereme jedince, opět ho samosprášíme atd.
Stanovení matice přechodu:
AA x AA ⇒AA, AA, AA, AA
aa x aa⇒ aa, aa, aa, aa
aA x aA ⇒ aa, aA, aA, AA
Řetězec má dva trvalé stavy (stav 1 = AA, stav 2 = aa), které jsou absorpční, řetězec je tedy absorpční.
Výpočet stacionárního rozložení:
aP = a, a1 + a2 + a3 = 1
( ) ( )321321 aaa
214141
010
001
aaa =










1aa1aaa
0aaa
4
1
a
0aaa
4
1
a
21321
3232
3131
=+⇒=++
=⇒=+
=⇒=+
Vidíme, že stacionární rozložení neexistuje.
Výpočet fundamentální matice:
1 2 3
Kanonický tvar matice P:










=
214141
010
001
3
2
1
P , tedy ( )21=Q , ( )4141=R .
Fundamentální matice ( ) 2211
1
=−=
−
M .
Znamená to, že když je řetězec v daném okamžiku ve stavu 3 (tj. ve stavu hybrida), , tak v něm v průměru
setrvá dva kroky, než bude absorbován ve stavu dominantního či recesivního homozygota.
Výpočet matice přechodu do absorpčních stavů:






=





⋅==
2
1
2
1
4
1
4
1
2MRB
Je-li řetězec v daném okamžiku ve stavu 3 (tj. hybrid), tak s pravděpodobností 1/2 bude absorbován ve stavu
dominantního homozygota či recesivního homozygota.