Návod na 1. cvičení v počítačové učebně, Markovské řetězce, PS 2011


Věta o vlastnostech homogenního markovského řetězce: Nechť  je markovský řetězec s vektorem
počátečních pravděpodobností p(0) a maticí přechodu P. Pak pro  platí:

a) P(n,n+m) = P(m) = P^m.

b) p(n,n+m) = p(m) = p(0)P^m.


Příklad 1.: (Klasifikace roků podle úrody jablek) V severní Nové Anglii můžeme klasifikovat roky
podle úrody jablek jako úrodné, průměrné a neúrodné. Pravděpodobnost, že po úrodném roce bude
následovat rok úrodný, průměrný, neúrodný, je postupně 0,4; 0,4; 0,2. Pravděpodobnost, že po
průměrném roce bude následovat rok úrodný, průměrný, neúrodný, je postupně 0,2; 0,6; 0,2.
Pravděpodobnost, že po neúrodném roce bude následovat rok úrodný, průměrný, neúrodný, je postupně
0,2; 0,4; 0,4. Rok 1965 byl úrodný. Vypočtěte vektor absolutních pravděpodobností pro rok 1967.


Řešení: Zavedeme homogenní markovský řetězec  s množinou stavů J = {0,1,2}, kde stav 0 znamená
úrodný rok, stav 1 průměrný rok a stav 2 neúrodný rok. Náhodná veličina X[n] nabývá hodnoty j, když
n-tý rok odpovídá stavu j. Sestavíme matici přechodu

. Vektor počátečních pravděpodobností je p(0) = (1, 0, 0). Hledáme vektor p(2) = p(0)P^2 = (0,28,
0,48,  0,24).


Návod na řešení v MATLABu:

P=[0.4 0.4 0.2;0.2 0.6 0.2;0.2 0.4 0.4];

p0=[1 0 0];

p2= p0*P^2


Příklad 2.: V příkladu 1 předpokládejme, že pravděpodobnost, že rok bude úrodný, je 0,25, průměrný
0,5 a neúrodný 0,25. Jaký je vektor absolutních pravděpodobností pro příští rok?


Řešení: Vektor počátečních pravděpodobností nyní bude p(0) = . Vypočteme vektor absolutních
pravděpodobností p(1) = p(0)P = .


Návod na řešení v MATLABu:

P=[0.4 0.4 0.2;0.2 0.6 0.2;0.2 0.4 0.4];

p0=[1/4 1/2 1/4];

p1= p0*P


Příklad 3. – k samostatnému řešení: Půjčovna aut, která vlastní 1000 automobilů, působí ve třech
pobočkách A, B, C. Zákazník si může vybrat auto v některé z poboček a vrátit ho v kterékoliv jiné
pobočce. Dlouhodobým sledováním v týdenním intervalu byly zjištěny tyto skutečnosti:
Pravděpodobnost vrácení auta do stejné pobočky, z níž bylo vypůjčeno, je pro pobočky A, B, C
postupně 0,6; 0,6; 0,5. Pravděpodobnost, že auto vypůjčené v A bude vráceno v B, je 0,3 a naopak,
pravděpodobnost, že auto vypůjčené v B bude vráceno v A, je 0,2. Pravděpodobnost, že auto vypůjčené
v B bude vráceno v C, je 0,2 a naopak, pravděpodobnost, že auto vypůjčené v C bude vráceno v B, je
0,4. Zjednodušeně předpokládáme, že žádné auto není ukradeno ani nehavaruje.

a)      Modelujte provoz půjčovny aut pomocí HMŘ, najděte matici přechodu a nakreslete přechodový
diagram.

b)      Předpokládejme, že na počátku sledování je 500 aut v pobočce A, 300 v B a 200 v C. Určete,
kolik aut bude v jednotlivých pobočkách po uplynutí 1 týdne.


Výsledek: Po týdnu sledování bude v pobočce A 380 aut, v pobočce B 410 aut a v pobočce C 210 aut.


Příklad 4. – k samostatnému řešení: Uvažme podnik, v němž jsou tři oddělené provozy – provoz 1,
provoz 2 a provoz 3. V těchto provozech pracují dělníci vykonávající jednostranné úkony. Aby
nedocházelo k otupění zaměstnanců, tak se dělníci na konci měsíce v jednotlivých provozech náhodně
střídají. Existuje samozřejmě i jistá šance, že si dělník najde jiné zaměstnání a podnik opustí.
Předpokládáme, že v takovém případě už se do podniku nevrátí. Dlouhodobým pozorováním pohybu
zaměstnanců v tomto podniku byly zjištěny následující skutečnosti:

Dělníci z provozu 1 na konci měsíce s pravděpodobností 1/4 zůstávají v provozu 1,
s pravděpodobností 1/4 přecházejí do provozu 2 a s pravděpodobností 1/2 přecházejí do provozu 3.

Dělníci v provozu 2 na konci měsíce s pravděpodobností 1/4 zůstávají v provozu 2,
s pravděpodobností 1/4 přecházejí do provozu 1 a s pravděpodobností 1/2 přecházejí do provozu 3.

