Příklady na čtvrté cvičení v počítačové učebně, SMI, PS 2010
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ů.
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))-1
q, kde A je limitní matice přechodu.
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 vektor q = diag(P*R’);
Vypočteme vektor v1=q+P*v0
Vypočteme vektor v2=q+P*v1
Příklad 2.: 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))-1
q 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ý.
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. (Může
např. vyjadřovat pravděpodobnost, že proces bude dále pokračovat.) Uvedený řetězec se pak
nazývá markovský řetězec s diskontovaným oceněním přechodů.
Rekurentní metoda výpočtu středních hodnot celkových výnosů
Pro vektor středních hodnot diskontovaných celkových výnosů platí rekurentní vztah:
v(n) = q + βPv(n-1), n = 1, 2, …, přičemž v(0) = 0.
Výpočet vytvořující funkce Gv(z) posloupnosti vektorů  
1n)n(v
  qPIv
1
z
z1
z
)z(G




Limitní hodnota vektoru středních hodnot celkových výnosů
n
lim v(n) = (I – βP)-1
q
Příklad 3.: Výrobce nealkoholických nápojů hodlá nabídnout síti potravinových obchodů
nápoj D s novou příchutí. Je si vědom konkurence tří současných oblíbených typů
nealkoholických nápojů A, B, C, ale věří, že zákazníci ocení příznivé složení a dobrou chuť
nápoje D a budou jej preferovat, jakmile ho ochutnají. Na základě zkušeností s obdobnými
produkty byla sestavena matice přechodu (časovým krokem je 1 týden):
P =














85,005,005,005,0
30,060,005,005,0
10,005,075,010,0
10,015,010,065,0
.
Výnos nebo ztráta, které plynou z jednotlivých přechodů, jsou uvedeny v matici výnosů:
R =


















4333
3211
5121
5112
.
Diskontní faktor je 0,5. Pro prvních 10 týdnů vypočtěte vektor středních hodnot celkových
výnosů. Zjistěte také limitní hodnotu vektoru středních hodnot celkových výnosů.
Návod na řešení v MATLABu:
Zadáme matice P, R, vektor v0 a diskontní faktor beta:
P=[0.65 0.1 0.15 0.1;0.1 0.75 0.05 0.1;0.05 0.05 0.6 0.3;0.05 0.05 0.05 0.85];
R=[-2 -1 -1 5;-1 -2 -1 5;-1 -1 -2 3;-3 -3 -3 4];
v0=[0 0 0 0]‘; beta=0.5;
Vypočteme vektor q = diag(P*R’);
vektor v1=q+beta*P*v0
vektor v2=q+beta*P*v1
atd. až
vektor v10=q+beta*P*v9
Výsledek:
v(0) v(1) v(2) v(3) v(4) … v(9) v(10)
A 0 -1,050 -1,331 -1,360 -1,331 … -1,255 -1,253
B 0 -1,150 -1,496 -1,574 -1,574 … -1,525 -1,523
C 0 -0,400 -0,133 0,110 0,255 … 0,402 0,405
D 0 2,950 4,139 4,635 4,849 … 5,023 5,025
Výpočet limitního vektoru v(n):
Zadáme jednotkovou matici I = eye(4);
limitni_v=(I-beta*P)^(-1)*q
n
lim v(n) = (-1,2506, -1,5216, 0,4069, 5,0276)
Upozornění: Ve Studijních materiálech v ISu je uložena funkce diskont.m, která počítá:
- vektory středních hodnot diskontovaných výnosů po jednom období až po n obdobích,
- limitní vektor středních hodnot diskontovaných výnosů,
- znázorní průběhy vektorů středních hodnot pro jednotlivé stavy v závislosti na počtu období.