13. Markovské řetězce se spojitým časem – základní pojmy 13.1. Definice: Definice markovského řetězce se spojitým časem Nechť ( )P,,ΑΩ je pravděpodobnostní prostor, )∞= ,0T je indexová množina, jejíž prvky nazveme okamžiky a J = {..., -2, -1, 0, 1, 2, ...} je nejvýše spočetná množina stavů (bez újmy na obecnosti lze předpokládat, že J = {0, 1, 2, ...} nebo J = {0,1, ..., n}). Stochastický proces { }Tt;Xt ∈ definovaný na měřitelném prostoru ( )ΑΩ, , jehož složky Xt nabývají hodnot z množiny stavů J, se nazývá markovský řetězec (se spojitým časem), jsou-li splněny následující podmínky: a) ( ) 0jXP:TtJj t >=∈∃∈∀ (vyloučení nepotřebných stavů) b) ( ) ( ) ( )1ntnt0t2nt1ntntn10n10n10 jX/jXPjXjXjX/jXP:Jj,,j,jtttTt,,t,t 1nn02n1nn −−− ====∧∧=∧==∈∀<<<∈∀ −−− KKKK za předpokladu, že ( ) 0jXjXjXP 0t2nt1nt 02n1n >=∧∧=∧= −− −− K (markovská vlastnost – budoucí chování markovského řetězce závisí pouze na přítomném stavu a nikoliv na stavech minulých). Vysvětlení: Markovské řetězce se spojitým časem modelují fyzikální či jiné soustavy, které mohou v libovolném okamžiku náhodně přejít do některého ze svých možných stavů. Markovská vlastnost znamená, že to, do jakého stavu se soustava dostane při následující změně, závisí pouze na tom, v jakém stavu se soustava právě nachází a nezávisí na stavech předchozích. Např. sledujeme-li během pracovní doby provoz automatických strojů v dílně, náhodná veličina Xt, )T,0t∈ je počet strojů, které v okamžiku t nepracují (jsou opravovány nebo čekají na opravu). 13.2. Příklad: Uvažme populaci, jejíž jedinci se mohou množit a zanikat. Pravděpodobnost, že z libovolného jedince vznikne v časovém intervalu ( ht,t + nový jedinec, je ( )hoh +λ (symbol o(h) znamená, že ( ) 0 h ho lim 0h = +→ ) a pravděpodobnost, že libovolný jedinec zanikne v intervalu ( ht,t + , je ( )hoh +µ . Osudy jedinců jsou navzájem nezávislé. Označme Xt rozsah populace v čase t. Pak stochastický proces { }Tt;Xt ∈ je markovský řetězec se spojitým časem. Nazývá se lineární proces vzniku a zániku (resp. lineární proces množení a úmrtí). 13.3. Označení: Jev {Xt = j} – markovský řetězec je v okamžiku t ve stavu j. P(Xt = j) = pj(t) – absolutní pravděpodobnost stavu j v okamžiku t. p(t) = (...., pj(t), ...) – vektor absolutních pravděpodobností. ( ) ( )ht,tpiX/jXP ijtht +===+ – pravděpodobnost přechodu ze stavu i v okamžiku t do stavu j v okamžiku t+h           +=+ M LL M )ht,t(p)ht,t( ij P - matice pravděpodobností přechodu mezi okamžiky t, t+h. P(X0 = j) = pj(0) – počáteční pravděpodobnost stavu j. p(0) = (...., pj(0), ...) – vektor počátečních pravděpodobností. 13.4. Věta: Věta o vlastnostech markovského řetězce se spojitým časem Nechť { }Tt;Xt ∈ je markovský řetězec. Pokud dále uvedené podmíněné pravděpodobnosti existují, platí pro Jj,iTg,h,t ∈∀∈∀ : a) P(Xt+h = j / Xt = i) ≥ 0, tj. pij(t,t+h) ≥ 0 ( )    ≠ = === jipro0 jipro1 iX/jXP tt , tj. ( )    ≠ = = jproi0 jipro1 t,tpij . b) ( ) 1iX/jXP Jj tht ===∑∈ + , tj. ( )∑∈ =+ Jj ij 1ht,tp . (Přechod ze stavu i v okamžiku t do nějakého stavu j v okamžiku t+h je jev s pravděpodobností 1.) c) ( ) ( ) ( )kX/jXPiX/kXPiX/jXP htght Jk thttght ======= +++ ∈ +++ ∑ , tj. ∑∈ ++++=++ Jk kjikij )ght,ht(p)ht,t(p)ght,t(p (Chapmanovy – Kolmogorovovy rovnice) d) ( ) ( ) ( )kX/jXPkXPjXP tht Jk tht ===== + ∈ + ∑ , tj. ∑∈ +=+ Jk kjkj )ht,t(p)t(p)ht(p (Zákon evoluce) Důkaz: Analogicky jako v diskrétním případě. 13.5. Poznámka: Zápis vlastností markovského řetězce se spojitým časem v maticovém tvaru a) P(t,t+h) ≥ 0, kde 0 je nulová matice, P(t,t) = I, kde I je jednotková matice. b) P(t,t+h)e = e, kde e je sloupcový vektor ze samých jedniček. c) P(t,t+h+g) = P(t,t+h) P(t+h,t+h+g). d) p(t+h) = p(t) P(t,t+h). 13.6. Definice: Definice HMŘ se spojitým časem Nechť { }Tt;Xt ∈ je markovský řetězec se spojitým časem. Řekneme, že tento řetězec je homogenní, jestliže platí: ( ) ( )hpiX/jXP:Tht,Jj,i ijtht ===∈∀∈∀ + . Vysvětlení: Znamená to, že pravděpodobnosti přechodu ( )iX/jXP tht ==+ – pokud existují – závisí pouze na časovém přírůstku h a nezávisí na časovém okamžiku t. Matice pravděpodobností přechodu P(t,t+h) se pak značí P(h) a nazývá se matice přechodu za časový přírůstek h. Pro HMŘ se spojitým časem tedy existuje celý systém matic přechodu ( ){ }Th,hP ∈ . Je zvykem definovat P(0) = I. 13.7. Věta: Vyjádření simultánní pravděpodobnostní funkce pro HMŘ Pro homogenní markovský řetězec se spojitým časem platí: ( ) ( ) ( ) ( )njj1jjjnhht1ht0tn10n1 hphptpjXjXjXP:Jj,,j,jTh,,h,t n1n100n11 − ==∧∧=∧=∈∀∈∀ ++++ KKKK K Důkaz: Plyne z věty o násobení pravděpodobností a markovské vlastnosti. 13.8. Věta: CH-K rovnice a zákon evoluce pro HMŘ Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem, s vektorem počátečních pravděpodobností p(0) a systémem matic přechodu ( ){ }Th,h ∈P . Pak pro Tg,h ∈∀ platí: a) P(h+g) = P(h) P(g) (Chapmanova – Kolmogorovova rovnice) b) p(h) = p(0) P(h) (zákon evoluce) Důkaz: ad a) plyne z tvrzení (c) věty 13.4 ad b) plyne z tvrzení (d) věty 13.4 13.9. Věta: Existenční věta Ke každému stochastickému vektoru p(0) a ke každému systému stochastických matic ( ){ }Th;h ∈P , které splňují CH-K rovnice, existuje HMŘ se spojitým časem, jehož počáteční pravděpodobnosti jsou dány vektorem p(0) a systém matic pravděpodobností přechodu je právě ( ){ }Th;h ∈P . 14. Matice intenzit přechodu homogenního markovského řetězce se spojitým časem 14.1. Motivace: Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem. Předpokládejme, že v okamžiku t je řetězec ve stavu i a za časový přírůstek h přejde do stavu j s pravděpodobností pij(h). Číslo ( ) h hpij vyjadřuje průměrnou pravděpodobnost přechodu ze stavu i do stavu j za časový přírůstek h. Označme pii(h) pravděpodobnost, že za časový přírůstek h řetězec setrvá ve stavu i. Pak 1 - pii(h) je pravděpodobnost, že za časový přírůstek h řetězec přejde do nějakého jiného stavu. Číslo ( ) h hp1 ii − vyjadřuje průměrnou pravděpodobnost výstupu řetězce ze stavu i za časový přírůstek h. Intenzity přechodu resp. výstupu popisují chování těchto průměrných pravděpodobností pro + → 0h . 14.2. Poznámka: Nadále budeme předpokládat, že a) Jj,i ∈∀ existuje ( ) h hp lim ij 0h +→ b) Ji∈∀ existuje ( ) h hp1 lim ii 0h − +→ c) Jj,i ∈∀ existuje ( )    ≠ = = +→ jipro0 jipro1 hplim ij 0h 14.3. Definice: Definice intenzit přechodu a výstupu Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem se systémem matic přechodu ( ){ }Th,h ∈P . Pak definujeme: a) Jj,i ∈∀ : ( ) h hp limq ij 0h ij +→ = - intenzita přechodu ze stavu i do stavu j b) Ji∈∀ : ( ) h hp1 limq ii 0h i − = +→ - intenzita výstupu ze stavu i. 14.4. Poznámka: Intenzita přechodu ( ) h hp limq ij 0hij +→ = resp. výstupu ( ) h hp1 limq ii 0hi − = +→ je derivací pravděpodobnosti přechodu resp. záporně vzatou derivací pravděpodobnosti výstupu. Tyto derivace jsou počítány pro h → 0+. Je tedy nutné funkce pij(h) a pii(h) spojitě dodefinovat na intervalu )h,0 . Hodnotu pij(0+) určíme takto: ( ) ( ) 0hlimqh h hp limhplim 0h ij ij 0h ij 0h === +++ →→→ , neboť qij ≠ 0, tedy pij(0+) = 0. Hodnotu pii(0+) určíme takto: ( ) ( ) ( ) 11hlimq1h h 1hp limh h hp limhplim 0h i ii 0h ii 0h ii 0h =+−=+ − == ++++ →→→→ , neboť qi ≠ 0, tedy pii(0+) = 1. Z definice intenzity přechodu ( ) h hp limq ij 0hij +→ = plyne, že pij(h) = hqij + o(h). Z definice intenzity výstupu ( ) h hp1 limq ii 0hi − = +→ plyne, že pii(h) = 1- hqi + o(h). Pro dostatečně malá h tedy dostáváme pij(h) ≈ hqij resp. pii(h) ≈ 1- hqi. Číslo qij vyjadřuje koeficient nárůstu pravděpodobnosti přechodu pij(h) během krátkého časového intervalu délky h a číslo qi vyjadřuje koeficient poklesu pravděpodobnosti setrvání pii(h) během krátkého časového intervalu délky h. Na obrázku vidíme průběhy funkcí pij(h) a pii(h) v pravém okolí bodu 0. Čárkovaně jsou zakresleny tečny těchto funkcí v bodě 0 zprava. 14.5. Věta: Věta o součtu intenzit přechodu Je-li množina stavů J konečná, pak pro intenzity přechodu platí: 0q:Ji Jj ij =∈∀ ∑∈ , kde qii = -qi. Důkaz: Vztah 0q Jj ij =∑∈ přepíšeme do tvaru i ij,Jj ij qq =∑≠∈ . Počítáme ( ) ( ) ( )[ ] iii0h ij,Jj ij0h ij,Jj ij 0h ij,Jj ij qhp1 h 1 limhp h 1 lim h hp limq =−=== +++ → ≠∈ → ≠∈ → ≠∈ ∑∑∑ . 14.6. Definice: Definice matice intenzit přechodu Matice Q = (qij)i,j J∈ , kde qii = -qi, se nazývá matice intenzit přechodu HMŘ se spojitým časem. Vysvětlení: Matice Q je charakterizována tím, že qij ≥ 0 pro i ≠ j a qii < 0 a součet prvků v každém řádku je nulový. Je to kvazistochastická matice. 14.7. Poznámka: Matici intenzit přechodu lze graficky vyjádřit pomocí přechodového diagramu. Je to ohodnocený orientovaný graf, kde a) vrcholy jsou stavy b) hrany odpovídají nenulovým intenzitám přechodu c) ohodnocení hran je rovno těmto intenzitám. Hrany, které nejsou smyčkami, mají kladné ohodnocení (qij > 0) a smyčky mají záporné ohodnocení (qii < 0). 14.8. Příklad: Doba bezporuchového provozu přístroje je náhodná veličina s rozložením Ex(α). Když dojde k poruše, přístroj začne být okamžitě opravován. Doba opravy je náhodná veličina s rozložením Ex(β). Jakmile je oprava ukončena, přístroj je okamžitě uveden do provozu. a) Modelujte tuto situaci pomocí HMŘ se spojitým časem. b) Najděte matici intenzit přechodu Q a nakreslete přechodový diagram. Řešení: Ad a) Zavedeme náhodnou veličinu    = opravěvstrojjetčasevpokud1, pracujestrojtčasevpokud,0 Xt . Stochastický proces { }Tt;Xt ∈ je HMŘ se spojitým časem s množinou stavů J = {0,1}. Ad b) Je-li Y spojitá náhodná veličina, pak její pravděpodobnostní chování je popsáno hustotou pravděpodobnosti ( )yϕ . Pro distribuční funkci ( )yΦ platí: ( ) ( )∫∞− ϕ=Φ y dtty . Dále zavedeme funkci přežití ( ) ( )yYPy >=Ψ a intenzitu ( ) ( ) ( )y y' y Ψ Ψ −=λ . V našem případě označme Y1 dobu bezporuchového provozu přístroje, Y1 ~ Ex(α), tedy ( )    >α =ϕ α− jinak0 0yproe y 1 y 11 1 , ( )    >− =Φ α− jinak0 0yproe1 y 1 y 11 1 , ( )    > =Ψ α− jinak1 0yproe y 1 y 11 1 , ( ) ( ) ( ) α= α− −= Ψ Ψ −=λ α− α− 1 1 y y 11 11 11 e e y y' y . Analogicky označme Y2 dobu opravy přístroje, Y2 ~ Ex(β). Stejným způsobem odvodíme, že ( ) β=λ 22 y . Matice intenzit přechodu: 0 1       β−β αα− = 1 0 Q . Přechodový diagram: 14.9. Věta: Věta o významu intenzit přechodu Nechť { }Tt;Xt ∈ je HMŘ se SČ, který má spočetnou množinu stavů J a matici intenzit přechodu Q = (qij)i,j J∈ . a) Nechť hs,st +∈ , kde s ≥ 0 a h > 0. Pak ( ) hq st i eiX/iXP − === , kde 0e hqi =− , je-li qi = ∞. b) Je-li qi = 0, potom pii(h) = 1. c) Je-li 0 < qi < ∞, pak veličina, která udává dobu setrvání řetězce ve stavu i, se řídí rozložením Ex(qi). Znamená to, že střední hodnota doby setrvání řetězce ve stavu i je i q 1 . Dále, pravděpodobnost toho, že první přechod ze stavu i se uskuteční právě do stavu j, j≠i, je i ij q q . 14.10. Definice: Definice různých typů stavů Nechť { }Tt;Xt ∈ je HMŘ se SČ, který má matici intenzit přechodu Q = (qij)i,j J∈ . a) Jestliže qi = 0, pak řekneme, že stav i je absorpční. (Řetězec, který vstoupí do absorpčního stavu, už v něm zůstane. Střední hodnota doby setrvání v absorpční stavu je nekonečně velká.) b) Jestliže 0 < qi < ∞, pak řekneme, že stav i je stabilní. (Budeme se zabývat výhradně řetězci se stabilními stavy) c) Jestliže qi = ∞, pak řekneme, že stav i je nestabilní. (Střední hodnota doby setrvání v nestabilním stavu je nulová.) 14.11. Definice: Definice stacionárního vektoru HMŘ se SČ Nechť { }Tt;Xt ∈ je HMŘ se SČ, který má systém matic přechodu ( ){ }Tt;t ∈P . Stochastický vektor a takový, že pro Tt∈∀ platí a = aP(t), se nazývá stacionární vektor (stacionární rozložení) daného řetězce. 14.12. Poznámka: Řešení rovnice a = aP(t) pro Tt∈∀ může být obtížné. Proto stacionární vektor počítáme raději pomocí matice intenzit přechodu. 14.13. Věta: Věta o získání stacionárního vektoru pomocí matice intenzit přechodu Nechť { }Tt;Xt ∈ je HMŘ se SČ, který má systém matic přechodu ( ){ }Tt;t ∈P a matici intenzit přechodu Q = (qij)i,j J∈ . Jestliže existuje Tt∈ tak, že matice P(t) je regulární (tj. všechny její prvky jsou kladné), pak existuje stacionární vektor daného řetězce a je dán vztahem: aQ = 0. Toto řešení je jediné. 14.14. Příklad: Pro zadání příkladu 14.8. najděte stacionární vektor. Řešení: Odvodili jsme, že       β−β αα− =Q . Hledáme a = (a0, a1), kde a0 + a1 = 1, tak, aby aQ = 0. ( ) ( ) 011010 a1a1aa,0,0a,a −=⇒=+=      β−β αα− . ( ) β+α α = β+α β =⇒=−β+α−⇒=β+α− 100010 a,a0a1a0aa . Stacionární vektor má tedy tvar:       β+α α β+α β = ,a . 14.15. Definice: Definice ergodického řetězce Homogenní markovský řetězec se spojitým časem a systémem matic přechodu ( ){ }Tt;t ∈P se nazývá ergodický, jestliže pro všechny stochastické vektory a odpovídající dimenze existuje ( )tlimt aP∞→ a tato limita na nich nezávisí. 14.16. Definice: Definice limitního rozložení a limitní matice přechodu a) Jestliže existuje ( ) pp = ∞→ tlim t , pak p se nazývá limitní rozložení (limitní vektor) daného řetězce. b) Jestliže existuje ( ) AP = ∞→ tlim t , pak A se nazývá limitní matice přechodu daného řetězce. Má-li všechny řádky stejné, nazývá se ergodická limitní matice přechodu. 14.17. Věta: Věta o souvislosti stacionárního a limitního rozložení Nechť { }Tt;Xt ∈ je HMŘ se SČ, který má stacionární rozložení a. Pak platí: a) Jeho limitní rozložení p je rovno stacionárnímu rozložení a. b) Všechny řádky limitní matice A jsou stejné a jsou rovny stacionárnímu vektoru a. 14.18. Poznámka: Při hledání stacionárního rozložení lze v MATLABu použít funkci stacionarni_vektor.m: function [a]=stacionarni_vektor(Q) %funkce pro vypocet stacionarniho vektoru %syntaxe: a=stacionarni_vektor(Q) %vstupni parametr ... kvazistochasticka matice Q %vystupni parametr ... stacionarni vektor a n=size(Q,1); A=[Q';ones(1,n)]; f=[zeros(n,1);1]; a=(A\f)'; 14.19. Příklad: Nechť HMŘ se SČ má množinu stavů { }2,1,0 a matici intenzit přechodu           − − − = 110 132 011 Q . Pomocí MATLABu najděte jeho stacionární rozložení. Řešení: Zadáme matici Q=[-1 1 0;2 -3 1;0 1 -1] Zavoláme funkci stacionarni_vektor: a=stacionarni_vektor(Q) Dostaneme výsledek: a = 0.5000 0.2500 0.2500 Znamená to, že po uplynutí dostatečně dlouhé doby polovinu doby stráví řetězec ve stavu 0, čtvrtinu doby ve stavu 1 a rovněž čtvrtinu doby ve stavu 2. 14.20. Příklad: Uvažme systém, v němž je v provozu velké množství předmětů téže funkce, např. talíře v jídelně. Předpokládáme, že předměty pocházejí od tří různých výrobců (říkáme, že jsou tří různých typů) a že doby životnosti předmětů od různých výrobců jsou stochasticky nezávislé náhodné veličiny s rozložením Ex(λi), i = 1, 2, 3. Provádíme cyklickou záměnu typů podle schématu 1 → 2 → 3 → 1. Zvolíme jedno místo v provozu a zavedeme HMŘ { }Tt;Xt ∈ se spojitým časem, kde Xt = j, když v okamžiku t je na tomto místě zařazen předmět typu j, j = 1, 2, 3. Najděte matici intenzit přechodu a stanovte stacionární rozložení. Řešení: Označme Yj dobu životnosti předmětu j-tého typu, Yj ~ Ex(λj), j = 1, 2, 3. V příkladu 14.8. bylo ukázáno, že intenzita poruchy je λj, tedy           λ−λ λλ− λλ− = 33 22 11 0 0 0 Q Stacionární rozložení získáme řešením systému rovnic : aQ = 0 s podmínkou 1a 3 1j j =∑= : 1aaa 0aa 0aa 0aa 321 3322 2211 3311 =++ =λ−λ =λ−λ =λ+λ− Řešením tohoto systému obdržíme: 323121 32 1 a λλ+λλ+λλ λλ = , 323121 31 2 a λλ+λλ+λλ λλ = , 323121 21 3 a λλ+λλ+λλ λλ = .