10. Markovské řetězce s oceněním přechodů
10.1. Definice: Definice markovského řetězce s oceněním přechodů
Nechť { }0n Nn;X ∈ je homogenní markovský řetězec s konečnou množinou stavů J, v němž jsou všechny stavy trvalé
nenulové neperiodické (tj. ergodické). Předpokládáme, že každému přechodu ze stavu i do stavu j je přiřazeno ocenění rij
(představuje výnos nebo ztrátu spojenou s přechodem z i do j). Tato ocenění uspořádáme do matice R = ( ) Jj,iijr ∈
, která se
nazývá matice výnosů. Řetězec { }0n Nn;X ∈ se pak nazývá markovský řetězec s oceněním přechodů.
10.2. Věta: Rekurentní vztah pro střední hodnotu celkového výnosu po n krocích
Nechť { }0n
Nn;X ∈ je markovský řetězec s oceněním přechodů, který má matici přechodu P a matici ocenění R. Označme
vi(n) střední hodnotu celkového výnosu, který se získá po n krocích, když řetězec vychází ze stavu i. Dále označme
∑∈
=
Jj
ijiji
rpq střední hodnotu výnosu při jednom přechodu ze stavu i. Pak pro Ji ∈∀ a n = 1, 2, 3, ... platí rekurentní vztah:
∑∈
−+=
Jj
jijii )1n(vpq)n(v , přičemž vi(0) = 0.
V maticové formě: v(n) = q + Pv(n-1).
Důkaz: Nebudeme provádět.
10.3. Příklad: Sledujeme provoz výrobní linky, která se může nacházet ve dvou stavech – v provozu (stav 0) nebo
v opravě (stav 1). Dlouhodobým sledováním byla stanovena matice přechodu: P = 





6,04,0
5,05,0
. Jednotlivým přechodům jsou
přiřazena určitá ocenění (tj. výnosy nebo ztráty) prostřednictvím matice výnosů R = 





− 55
410
. Pro i = 0, 1 položíme
vi(0) = 0. Pro oba stavy vypočtěte střední hodnotu celkového výnosu, který se získá za n = 1, 2,…, 6 období.
Řešení: Nejprve vypočteme střední hodnotu výnosu při jednom přechodu ze stavu 0 resp. 1. Přitom
P = 





6,04,0
5,05,0
, R = 





− 55
410
.
745,0105,0rprprpq 01010000
1
0j
j0j00 =⋅+⋅=+== ∑=
, 1)5(6,054,0rprprpq 11111010
1
0j
j1j11 −=−⋅+⋅=+== ∑=
, tj. 





−
=
1
7
q .
Nyní počítáme v(1) = q + Pv(0) = 





−
=











+





− 1
7
0
0
6,04,0
5,05,0
1
7
, v(2) = q + Pv(1) = 





=





−





+





− 2,1
10
1
7
6,04,0
5,05,0
1
7
atd.
Tabulka středních hodnot celkových výnosů pro n = 1, 2, ..., 6:
n 1 2 3 4 5 6
v0(n) 7 10 12,6 15,16 17,716 20,2716
v1(n) -1 1,2 3,72 6,272 8,8278 11,38272
v0(n+1)-v0(n) x 3 2,6 2,56 2,556 2,5556
v1(n+1)-v1(n) x 2,2 2,52 2,552 2,5558 2,55492
v0(n) - v1(n) 8 8,8 8,88 8,888 8,8888 8,88888
Vidíme, že s rostoucím n se rozdíl v0(n) - v1(n) blíží konstantě 8,8 . Znamená to, že když je na počátku sledování linka
v provozu, tak se po dostatečně dlouhé době získá výnos vyšší o 8,8 jednotek než v případě, kdy je linka na počátku
v opravě. Dále můžeme pozorovat, že s rostoucím n se rozdíl vi(n+1) – vi(n) blíží konstantě 5,2 . To souvisí s limitními
vlastnostmi řetězce.
10.4. Poznámka: Je-li{ }0n Nn;X ∈ homogenní markovský řetězec s množinou stavů { }m,,1,0J K= s oceněním
přechodů nerozložitelný, pak existuje jeho stacionární rozložení ( )m10 a,,a,a K=a a platí:
( ) ( )( ) gqanv1nvlim
m
0j
jjii
n
==−+ ∑=
∞→
.
Konstanta g se nazývá zisk řetězce. V př. 10.3. 





−
=





=
1
7
,
9
5
,
9
4
qa , tedy 5,2
9
5
7
9
4
g =−= .
10.5. Věta: Přibližné vyjádření vektoru středních hodnot celkových výnosů po n krocích pomocí limitní
matice přechodu
Nechť A je limitní matice přechodu daného markovského řetězce s oceněním přechodů. Pak pro dostatečně
velká n platí: v(n) ≈ (n-1)Aq + (I – (P – A))-1
q.
Důkaz: Nebudeme provádět.
10.6. Příklad: Pro zadání z příkladu 10.3. najděte přibližné vyjádření pro vektor v(n).
Řešení: Použijeme vzorec v(n) ≈ (n-1)Aq + (I – (P – A))-1
q. Nejprve najdeme limitní matici A, jejíž všechny řádky jsou
stejné a jsou rovny stacionárnímu vektoru matice P. Řešením systému a = aP, a1 + a2 = 1 získáme vektor a = (4/9 5/9),
tudíž A = 





9/59/4
9/59/4
.
Dále q = 





−1
7
, (I – (P – A))-1
= 





−
−
==











+





−





−
0494,10494,0
0617,00617,1
9/59/4
9/59/4
5/35/2
2/12/1
10
01
1
K , tedy
v(n) ≈ (n-1) 







−
+
==





−





−
−
+





−
⋅





9506,3n5,2
9383,4n5,2
1
7
0494,10494,0
0617,00617,1
1
7
9/59/4
9/59/4
K .
Tabulka:
n 1 2 3 4 5 6
v0(n) 7,4938 10,0494 12,609 15,1605 17,716 20,2716
v1(n) -1,3951 1,1605 3,716 6,2716 8,8272 11,3827
Pro porovnání uvedeme tabulku získanou pomocí rekurentního vzorce:
n 1 2 3 4 5 6
v0(n) 7 10 12,6 15,16 17,716 20,2716
v1(n) -1 1,2 3,72 6,272 8,8278 11,38272
10.7. Poznámka: Vektor středních hodnot celkových výnosů po jednom až n obdobích lze získat pomocí funkce
vynos.m:
function a = vynos(P,R,n);
% Autor: Stanislav Tvrz
% syntaxe: function a=vynos(P,R,n);
% funkce pocita:
% vektory strednich hodnot celkovych vynosu po jednom az po n obdobich
% znazorni prubehy vektoru strednich hodnot pro jednotlive stavy
% v zavislosti na poctu obdobi
% vstupni parametry:
% P - matice prechodu, R - matice vynosu, n - pocet obdobi
disp('kontrola - matice prechodu P')
P
disp(' ')
disp('kontrola - matice vynosu R')
R
disp(' ')
vel=size(P);
v=zeros(vel(1),n+1);
q=diag(P*R');
for i=2:n+1
v(:,i)=q+P*v(:,i-1);
end
cas=0:n;
vysledek=[cas;v];
disp('sloupcove vektory strednich hodnot celkovych vynosu po n krocich')
disp(num2str(vysledek))
disp('pozn: na prvnim radku hodnoty n')
%generovani popisu stavu
max_ind=size(num2str(vel(1)),2);
legenda=zeros(vel(1),5+max_ind);
for i=1:vel(1)
legenda(i,1:5+size(num2str(i),2))=[['stav '],num2str(i)];
end
legenda=char(legenda);
%graf celkovych vynosu
figure
plot([0:n],v);
legend(legenda)
end
Použijeme-li tuto funkci pro řešení příkladu 10.3. pro jedno až 6 období, dostaneme výsledky:
sloupcove vektory strednich hodnot celkovych vynosu po n krocich
0 1 2 3 4 5 6
0 7 10 12.6 15.16 17.716 20.2716
0 -1 1.2 3.72 6.272 8.8272 11.3827
pozn: na prvnim radku hodnoty n
Graf celkových výnosů:
0 1 2 3 4 5 6
-5
0
5
10
15
20
25
stav 1
stav 2
10.8. Definice: Definice markovského řetězce s diskontovaným oceněním přechodů
Nechť v homogenním markovském řetězci s oceněním přechodů je přechod ze stavu i v čase n do stavu j v čase n+1 oceněn
číslem βn
rij, kde číslo β (0 < β < 1) je tzv. diskontní faktor. Uvedený řetězec se pak nazývá markovský řetězec
s diskontovaným oceněním přechodů.
Vysvětlení: Diskontní faktor snižuje hodnotu budoucího výnosu. Vystupuje v roli odúročitele, může být 1/(1+i), kde i je
úročitel. Může také vyjadřovat pravděpodobnost, že proces bude dále pokračovat. Jeho užití bude účelné tam, kde se může
očekávat, že proces skončí, ale neví se, kdy přesně k tomu dojde.
10.9. Věta: Rekurentní vztah pro vektor středních hodnot diskontovaných celkových výnosů po n krocích.
Pro vektor středních hodnot diskontovaných celkových výnosů platí rekurentní vztah:
v(n) = q + βPv(n-1), přičemž v(0) = 0.
Limitní hodnota vektoru středních hodnot celkových výnosů je ∞→n
lim v(n) = (I – βP)-1
q
Důkaz: Nebudeme provádět.
10.10. Příklad: V příkladu 10.3. předpokládejme, že diskontní faktor β = 0,5 značí pravděpodobnost, že proces bude dále
pokračovat. Pomocí rekurentního vztahu najděte vektor v(n) středních hodnot celkových výnosů pro n = 1, 2, …, 6 a
stanovte limitní hodnotu tohoto vektoru.
Řešení: q = 





−1
7
, v(0) = 





0
0
, P = 





6,04,0
5,05,0
, β = 0,5, v(n) = q + βPv(n-1).
v(1) = 





−1
7
+ 





6,04,0
5,05,0
5,0 





0
0
= 





−1
7
, v(2) = 





−1
7
+ 





6,04,0
5,05,0
5,0 





−1
7
= 





1,0
5,8
atd.
Dále uvedeme tabulku středních hodnot celkových výnosů pro n = 1, 2, ..., 6.
n 1 2 3 4 5 6
v0(n) 7 8,5 9,15 9,47 9,6297 9,7096
v1(n) -1 0,1 0,73 0,1049 1,2087 1,2886
v0(n)- v1(n) 8 8,4 8,42 8,3651 8,4210 8,4210
Nyní vypočteme limitní hodnotu vektoru středních hodnot celkových výnosů podle vzorce: ∞→n
lim v(n) = (I – βP)-1
q.










−
−
=





−





=β−
10
7
5
1
4
1
4
3
6,04,0
5,05,0
5,0
10
01
PI ,
40
19
5
1
4
1
10
7
4
3
=⋅−⋅=β− PI ,
( )












=












=β−
−
19
30
19
8
19
10
19
28
4
3
5
1
4
1
10
7
19
401
PI , ( ) ( ) 





=












=





−
⋅












==β−=
−
∞→ 3684,1
7895,9
19
26
19
186
1
7
19
30
19
8
19
10
19
28
qnlim
1
n
PIv
Rozdíl složek limitního vektoru: 9,7895 – 1,3684 = 8,4219.
Znamená to, že když je na počátku sledování linka v provozu, tak se po dostatečně dlouhé době získá výnos vyšší o 8,4219
jednotek než v případě, kdy je linka na počátku v opravě.
10. 11. Poznámka: Vektor středních hodnot diskontovaných výnosů po jednom až n obdobích a limitní hodnotu tohoto
vektoru lze získat pomocí funkce diskont.m:
function a=diskont(P,R,beta,n);
% Autor: Stanislav Tvrz
% function a=diskont(P,R,beta,n);
% funkce pocita:
% vektory strednich hodnot diskontovanych vynosu po jednom az po n obdobich
% limitni vektor strednich hodnot diskontovanych vynosu
% znazorni prubehy vektoru strednich hodnot pro jednotlive stavy
% v zavislosti na poctu obdobi
% vstupni parametry:
% P - matice prechodu
% R - matice vynosu
% beta - diskontni faktor
% n - pocet obdobi
%clc;
disp('kontrola - matice prechodu P')
P
disp(' ')
disp('kontrola - matice vynosu R')
R
disp(' ')
vel=size(P);
v=zeros(vel(1),n+1);
q=diag(P*R');
for i=2:n+1
v(:,i)=q+beta*P*v(:,i-1);
end
cas=0:n;
vysledek=[cas;v];
disp('sloupcove vektory strednich hodnot diskontovanych vynosu po n krocich')
disp(num2str(vysledek))
disp(['pri hodnote diskontniho faktoru beta = ',num2str(beta)])
disp('pozn: na prvnim radku hodnoty n')
disp(' ')
disp('limitni vektor v(n)')
v_n=inv(eye(vel(1))-beta*P)*q;
disp(num2str(v_n))
%generovani popisu stavu
max_ind=size(num2str(vel(1)),2);
legenda=zeros(vel(1),5+max_ind);
for i=1:vel(1)
legenda(i,1:5+size(num2str(i),2))=[['stav '],num2str(i)];
end
legenda=char(legenda);
%graf diskontovanych vynosu
figure
plot([0:n],v);
legend(legenda)
end
Použijeme-li tuto funkci pro řešení příkladu 10.10. pro jedno až 6 období, dostaneme tyto výsledky:
sloupcove vektory strednich hodnot diskontovanych vynosu po n krocich
0 1 2 3 4 5 6
0 7 8.5 9.15 9.47 9.6297 9.7096
0 -1 0.1 0.73 1.049 1.2087 1.2886
pri hodnote diskontniho faktoru beta = 0.5
pozn: na prvnim radku hodnoty n
limitni vektor v(n)
9.7895
1.3684
Graf diskontovaných výnosů:
0 1 2 3 4 5 6
-2
0
2
4
6
8
10
stav 1
stav 2