Návod na 4. cvičení v počítačové učebně, Markovské řetězce, PS 2011 Definice markovského řetězce s oceněním přechodů Nechť 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í r[ij] (představuje výnos nebo ztrátu spojenou s přechodem z i do j). Tato ocenění uspořádáme do matice R = , která se nazývá matice výnosů. Řetězec 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ť je markovský řetězec s oceněním přechodů, který má matici přechodu P a matici ocenění R. Označme v[i](n) střední hodnotu celkového výnosu, který se získá po n krocích, když řetězec vychází ze stavu i, střední hodnotu výnosu při jednom přechodu ze stavu i. Pak pro a n = 1, 2, 3, ... platí rekurentní vztah: , přičemž v[i](0) = 0. V maticové formě: v(n) = q + Pv(n-1), n = 1, 2, … Aproximační vzorec pro výpočet středních hodnot celkových výnosů v(n) ≈ (n-1)Aq + (I – (P – A))^-1q, 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Ř s množinou stavů J = {0,1}, přičemž X[n] = 0 (resp. 1), když v okamžiku n je řidič ve městě A (resp. B). Matice . q[0] = 0,7.100 + 0,3.1000 = 370, q[1] = 0,5.1000 + 0,5.100 = 550 q = , v(0) = . v(1) = q + P v(0) = v(2) = q + P v(1) = + = 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 Upozornění: Ve Studijních materiálech v ISu je uložena funkce vynos.m, která počítá: - vektory středních hodnot celkových výnosů po jednom období až po n obdobích, - znázorní průběhy vektorů středních hodnot pro jednotlivé stavy v závislosti na počtu období. 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))^-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Ř s množinou stavů J = {0,1}, přičemž X[n] = 0 (resp. 1), když v n-tém období je výrobek úspěšný (resp. neúspěšný). Matice . ad b) Výpočet pomocí rekurentního vzorce: q[0] = 0,8.10 + 0,2.5 = 9, q[1] = 0,3.10 + 0,7.(-20) = -11 q = , v(0) = . v(1) = q + P v(0) = , v(2) = q + P v(1) = , v(3) = q + P v(2) = , v(4) = q + P v(3) = , v(5) = q + P v(4) = , v(6) = q + P v(5) = 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 = . Po dosazení do aproximačního vzorce získáme výsledky: v(1) = , v(2) = , v(3) = , v(4) = , v(5) = , v(6) = 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 β^nr[ij], 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. Limitní hodnota vektoru středních hodnot celkových výnosů v(n) = (I – βP)^-1q 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 = . Výnos nebo ztráta, které plynou z jednotlivých přechodů, jsou uvedeny v matici výnosů: R = . 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 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í. Dobrovolný samostatný úkol: Upravte funkci vynos.m tak, aby poskytovala ještě zisk řetězce, tj .