Dodatek: Základní poznatky o markovských řetězcích se spojitým časem 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) ( ) ( )1ntnt0t2nt1ntntn10n10 jX/jXPjXjXjX/jXP:Jj,,j,jTttt 1nn02n1nn −−− ====∧∧=∧==∈∀∈<<<∀ −−− KKK 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). 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í. 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,h ∈P . Je zvykem definovat P(0) = I. Vlastnosti HMŘ se SČ (CH-K rovnice a zákon evoluce) 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) Definice matice intenzit přechodu 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 0hij +→ = - intenzita přechodu ze stavu i do stavu j b) Ji∈∀ : ( ) h hp1 limq ii 0h i − = +→ - intenzita výstupu ze stavu i. 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. 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). 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. Výpočet 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é. Kolmogorovovy systémy a systém evolučních diferenciálních rovnic Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem, který má systém matic přechodu ( ){ }Tt;t ∈P , systém vektorů absolutních pravděpodobností ( ){ }Tt;t ∈p , vektor počátečních pravděpodobností p(0) a matici intenzit přechodu Q. Pak platí: a) ( ) ( )QPP tt' = s počáteční podmínkou P(0) = I (Kolmogorovův systém prospektivních diferenciálních rovnic) b) ( ) ( )tt' QPP = s počáteční podmínkou P(0) = I (Kolmogorovův systém retrospektivních diferenciálních rovnic) c) ( ) ( )Qpp tt' = s počáteční podmínkou p(0) = daný stochastický vektor (systém evolučních diferenciálních rovnic). Definice Poissonova procesu Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem, který má množinu stavů J = {0, 1, 2, …}, vektor počátečních pravděpodobností p(0) = (1, 0, …) a matici intenzit přechodu             λλ− λλ− λλ− = KKKKK K K K 00 00 00 Q , kde 0>λ je konstanta, nazývá se intenzita. Přechodový diagram: Tento HMŘ se nazývá Poissonův proces (s parametrem λ). (Vidíme, že v Poissonově procesu je možné jen setrvání v dosavadním stavu nebo přechod do nejbližšího vyššího stavu.) Pravděpodobnostní rozložení složek Poissonova procesu Nechť { }Tt;Xt ∈ je Poissonův proces s parametrem λ. Pak platí: ( ) ( ) t j j e !j t tp:JjTt λ−λ =∈∀∈∀ . Vysvětlení: Náhodná veličina Xt, která udává např. počet zákazníků, kteří přijdou do fronty v intervalu ( t,0 , se řídí rozložením Po(λt). Střední hodnota počtu událostí, které nastanou v intervalu ( t,0 , je rovna číslu λt, tedy konstanta λ představuje střední hodnotu počtu událostí, které nastanou za jednotkový časový interval. Proto se λ nazývá intenzita procesu. Čísla pj(t) udávají pravděpodobnosti, že v intervalu ( t,0 nastalo právě j událostí. Číslo p0(t) = e-λt udává pravděpodobnost, že v intervalu ( t,0 nenastala žádná událost. Označíme-li S dobu čekání na změnu mezi stavy (tj. dobu čekání na příchod události resp. dobu setrvání ve stavu), pak P(S > t) = e-λt , tedy ( )    < ≥− =≤ λ− 0t,0 0t,e1 tSP t . To znamená, že je-li rozložení počtu událostí, které nastaly v intervalu ( t,0 Poissonovo, je rozložení doby čekání na změnu resp. doby setrvání ve stavu exponenciální. Pravděpodobnosti přechodu v Poissonově procesu Nechť { }Tt;Xt ∈ je Poissonův proces s parametrem λ. Pak platí: ( ) ( ) ( )      < ≥ − λ =∈∀∈∀ λ− − ijpro0 ijproe !ij t tp:Jji,Tt t ij ij . Bodový a intervalový odhad parametru λ Poissonova procesu Nechť v intervalu T,0 byl sledován Poissonův proces s neznámým parametrem λ a bylo pozorováno n událostí. a) Bodový odhad parametru λ je dán vzorcem: T nˆ =λ , přičemž ( ) λ=λˆE (tj. λˆ je nestranný odhad) a ( ) T ˆD λ =λ . b) 100(1-α)% interval spolehlivosti pro λ má meze: ( )n2 T2 1 d 2/ 2 αχ= , ( )2n2 T2 1 h 2/1 2 +χ= α− . Definice procesu vzniku a zániku Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem, který má množinu stavů J = {0, 1, 2, …}, vektor počátečních pravděpodobností p(0) = (1, 0, …) a matici intenzit přechodu ( ) ( )             λλ+µ−µ λλ+µ−µ λλ− = KKKKK K K K 2222 1111 00 0 0 00 Q , kde K0,1,2,j,0j =>λ a K1,2,j,0j =>µ jsou konstanty. Tento řetězec se nazývá proces vzniku a zániku (resp. množení a úmrtí). Přechodový diagram: Upozornění: Je zřejmé, že Poissonův proces je speciálním případem procesu vzniku a zániku, v němž µj = 0, j = 1, 2, … a λj = λ, j = 0, 1, 2, … Vysvětlení: Proces vzniku a zániku modeluje kolísání rozsahu souboru objektů v čase za předpokladu, že a) v náhodných okamžicích vstupují do tohoto souboru nové objekty, přičemž pravděpodobnost, že v intervalu ( ht,t + vstoupí do souboru rozsahu j nový objekt, je ( )hohj +λ , kde λj > 0 je intenzita vstupu do stavu j; b) v náhodných okamžicích vystupují z tohoto souboru jiné objekty, přičemž pravděpodobnost, že v intervalu ( ht,t + vystoupí ze souboru rozsahu j jeden objekt, je ( )hohj +µ , kde µj > 0 je intenzita výstupu ze stavu j; c) vstupy a výstupy objektů jsou stochasticky nezávislé jevy; d) během krátkého časového intervalu zůstává rozsah souboru týž nebo se jedničku zvětší či zmenší.