Jelikož práce v provozu 3 je velmi namáhavá, tak po měsíci dělníci z tohoto provozu odcházejí se
stejnou pravděpodobností buď do provozu 1 nebo do provozu 2.

Dále bylo zjištěno, že zaměstnanci z tohoto podniku odcházejí pouze z provozu 3, a to
s pravděpodobností 1/9.

a)      Modelujte tuto situaci pomocí HMŘ, najděte matici přechodu a nakreslete přechodový diagram.

b)      Vypočtěte pravděpodobnost, že zaměstnanec, který na počátku sledování pracoval v provozu 1,
ve čtvrtém měsíci sledování již v podniku pracovat nebude.


Výsledek: Pravděpodobnost, že ve 4. měsíci už zaměstnanec nebude v podniku pracovat, je .


Definice stacionárního vektoru stochastické matice: Nechť a je stochastický vektor a P stochastická
matice odpovídající dimenze. Jestliže platí a = aP, pak vektor a se nazývá stacionární vektor
matice P.


Definice stacionárního rozložení HMŘ: Nechť  je homogenní markovský řetězec s maticí přechodu P.
Stochastický vektor a, který je stacionárním vektorem matice P, se nazývá stacionární rozložení
daného řetězce.


Definice limitního rozložení HMŘ: Nechť  je homogenní markovský řetězec s vektorem počátečních
pravděpodobností p(0). Jestliže existuje , pak vektor  se nazývá limitní rozložení daného řetězce.
Jestliže vektor  nezávisí na vektoru počátečních pravděpodobností p(0), pak řekneme, že daný
řetězec je ergodický (regulární).


Věta o vztahu mezi stacionárním a limitním rozložením HMŘ: Jestliže  je ergodický homogenní
markovský řetězec a existuje jeho stacionární rozložení a, pak limitní rozložení  je rovno
stacionárnímu rozložení a.


Markovova věta: Nechť  je homogenní markovský řetězec s maticí přechodu P. Jestliže existuje takové
číslo , že matice P^n má všechny prvky kladné, pak

a) existuje stacionární rozložení daného řetězce a je jediné,

b) řetězec  je ergodický,

c) posloupnost matic P^n konverguje k limitní matici A, jejíž řádky jsou stejné a jsou rovny
stacionárnímu vektoru a.


Návod na hledání stacionárního vektoru stochastické matice pomocí MATLABu

function [a]=sv(P)

%funkce pro vypocet stacionarniho vektoru

%syntaxe: a=sv(P)

%vstupni parametr ... stochasticka matice P

%vystupni parametr ... stacionarni vektor a

%zjistime rad matice P:

n=size(P,1);

%vytvorime pomocnou jednotkovou matici:

I=eye(n);

%sestavime matici soustavy:

A=[[I-P]';ones(1,n)];

%vytvorime vektor pravých stran:

f=[zeros(n,1);1];

%vypocteme stacionární vektor

a=(A\f)';


Příklad 5.: Předpokládejme, že v nějaké oblasti může být počasí pouze ve třech stavech, a to déšť,
jasno, sníh. Dlouhodobým pozorováním bylo zjištěno, že nikdy nebývají dva jasné dny za sebou.
Jestliže je v jistém dni jasno, pak další den bude buď déšť nebo sníh, a to se stejnou
pravděpodobností. Jestliže je v jistém dni sníh nebo déšť, pak následující den se počasí buď
nezmění, a to s pravděpodobností 0,5 nebo se změní, a pak v polovině případů bude jasno. Popište
stav počasí homogenním markovským řetězcem a vypočtěte jeho stacionární rozložení.


Řešení: Homogenní markovský řetězec  má množinu stavů , kde stav 1 znamená déšť, stav 2 jasno a
stav 3 sníh. Matice přechodu P má tvar:

.


Návod na řešení v MATLABu:

P=[0.5 0.25 0.25;0.5 0 0.5;0.25 0.25 0.5];

a=sv(P)


Výsledek: a = (0,4  0,2  0,4)

Znamená to, že po 40 % dnů prší, po 20 % dnů je jasno a po 40 % dnů sněží.


Příklad 6. – k samostatnému řešení: Obchodník prodává tři druhy pracích prášků, které označíme A,
B, C. Aby zjistil, jak se vyvíjí poptávka po těchto prášcích, provedl v 1. měsíci prodeje průzkum,
v němž se zjišťovalo, který druh prášku zákazníci kupují. Při tomto průzkumu bylo zjištěno, že
prášek A kupuje 50% zákazníků, prášek B 20% a prášek C 30% zákazníků. Za měsíc byl proveden další
průzkum, který zjišťoval, ke kterému druhu prášků zákazníci přešli. Výsledky průzkumu zachycuje
matice přechodu: .

a) Určete absolutní pravděpodobnosti po dvou měsících a interpretujte je. (Po dvou měsících bude
prášek A nakupovat 80,6% zákazníků, prášek B 12,8% a C 6,6% zákazníků.

b) Najděte vektor limitních pravděpodobností a limitní matici přechodu.

( , )