Příklady na čtvrté cvičení v počítačové učebně, SMI, PS 2009
Definice markovskéhp ř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ů.
Rekurentní metoda výpočtu středních hodnot celkových výnosů
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,


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
iijii )1n(vpq)n(v
, přičemž vi(0) = 0.
V maticové formě: v(n) = q + Pv(n-1), n = 1, 2, ...
Výpočet vytvořující funkce Gv(z) posloupnosti vektorů
 
1n)n(v
  qPIv
1
z
z1
z
)z(G




Aproximační vzorec pro výpočet středních hodnot celkových výnosů
v(n)  (n-1)Aq + (I - (P - A))-1q.
Příklad 1.: Řidič taxi dlouhodobým pozorováním zjistil, že když se v daném okamžiku nachází ve
městě A, pak s pravděpodobností 0,3 poveze příštího zákazníka do města B a s pravděpodobností
0,7 bude zákazník žádat jízdu uvnitř A. Jestliže se řidič taxi nachází ve městě B, pak se stejnou
pravděpodobností buď poveze příštího zákazníka do A nebo bude jezdit uvnitř B. Průměrná tržba
za jízdu (v obou směrech) mezi A a B činí 1000 Kč a uvnitř měst A a B 100 Kč. Vypočítejte
střední hodnotu tržby za první dvě jízdy, vyjede-li řidič z města A resp. B.
Řešení:
Zavedeme HMŘ
 0n Nn;X 
s množinou stavů J = {0,1}, přičemž Xn = 0 (resp. 1), když v
okamžiku n je řidič ve městě A (resp. B). Matice













1001000
1000100
,
5,05,0
3,07,0
RP
.
q0 = 0,7.100 + 0,3.1000 = 370, q1 = 0,5.1000 + 0,5.100 = 550
q =






550
370
, v(0) =






0
0
.
v(1) = q + P v(0) =






550
370
v(2) = q + P v(1) =






550
370
+






5,05,0
3,07,0






550
370
=






1010
794
Vyjede-li řidič z města A, bude mít za první dvě jízdy v průměru tržbu 794 Kč. Vyjede-li řidič z
města B, bude mít za první dvě jízdy v průměru tržbu 1010 Kč.
Návod na řešení v MATLABu:
Zadáme matice P, R a vektor v0:
P=[0.7 0.3;0.5 0.5]; R=[100 1000;1000 100];v0=[0 0]`;
Vypočteme pomocnou matici Q=P*R';
Diagonála matice Q je vektor q=diag(Q);
Vypočteme vektor v1=q+P*v0
Vypočteme vektor v2=q+P*v1
Upozornění:
Posloupnost vektorů v(n) lze v MATLABu získat pomocí cyklu:
v(:,1) = [0;0]
n=2;
for i=1:n
v(:,i+1) = q + P*v(:, i)
end
Příklad 2.: Předpokládejme, že chovatel má slepici, která buď snáší vejce (stav 0) nebo sedí na
vejcích (stav 1). Uvažujeme období o délce 1 měsíc. Matice přechodu a matice výnosů jsou:













6-3
28
,
7,03,0
4,06,0
RP
.
a) Pomocí vytvořujících funkcí najděte vektor středních hodnot celkových výnosů po n měsících.
b) Jaký je vektor středních hodnot celkových výnosů pro n = 1, 2, ..., 24? Graficky znázorněte
závislost středních hodnot celkových výnosů na n.
Řešení:
Zavedeme HMŘ
 0n Nn;X 
s množinou stavů J = {0,1}, přičemž Xn = 0 (resp. 1), když v
měsíci n slepice snáší vejce (resp. sedí na vejcích). Matice













6-3
28
,
7,03,0
4,06,0
RP
.
q0 = 0,6.8 + 0,4.2 = 5,6, q1 = 0,3.3 + 0,7.(-6) = -3,3
q =






 3,3
6,5
, v(0) =






0
0
.
  qPIv
1
z
z1
z
)z(G




= ... =
 






























70
267
70
356
10
z3
1
7
10
z1
7
10
70
36
70
36
z1
z
2
 2
z1
z
 je vytvořující funkce posloupnosti an = n, n = 0, 1, 2, ...
z1
1
7
10


je vytvořující funkce posloupnosti an = 7
10
1
7
10 n

, n = 0, 1, 2, ...
10
z3
1
1
7
10


je vytvořující funkce posloupnosti an =
n
3,0
7
10

, n = 0, 1, 2, ...
Celkem:
   



























70
267
70
356
3,01
7
10
70
36
70
36
nn n
v
v(1) =






 3,3
6,5
, v(2) =






 93,3
64,7
, v(3) =






 759,3
612,8
, ..., v(24) =






8939,6
6082,19
.
Návod na řešení v MATLABu:
Zadáme vektor n: n=[0:1:24];
Napíšeme vyjádření pro první složku vektoru v(n):
v0n=n.*(36/70)+(10/7)*(1-0.3.^n)*(356/70)
Napíšeme vyjádření pro druhou složku vektoru v(n):
v1n=n.*(36/70)+(10/7)*(1-0.3.^n)*(-267/70)
Graficky znázorníme závislost středních hodnot celkových výnosů na n:
plot(n,v0n,'o',n,v1n,'*')
Příklad 3.: Výrobce limonád pravidelně sleduje prodejnost nového výrobku na domácím trhu.
Výrobek hodnotí v každém sledovaném období jako úspěšný (stav 0) nebo jako neúspěšný (stav
1), přičemž lze předpokládat, že úspěšnost či neúspěšnost prodeje v daném období je ovlivněna
jen tím, jak se výrobek prodával v předchozím období. Dlouhodobým sledováním prodeje byly
zjištěny tyto poznatky: pokud byl výrobek v jednom období úspěšný, pak v následujícím období
bude úspěšný s pravděpodobností 0,8. Jestliže byl výrobek v jednom období neúspěšný, tak v
následujícím období zůstane neúspěšný s pravděpodobností 0,7. Zůstává-li výrobek úspěšný, je
výnos 10 jednotek. Změní-li se z úspěšného na neúspěšný, klesne výnos na 5 jednotek. Při změně
z neúspěšného na úspěšný je výnos 10 jednotek a zůstává-li výrobek neúspěšný, dojde ke ztrátě
20 jednotek.
a) Modelujte proces pomocí homogenního markovského řetězce. Najděte matici přechodu a
matici výnosů.
b) Pomocí rekurentního vzorce v(n) = q + P v(n-1) vypočtěte pro oba stavy střední hodnotu
celkového výnosu, který se získá za n období, n = 1, 2, ..., 6.
c) Pomocí aproximačního vzorce v(n)  (n-1)Aq + (I - (P - A))-1q najděte přibližné vyjádření pro
vektor středních hodnot celkových výnosů v(n). Pro n = 1, 2, ..., 6 porovnejte výsledky s přesným
vyjádřením získaným v bodě (b).
Řešení:
ad a) Zavedeme HMŘ
 0n Nn;X 
s množinou stavů J = {0,1}, přičemž Xn = 0 (resp. 1), když v
n-tém období je výrobek úspěšný (resp. neúspěšný). Matice













20-10
510
,
7,03,0
2,08,0
RP
.
ad b) Výpočet pomocí rekurentního vzorce:
q0 = 0,8.10 + 0,2.5 = 9, q1 = 0,3.10 + 0,7.(-20) = -11
q =






11
9
, v(0) =






0
0
.
v(1) = q + P v(0) =






11
9
, v(2) = q + P v(1) =






16
14
, v(3) = q + P v(2) =






18
17
,
v(4) = q + P v(3) =






 5,18
19
, v(5) = q + P v(4) =






 25,18
5,20
, v(6) = q + P v(5) =






 625,17
75,21
ad c) Výpočet pomocí aproximačního vzorce:
Nejprve najdeme stacionární vektor a matice P (viz Příklady na druhé cvičení v počítačové
učebně) a sestavíme limitní matici A =






4,06,0
4,06,0
. Po dosazení do aproximačního vzorce
získáme výsledky:
v(1) =






 23
17
, v(2) =






 22
18
, v(3) =






 21
19
, v(4) =






 20
20
, v(5) =






19
21
, v(6) =






18
22
Je zřejmé, že aproximační vzorec je pro malá n nevhodný.