MARKOVOVSKÉ ŘETĚZCE Stochastické procesy Markovovské řetězce s diskrétním časem DTMC Discrete Time Markov Chain

OBSAH MARKOVOVSKÉ ŘETĚZCE ................................................................... 2 5.1 Stochastické procesy ............................................................................... 2 5.2 Markovovské řetězce s diskrétním časem DTMC – Discrete Time Markov Chain .............................................................................................................. 2 5.2.1 Definice Markovovského řetězce ................................................................ 3 5.2.2 Matice přechodu ......................................................................................... 4 5.2.3 Stabilizovaný stav systému ........................................................................ 6

5.3 Bodový proces.......................................................................................... 8 5.4 Markovovské procesy se spojitým časem CTMC – Continuous Time Markov Chain ............................................................................................... 11 5.4.1 Matice přechodu ....................................................................................... 12 5.4.2 Matice intenzit........................................................................................... 12 5.4.3 Graf diferenciálních přechodů .................................................................. 14 5.4.4 Kolmogorovovy diferenciální rovnice ........................................................ 15 5.4.5 Stabilizovaný stav ..................................................................................... 15 5.4.6 Vnořený Markovovský řetězec s diskrétním časem .................................. 16 5.4.7 Postup při analýze CTMC ......................................................................... 17

1

MARKOVOVSKÉ ŘETĚZCE V této kapitole shrneme základní definice a výsledky teorie stochastických procesů které je možné využít při analýze obecných stochastických Petriho sítí i jejich rozšíření, nejpoužívanější třídy zobecněných stochastických Petriho sítí (GSPN). Markovovské procesy se také využívají při analýze systémů hromadné obsluhy. Vyšetřování frontových systémů je v podstatě vyšetřováním stavů stochastických procesů. Pokud zákazníci vstupují v Poissonovském toku a délka obsluhy je exponenciální náhodná veličina, pak takovýto systém hromadné obsluhy je Markovovským řetězcem. Cílem není podrobný popis matematického aparátu stochastických procesů, ale spíšeje vysvětlení základním pojmů a intuitivní popis struktury Markovovských řetězců.

5.1 Stochastické procesy Zkoumáme-li jak se mění náhodná veličina v čase, mluvíme o stochastickém procesu, přesněji: Definice:Stochastickým procesem {X(t), tR} je množina náhodných veličin X(t) definovaných nad stejným pravděpodobnostním prostorem. Příkladem stochastického procesu může být intenzita provozu měřená v průběhu dne, počet studentů v posluchárně, nebo vývoj hodnot cen akcií. Klasifikace stochastických procesů je závislá na třech faktorech: stavovém prostoru, parametrickém prostoru a statistické závislosti náhodných veličin X(t) pro různé hodnoty parametru t. Definice: Stavový prostor S je množina možných hodnot X(t). Jednotlivé stavy procesu označme ei, pak S={e1,e2,...,en, …}. Stavový prostor může být spojitý, nebo diskrétní. Pro stochastický proces s diskrétním stavovým prostorem používáme termín stochastický řetězec. Parametrický prostor: množina hodnot (časového) parametru t. Stochastický proces můžeme zkoumat v průběhu spojitého časového úseku, nebo v diskrétních okamžicích.

Obr. 0.1

Příkladem stochastického procesu se spojitým stavovým prostorem je teplota měřená během dne, nebo rychlost vozidel projíždějících daným místem. Příkladem stochastického procesu s diskrétním stavovým prostorem Obr. 0.1 je počet aut před křižovatkou, počet zákazníků v obchodě, či počet žetonů v jednom místě. Procesy s diskrétním stavovým prostorem se někdy nazývají náhodné řetězce. V dalším textu se budeme zabývat jen náhodnými řetězci. V reálných aplikacích vždy můžeme spojitý stavový prostor převést na diskrétní už jenom tím, že měříme s jistou přesností.

5.2 Markovovské řetězce s diskrétním časem DTMC – Discrete Time Markov Chain Uvažujme nyní stochastický proces diskrétní v čase i v úrovni. Daný systém se v každém okamžiku nachází právě v jednom z dané množiny stavů. Bez újmy na obecnosti můžeme předpokládat, že okamžiky změn tvoří aritmetickou posloupnost 0,1, 2, 3,... . Odečítáme-li např. počet aut v tunelu každých 10 minut, bude začátek pozorování označen jako stav v nultém 2

kroku, po 10 minutách budeme mít stav 1, počet aut za 20 minut bude stav po 2 krocích atd.. Proces je popsán posloupností náhodných veličin X1, X2, ..., Xn. Nechť S={e1,e2,...,en, …} je stavový prostor, pak skutečnost, že v i-tém kroku je systém ve stavu e2 zapíšeme X i  e2 . 5.2.1 Definice Markovovského řetězce Říkáme, že řetězec je Markovovský1, jestliže pravděpodobnosti, s nimiž nastávají jednotlivé změny – přechody mezi dvěma stavy – nejsou ovlivňovány předchozí historií procesu.

P( X n  e j / X n1  ei , X n2  ein2 ,

, X 0  ei0 )  P( X n  e j / X n1  ei )  pij  n 

Pravděpodobnost pij(n) nazveme pravděpodobností přechodu ze stavu ei do stavu ej. Jinými slovy: Pravděpodobnost přechodu systému ze stavu ei do stavu ej není nijak závislá na tom, jak se systém do stavu ej dostal. Markovovské řetězce jsou velmi dobře popsány, existuje celá řada jejich vlastností, které můžeme s výhodou využívat při analýze systémů, proto se Markovovy řetězce používají všude tam, kde lze podmínku procesu „bez paměti“ přijmout, nebo alespoň přijmout částečně, za jistých omezení. V následujících úvahách se omezíme jen na homogenní Markovovy řetězce. Definice: Stochastický proces nazýváme homogenní, jestliže pro jakékoliv stavy ei, ej pravděpodobnosti přechodu pij(n) nezávisí na okamžiku n, v němž se přechod uskutečňuje, tj. pij(0) = pij(1) = pij(2) =… Argument n při zápisu pravděpodobností přechodu můžeme vynechat, protože na něm hodnota psti nezáleží. pij(n)=pij Markovovy procesy používáme v mnohých praktických aplikacích, a pokud je to jen trochu možné, přijímáme předpoklad, že je proces homogenní. Hlavním významem přijmutí předpokladu homogenity je fakt, že se analýza takovýchto systémů podstatně zjednoduší. Příklad: Sledujeme intenzitu cyklistické dopravy na daném úseku komunikace. Intenzita dopravy je vyjádřena počtem cyklistů na určitém profilu pozemní komunikace za jednotku času. Intenzita dopravy se mění spojitě v průběhu celého zkoumaného intervalu-vznikají tak variace intenzit dopravy. Používaný je denní, týdenní i roční cyklus variací intenzit dopravy. Na Obr. 0.2 je zobrazení denní variace relativních intenzit cyklistické dopravy v pracovní den. Stav systému je aktuální počet cyklistů v měřených lokalitách. Ke změně stavu dojde, když cyklista opustí monitorovací prostor, nebo naopak, když do něj přijede. Je zřejmé, že pravděpodobnosti změny stavu se během dne výrazně mění, není tedy takovýto proces možné považovat za homogenní. Abychom mohli, s jistou dávkou velkorysosti, předpoklad homogenity přijmout je zapotřebí rozdělit zkoumaný časový úsek na kratší intervaly a v nich nahradit funkci Variace intenzity za konstantní funkci. V případě cyklistické dopravy zřejmě můžeme přijmout předpoklad, že je daná intenzita konstantní v průběhu 30 minut.

1

Třídu stochastických procesů bez paměti popsal v roce 1907 ruský matematik A. A. Markov

3

Obr. 0.2: Denní variace intenzit cyklistické dopravy-průměr ze 120 stanovišť v ČR naměřený v květnu 2007

Intenzita se mění spojitě, my ji ale spojitě zkoumat nemusíme. Předpokládejme např., že intenzitu naměříme každých 5 minut. Intenzita dopravy tak může být chápána jako stochastický řetězec diskrétní v čase i v úrovni. Jednotlivé stavy v daném kroku zkoumání jsou vyjádřeny nezáporným číslem představujícím intenzitu provozu. Pokud pravděpodobnost změny stavu (příjezdu/odjezdu cyklistů) nejsou závislá na historii procesu, pak můžeme proces zkoumat jako Markovovský řetězec s diskrétním časem (DTMC). Otázkou zůstává, jak takovýto systém přehledně popsat. 5.2.2 Matice přechodu Pravděpodobnosti přechodu pij sestavíme do tzv. matice přechodu P = ( pij). Matice přechodu je čtvercová, její rozměr je rovný počtu stavů systému.

 p11 p P   pij    21    pn1

p12 p22 pn 2

p1n  p2 n    pnn 

Z podstaty hodnot pij má matice přechodu homogenního DTMC speciální strukturu: 1. všechny prvky matice jsou čísla v intervalu [0,1] 2. řádkové součty jsou rovny jedné

p

ij

1 .

j

Mluvíme o tzv. stochastických maticích. . Tyto pravděpodobnosti sestavíme do tzv. stavového vektoru rozdělení pravděpodobnosti. Stavový vektor v n-tém kroku označíme a  n    a1  n  , a2  n  ,

, an  n  ,



Vektor má tolik složek, kolik je možných stavů systému. i-tá složka vektoru představuje pst, že se systém nachází ve stavu ei. ai  n   P  X n  ei  .

4

Pokud matice přechodu poskytuje dokonalý popis procesu, pak jsme schopni jednoznačně určit pravděpodobnosti, že se systém v daném kroku nachází v daném stavu. Známe-li stavový vektor v n-tém kroku, umíme pomocí matice přechodu vypočítat stavový vektor v n+1 kroku. Ze vzorce úplné pravděpodobnosti

a j  n  1   ai  n   pij . i

Přepíšeme-li tento zápis do maticové formy dostáváme hezký rekurentní vztah

a  n  1  a  n  P Známe-li tedy počáteční rozdělení pravděpodobnosti a matici přechodu, umíme vypočítat stavové vektory rozdělení pravděpodobnosti pro všechny další kroku – můžeme vyšetřovat dynamiku procesu.

a 1  a  0   P a  2   a 1  P  a  0   P 2 a  n   a  0  Pn Důsledkem těchto vzorců a nezávislosti pravděpodobností na historii procesu i na aktuálním kroku dostáváme Chapman-Kolmogorovovu rovnost. Příklad: Sledujeme aktuální pozici studentů během dne. Výuka probíhá ve třech budovách: Florenc, Konvikt a Horská. Rozvrh studentů neznáme, migrace studentů se nám jeví jako stochastický proces. Na základě relativních četností odhadneme pravděpodobnosti přejíždění. Proces sledujeme v diskrétních časových okamžicích, vždy po dvou vyučovacích hodinách. Matice přechodu při pořadí míst „Florenc, Konvikt, Horská“ nechť má tvar:

 0, 6 0, 2 0, 2    P   0,5 0, 25 0, 25   0, 4 0, 4 0, 2    Pravděpodobnosti zakreslíme pomocí orientovaného grafu. Vrcholy grafu jsou stavy procesu – budovy, hrany grafu jsou ohodnoceny pravděpodobnostmi přechodu. Protože součet pravděpodobností všech přechodů z jednoho daného stavu je jedna, jsou řádkové součty matice přechodu 1 a ze stejného důvodu musí být u stavového grafu součet hodnot hran vycházejících z jednoho uzlu také jedna.

5

Obr. 0.3:Stavový graf Markovovského řetězce

Jestliže víme, že na začátku dne v 8:00 je student v Konviktu, známe počáteční stavový vektor rozložení pravděpodobnosti. S jistotou víme, že na začátku je systém(student) ve stavu „Konvikt“. Při daném pořadí míst „Florenc, Konvikt, Horská“ je a  0   (0,1,0) . Pravděpodobnosti, pozice studenta o příští přednášce,tj v dalším kroku je dána a 1  a  0 P   0,5; 0, 25;0, 25 . Z rovnice a  n   a  0  P n můžeme vypočítat stavový vektor pro obecný n-tý krok. Výpočet n-té mocniny matice je možný provést různými způsoby, např. pokud má matice jednoduchou strukturu můžeme využít diagonální matici. Chapman-Kolmogorovova rovnost Označme pij(2) pravděpodobnost, že systém, který byl v určitém okamžiku ve stavu ei bude po 2 přechodech ve stavu ej (Nezávisle na tom, jakým mezikrokem systém prošel). Potom pij(2)   pik pkj , tj. P 2  P2 . Obecněji pij( n )   pik ( n1) pkj  pik ( m ) pkj ( n m ) , tedy můžeme psát k

P

 n m

k

k

 P P . n

m

5.2.3 Stabilizovaný stav systému Rozložení pravděpodobností stavů systému se může po delší době ustálit, tj. všechny složky stavového vektoru mohou konvergovat lim ak  n   ak . n



a  lim a (n)  lim a1 (n), lim a2 (n), n

n

n

, lim ak ( n), n



Dynamika systému je závislá na konstantní matici přechodu a na počátečním stavu, tedy obecně i limitní chování může být na počátečním stavu závislé lim a (n)  a (0)  lim P n n

n

Pokud tomu tak není a limitní rozdělení stavového vektoru jsou identická pro všechny počáteční stavy, pak mluvíme o stabilizovaném systému. Definice: Pokud je limitní rozložení lim a (n)  a (0)  lim P n nezávislé na počátečním rozložení n

n

a  0  , pak říkáme, že je systém stabilizován.

Zamysleme se nyní nad tím, jak určit, zda je systém stabilizován. Je zřejmé, že nutnou podmínkou stabilizace systému je, aby pro n   konvergovaly pravděpodobnosti pik(n).

6

lim ak (n)   ai (0)  lim pik( n ) n

n

i

Pokud budou pro všechna i lim pik( n ) identické, pak je můžeme vytknout před sumu a využitím n

vlastnosti vektoru rozdělení psti

 a (0)  1 ,dostáváme i

i

lim ak (n)   ai (0)  lim pik( n )   ai (0)  ak  ak . n

n

i

i

Tedy, pokud jsou prvky ve sloupcích matice lim P n identické, systém je stabilizovaný. Právě dokázaná věta nemá při řešení praktických příkladů příliš velký význam, protože je většinou velmi obtížné určit obecnou mocninu matice P n .Uvědomme si, že matice P má rozměr rovný počtu stavů, přitom je většinou velmi řídká – má velké množství nul. V teorii Markovovských procesů existuje celá řada nutných či postačujících podmínek pro stabilizaci systému, založených na klasifikaci stavů, tato teorie ale překračuje rámec skript a nebudeme ji zde rozepisovat. Pokud máme zjištěno, že je systém stabilizovaný, pak můžeme vypočítat stabilizovaný stav a přímo, řešením homogenní soustavy lineárních rovnic

a  aP Rovnice vyplývá přímo ze vztahu a  n  1  a  n  P . Za předpokladu že je systém stabilizovaný,můžeme psát lim a  n  1  lim a  n   a . n

n

Příklad: Vraťme se k příkladu stěhování studentů Fakulty dopravní. Matice přechodu byla zadána ve tvaru.

 0, 6 0, 2 0, 2    P   0,5 0, 25 0, 25   0, 4 0, 4 0, 2    Platí, že pokud je stavový graf procesu s konečnou množinou stavů silně souvislý, pak je systém stabilizovaný. Vypočítejme vektor rozložení pravděpodobnosti stavu. Rovnici a  a  P můžeme přepsat do tvaru  I  PT  a  o , kde I je jednotková matice. Dále postupujeme Gaussovou eliminací. Hodnost matice soustavy

I  P  T

je dva, řešení je jednoparametrický systém

aR  t   25,12,10  , t  R . Vektor rozložení pravděpodobnosti má součet všech složek roven jedné, tedy výsledný stabilizovaný stav má pravděpodobnosti

 25 12 10  a  , ,   47 47 47  V našem konkrétním příkladě je výpočet stabilizovaného řešení nesmyslný, protože prakticky tento stochastický proces trvá jen několik kroků, délka zkoumané posloupnosti stěhování je omezena koncem vyučování v 20:00. Za tak krátkou dobu se proces zřejmě nestačí stabilizovat. Existuje ale celá řada aplikací, pro které je výpočet stabilizovaného stavu podstatný a v mnohém případě i postačující pro další analýzu. Klasickým příkladem jsou dopravní systémy či komunikační protokoly. Obecně jsou to všechny aplikace, kde pracujeme s vzájemně nezávislými entitami a nezajímá nás dynamika procesu.

7

Prozatím jsme zkoumali Markovovské řetězce v diskrétních časových okamžicích, tzv. krocích. Abychom mohli stochastický proces X(t) zkoumat jako množinu se spojitým parametrickým prostorem tR musíme uvažovat posloupnost změn stavu jako bodový proces. Proto, dříve než přistoupíme ke studiu stochastického řetězce se spojitým časem vysvětlíme základní metody analýzy bodového procesu.

5.3 Bodový proces Představme si posloupnost nějakých událostí, které nastávají náhodně v čase. Příkladem mohou být příjezdy vozidel k celnici, příchody cestujících do stanice metra, nebo porucha nějakého zařízení, která vyžaduje opravu. Zápis procesu Okamžiky změny stavu stochastického procesu (v našem případě okamžiky vstupu zákazníků do systému) můžeme zapsat různými způsoby Obr. 0.4. 1. posloupnost časových okamžiků t1, t2, ..., tn 2. posloupnost intervalů 1, 2, ..., n 3. počet událostí během časového intervalu [s, s+t] - funkce N(s,t)

Obr. 0.4

Tyto zápisy jsou vzájemně ekvivalentními a podle potřeby zvolíme, který je pro nás v danou chvíli nejvýhodnější. Některé vlastnosti a definice je možné přehledněji zapsat v jednom zápise, pro jiné je výhodnější volit jiný typ zápisu. Přechod mezi jednotlivými zápisy je triviální:

 k  tk 1  tk ; k  0,1, 2, n 1

tn   k ; n  1, 2, k 0

N ( s, t )  n  tn  s  t  tn 1 Pro každé k je k – délka intervalu mezi k-tou a k+1 událostí spojitá náhodná veličina, její distribuční funkci označme Ak (t ) . Dle definice Ak (t )  P{ k  t}, k  0,1, 2,

Funkce N(s,t) je po částech konstantní funkce, body nespojitosti jsou okamžiky příchodu t1, t2, ..., tn. Pro pevné s,t je počet událostí N(s,t) diskrétní náhodná veličina. Označme její pravděpodobnostní funkci vn  s, t   P N  s, t   n, n  0,1,

t  0; s  0,



 v ( s, t )  1 n 0

n

Střední počet událostí v časovém intervalu [s, s+t] pak vypočítáme z definice střední hodnoty 

E[ N ( s, t )]   n  vn ( s, t ) n 0

8

Jednotlivé požadavky se mohou vzájemně ovlivňovat, proces se může dynamicky měnit, intervaly mezi jednotlivými událostmi mohou mít dokonce i jiné rozdělení. Je tedy účelné rozlišovat mezi jednotlivými typy procesů. Uveďme si zde definice jen několik základních typů Proces s nezávislými přírůstky pro libovolnou k-tici vzájemně disjunktních intervalů [s1, s1+t1]; [s2, s2+t2]; ...; [sk, sk+tk]; … je {N(s1, s1+t1), N(s2, s2+t2), ... , N(sk, sk+tk); ...} posloupnost nezávislých náhodných veličin. Regenerativní proces (proces obnovy)

 n  je posloupnost nezávislých náhodných veličin. Rekurentní proces

 n  je

posloupnost pravděpodobnosti.

nezávislých

náhodných

veličin

se

stejným

rozdělením

Homogenní proces pravděpodobnosti, že během intervalu [s, s+t] nastane n událostí jsou závislé pouze na délce intervalu t a ne na jeho vn ( s, t )  P( N ( s, t )  n); n  0,1, 2 počátku s, tedy N(s,t) má pro libovolné s vždy stejný zákon rozložení jako N(0, t). E[ N (t  u)]  E[ N (t )]  E[ N (u)]  E[ N (t )]  t  E[ N (1)]  t  

a pro homogenní procesy má smysl definovat intenzitu procesu Definice: Intenzitou homogenního procesu nazveme střední počet událostí za časovou jednotku E[ N (1)]   .

Ordinární proces ve velmi krátkém časovém okamžiku nastane více než jedna událost jen se zanedbatelnou pravděpodobností, řádově menší než je délka tohoto intervalu. Nedochází ke kumulování událostí.

1  v0  t   v1  t  0 t 0 t

lim

Při praktických aplikacích většinou pojmy procesu s nezávislými přírůstky a regenerativního procesu splývají, obecně ale mezi nimi je rozdíl. Tak například průjezdy motorových vozidel určitým místem tvoří proces s nezávislými přírůstky, protože řidiči se rozhodují většinou vzájemně nezávisle, zda daným místem pojedou, ale už tento tok nebývá regenerativní, protože se auta, která jedou za sebou vzájemně ovlivňují. Pokud je ale proces ordinální, pak proces s nezávislými přírůstky je současně regenerativní. Pro ordinární homogenní proces podmínky regenerativnosti a rekurence splývají. Poissonovský tok ordinární homogenní proces s nezávislými přírůstky Pro ordinární beznásledný homogenní vstupní tok událostí pravděpodobnost, že za časový interval délky t nastane právě k událostí, je

P ( N ( s , t )  k )  vk ( s , t ) 

  t  k!

k

 e  t

Poissonův tok je až na konstantu  jednoznačně určen. Z definice střední hodnoty 9

ukážeme, že parametr  je intenzitou procesu 

E[ N (t )]   ke

 t

t  k!

k 0

k

e

 t

 t  t   t   e  t  t    t k! k 0  k  1 ! k 0 

k 1

k

Poissonovský tok patří mezi nejdůležitější toky, je ze všech stochastických procesů nejjednodušší, protože pro jeho matematický popis můžeme použít aparát Markovovských procesů. Intervaly mezi událostmi Poissonovského toku jsou vzájemně nezávislé veličiny s exponenciálním rozdělením. Dosazením do předchozího vztahu dostaneme distribuční funkci exponenciálního rozdělení.

A  t   P(  t )  1  v0  s, t   1  e t Tedy pro hustotu pravděpodobnosti náhodné veličiny představující délku intervalu mezi vstupy a(t )  A(t )    et .

Obr. 0.5:Hustota pravděpodobnosti délky intervalu mezi událostmi

Z grafu exponenciální náhodné veličiny Obr. 0.5 je zřejmé, že pravděpodobnost krátkých intervalů mezi událostmi je větší než psti delších časových rozestupů. V elementárním toku se nejčastěji vyskytují krátké intervaly mezi událostmi, tj změny stavů se realizují v sériích krátkých sledů Obr. 0.6. To je vlastnost všeobecně známá např. ze rčení „Do třetice všeho dobrého a zlého“, které používáme pro vyjádření toho, že na sobě navzájem nezávislé události, které se nestávají příliš často přicházejí ve shlucích oddělených delším časovým rozestupem.

Obr. 0.6:Zobrazení posloupnosti okamžiků událostí v Poissonosvském procesu – události se stávají ve shlucích

Díky vlastnosti exponenciální náhodné veličiny je Poissonovský tok Markovovský proces ryzího množení. Exponenciální náhodná veličina je jediná spojitá náhodná veličina bez paměti, tj. pravděpodobnosti změny stavu jsou nezávislé na historii procesu. Přesněji, pravděpodobnost, že v elementárním toku nenastane v intervalu délky T žádná událost, víme-li že od vstupu předešlého požadavku už uplynul čas t
P(  t  u /   t ) 

  t u P(  t  u ) v0  t  u  e   = =  t = e  u = P(  u) P(  t ) v0  t  e

10

Pro Poissonovský tok platí vlastnosti, která nám při analýze systémů výrazně usnadňují výpočty. Při analýze stochastických Petriho sítí využíváme vlastností superpozice a náhodného výběru. 1. Superpozice: Složením dvou Poissonovských procesů o intenzitách 1 a 2 vznikne opět Poissonův proces s intenzitou =1+2 (Obr. 0.7). 2. Náhodný výběr: Vybíráme-li s pstí p z daného Poissonovského procesu s intenzitou , pak výsledný proces je Poissonovský s intenzitou p.

Obr. 0.7: Složením dvou Poissonovských procesů je Poissonův proces s intenzitou rovnou součtu intenzit vstupujících Poissonovských procesů.

5.4 Markovovské procesy se spojitým časem CTMC – Continuous Time Markov Chain Nyní spojíme znalosti získané z předchozích dvou kapitol. Většinu základních pojmů CTMC získáme analogií z diskrétního časového prostoru. Budeme nyní zkoumat stochastický řetězec s diskrétním stavovým prostorem a spojitým časem. Příkladem může být sledování počtu aut v jistém úseku komunikace. Definice: Proces je Markovovský (CTMC), jestliže znalost několika minulých hodnot funkce X nepřináší o rozložení pravděpodobnosti její současné hodnoty X(t) více informace nežli znalost jediné – té poslední z nich. P( X (t )  ei / X (tn )  en , X (tn1 )  en1 ,

, X (t0 )  e0 )  P( X (t )  ei / X (tn )  en )

Označme pij ( s, t )  P( X ( s  t )  e j / X ( s)  ei ) pravděpodobnosti přechodu. Stejně jakou diskrétních Markovovských řetězců budeme se nadále zabývat jen homogenními procesy. Daný proces je homogenní, jsou-li pravděpodobnosti pij(s,t) závislé pouze na délce časového úseku t, nikoliv na jeho počátku s. Budeme nadále považovat psti přechodu jen za funkce času t a budeme zapisovat pij(t) Zvolme pevně jeden stav systému. Nechť se systém v tomto stavu právě teď nachází. Označme  spojitou náhodnou veličinu doby setrvání stavu v systému. Pravděpodobnost změny systému v příštím, krátkém časovém úseku t musí být z definice Markovovského procesu nezávislá na historii procesu, tj  musí být exponenciální náhodná veličina. Uvažujeme-li jen dvě možnosti, buď systém ve stavu setrvá, nebo jej opustí, pak dostáváme analogii DTMC a CTMC Obr. 0.8.

11

Obr. 0.8

Pst. setrvání systému ve stavu

P   t   1  et    t  o  t 

Pst., že během intervalu t systém stav opustí

P   t   et  1    t  o  t 

5.4.1 Matice přechodu Všechny funkce přechodu ze stavu ei do stavu ej sestavíme do matice časových funkcí P(t)=(pij(t)). Matice přechodu má speciální strukturu. 1. obor hodnot funkcí přechodu je interval [0,1] 2. řádkové součty jsou rovny jedné

 p  t  1 . ij

j

3. diagonální funkce jsou klesající, nediagonální funkce jsou rostoucí 4. P  0   E Příklad grafů prvků matice přechodu je na (Obr. 0.9). Uvědomme si, že prvky matice přechodu pij(t) nejsou určeny jen délkou intervalu přechodu ze stavu ei do stavu ej. Situace je poněkud složitější, protože za čas t může systém projít mnoha změnami. Prvky matice přechody je třeba chápat v následujícím smyslu. Nechť je v čase t0 systém ve stavu ei. Pak pravděpodobnost, že v čase t0+t je systém ve stavu ej je dána pravděpodobností pij(t). Naše úvahy jsou omezeny jen na homogenní procesy, kdy se chování systému v průběhu intervalu zkoumání neměnní, tedy pravděpodobnosti přechodu nejsou závislé na počátku pozorování t0 a proto argument t0 a při zápisu pij(t). nepoužíváme. Pro popis Markovovských řetězců s diskrétním časem se využívá matice přechodu, která je stochastickou konstantní maticí. Pro daný okamžik t je matice přechodu také stochastickou maticí, ale zadání řetězce se spojitým časem pomocí matice, jejíž prvky jsou funkce času je prakticky nerealizovatelné. Stěží si představíme statistický průzkum v terénu, jehož výstupem bude takováto matice. Proto pro zadávání systému využíváme jiných charakteristik, které je možné odhadnout na základě reálných dat získaných ze statistického průzkumu. Zavádíme intenzity přechodu mezi stavy a intenzity výstupu ze stavu. Matice intenzit sestavená z těchto hodnot bude používána podobně, jako matice přechodu pro procesy s diskrétním časem.. 5.4.2 Matice intenzit Matice přechodu pro diskrétní čas je tvořena pravděpodobnostmi přechodu v jednom kroku, podobně matice intenzit bude tvořena infinitezimálními intenzitami pro nekonečně krátký interval t 12

Intenzity přechodu ze stavu ei do stavu ej. i  j .

qij  lim

Intenzity výstupu ze stavu ei

qii  lim

pij ( t ) t

t 0

t 0

pii  t   1 t

Q = (qij) – matice intenzit (infinitesimální generátor) Pro homogenní procesy intenzity přechodu nezávisí na délce intervalu, ale jen na čase pozorování, vyjadřují počet přechodů za časovou jednotku, proto je matice intenzit homogenních procesů konstantní. Zkoumáme li chování procesu lokálně, rozlišujeme pro jeden aktuální stav jen dvě možnosti. Buď systém ve stavu zůstane, nebo jej opustí. Doba setrvání homogenního Markovova procesu X(t) ve stavu ei má exponenciální rozdělení s parametrem - . Parametr exponenciálního rozdělení je až na znaménko rovna intenzitě výstupu.

qii  lim

t 0

pii  t   1 e t  1   e t  lim  lim   t 0 t 0 t t 1

Věta: Vztah mezi maticí intenzit a přechodu popisují následující vzorce: 1.

dP t  0  Q dt Důkaz:

pij (t )  lim

t 0

pij (0)  lim

pij  t  t   pij  t  t pij  t   pij  0  t

t 0

 lim

t 0

pij  t  t

pij (0)  qij

Analogicky bychom dokázali, že pii (0)  qii . Právě dokázaná vlastnost říká, že matice intenzit je sestavena se směrnic tečen grafu funkcí pij(t) v bodě t=0. 2. P Qt+E , Řádkové součty matice intenzit jsou 0. Nediagonální prvky jsou kladné, prvek na diagonále je záporný Důkaz: nejprve pro nediagonální prvky

lim

pij ( t )

t 0

t



tqij t

 0 tj pij ( t )  tqij  o( t )

pij ( t )  tqij  o( t ) pro diagonální prvky 1  pii  t    pij  t    qij t  o  t  j i

j i

p  t   1 qii  lim ii  lim t 0 t 0 t Z předchozích dvou vztahů

13

 qij t  o  t  i j

t

  qij i j

pii (t )  1  tqii  o(t )

Matice intenzit může být jakákoliv čtvercová matice, jejíž všechny nediagonální prvky jsou nezáporné a řádkové součty jsou 0. Pro homogenní proces je matice intenzit konstantní. Lineární aproximací P Qt+E prakticky zdiskretizujeme CTMC, změnu stavů zkoumáme jen pro dostatečně malé intervaly t Příklad: CTMC je dán maticí přechodu

 1 e 2 t 2  2 P t    2 t 1 e   2 2

1 e 2 t  2 2 1 e 2 t  2 2

     

Grafy funkcí pravděpodobností přechodu jsou znázorněny na Obr. 0.9. Řádkový součet musí dávat konstantní funkci 1, obory hodnot všech funkcí v matici přechodu musí být [0, 1].

 1 1  dP t  0 = Q    . Matice intenzit dt  1 1 je sestavena se směrnic tečen grafu funkcí pij(t) v bodě t=0. Z matice přechodu určíme matici intenzit Q 

Obr. 0.9-Grafy pravděpodobností přechodu

1 2 Systém je stabilizovaný lim P  t    t  1  2

1 1 2 a  1 2  2

1 . 2

5.4.3 Graf diferenciálních přechodů Podobně, jako jsme graficky znázornily vztahy mezi stavy Markovovského řetězce s diskrétním časem pomocí stavového grafu, používáme pro řetězec se spojitým časem graf diferenciálních přechodů. Uzlu představují stavy procesu, pokud existuje nenulová intenzita přechodu qij, pak vede orientovaná hrana ze stavu ei do stavu ej. Hranu ohodnotíme intenzitou 14

přechodu. Pro pořádek můžeme všem vrcholům dodat smyčky ohodnocené intenzitou výstupu. Intenzita výstupu je jednoznačně určena intenzitami přechodu

qii   qij , i j

tedy součet všech hran vycházejících z daného uzlu musí být nula. Graf diferenciálních přechodů z předcházejícího příkladu je na Obr. 0.10. Systém má dva stavu, označme je „O“ a „1“. Obě intenzity přechodu jsou jedna.

Obr. 0.10: Graf diferenciálních přechodů dvoustavového procesu

5.4.4 Kolmogorovovy diferenciální rovnice Struktura matice přechodu je pro řetězce se spojitým časem komplikovaná, v praxi postupujeme obráceně, nejprve empiricky určíme intenzity přechodu qij jako odhad středního počtu změny ei  e j za časovou jednotku, poté dopočítáme intenzity výstupu z podmínky  qij  0 . j

Pokud známe matici intenzit Q můžeme určit matici přechodu ze systému přímých (zpětných ) Kolmogorovýh rovnic.

P(t )  P(t )  Q , P  0   E Soustava lineárních diferenciálních rovnic s konstantními koeficienty má řešení ve tvaru P(t )  P(0)  eQt . P(t) je určena až na násobek konstantní maticí P  t   V  t   C . Konstantní matici C vypočítáme z podmínky P  0   E . Platí: P  0  V  0   C  C  V 1  0  . Shrňme: Nechť Q je matice intenzit, pak matice přechodu CTMC je ve tvaru

P  t   V  t   V 1  0  , V  t    e1t  v 1 ; e2t  v 2 ; kde  1 , 2 , , n  jsou vlastní čísla matice Q a  v1 , v2 , vlastním číslům, psané do sloupce.

; e1t  v n  , , vn  jsou vlastní vektory k příslušným

5.4.5 Stabilizovaný stav Pravděpodobnosti stavů e1,e2,e3,…sestavíme do stavového vektoru

a (t )  (a1 (t ), a2 (t ),

, ak (t ), ); ai  t   P  X  t   ei 

Podobně jako u Markovovských řetězců s diskrétním časem, stavový vektor vypočítáme z počátečního rozdělení a s matice přechodu

a (t )  a (0)  P(t )

15

(0.1)

Konvergují li složky stavového vektoru nezávisle na počátečním rozložení a j  lim a j (t ) , pak t 

říkáme, že je systém stabilizovaný. Podobně jako u DTMC je možné rozhodnout o stabilizaci systému ze struktury matice lim P  t  . Jsou li limitní pravděpodobnosti nezávislé na indexu i, t 

pak můžeme psát.

a j  lim a j (t )  lim  ai (0) pij (t )  lim pij (t ) t 

t 

t 

i

V praxi je výpočet matice P(t) komplikovaný a většinou i nemožný, o stabilizaci systému rozhodneme jinými metodami, např. pomocí klasifikace stavů vnořeného DTMC a metodami teorie grafů. Věta: Stabilizovaný vektor rozdělení pravděpodobností stabilizovaného Markovovského řetězce se spojitým časem vypočítáme ze soustavy homogenních lineárních rovnic.

a Q  o Důkaz:

Derivací

(1.1)

získáme

(0.2)

rovnici

a  t   a  0   P  t  .

Dosadíme

vztah

z Kolmogorovových rovnic a  t   a  0   P  t   Q . Limitním přechodem dostáváme

lim a  t   lim a  t   Q t 

t 

Protože předpokládáme, že proces je stabilizovaný lim a  t   a , musí pro všechny složky t 

vektoru a (t ) existovat horizontální asymptota lim a  t   0 . Dosazením limit dostáváme přímo t 

dokazovaný vztah. 0  a  Q . 5.4.6 Vnořený Markovovský řetězec s diskrétním časem Markovovský řetězec se spojitým časem můžeme převést na proces s diskrétním časem (DTMC) a metody analýzy DTMC využijeme pro zkoumání vlastností řetězce se spojitým časem CTMC. Některé z výrazných vlastnost, jako např. stabilitu mají tyto dva procesy společné. Přechod ke vnořenému řetězci s diskrétním časem realizujeme tak, že neuvažujeme čas strávený v nějakým stavu a registrujeme jen přechody. Matice přechodu vnořeného DTMC:

S   sij  ; sij 

qij

q i j

sij  0

pro i  j

ij

pro i  j

S  E  QD  Q , QD je matice tvořená intenzitami výstupu – diagonálními prvky matice 1

intenzit. QD  diag Q 

CTMC je ireducibilní právě tehdy, je-li ireducibilní vnořený DTMC. Je-li ã stabilizovaný stav vnořeného DTMC, pak je stabilizovaný i původní CTMC a pro jeho stabilizovaný stav platí:

16

a

a  QD 

1

a  QD 

1

5.4.7 Postup při analýze CTMC Pokud stojíme před úkolem analyzovat reálný stochastický proces, je vždy příjemné, pokud zkoumaný proces je Markovovský. Abychom aparát markovovských řetězců mohli použít, musíme nejprve verifikovat metodami matematické statistiky, že se skutečně jedná o Markovovský řetězec. Pokud se naše hypotézy potvrdí, resp. nevyvrátí na základě naměřeného souboru dat,můžeme odhadnout intenzity přechodu a na základě nich vypočítat požadované charakteristiky. Postup můžeme shrnout do následujících kroků. 1. Sestrojení grafu diferenciálních přechodů na základě dané formulace problému 2. Sestavení matice pravděpodobnosti přechodů, resp. matice intenzity přechodů (Sestavení soustavy diferenciálních rovnic na základě matice intenzit a její vyřešení) 3. Nalezení stacionárního řešení 4. Výpočet požadovaných charakteristik Příklad: Sledujeme stav datového projektoru. Označme T1 náhodnou veličinu představující délku setrvání projektoru v bezvadném stavu. Za časovou jednotku zvolíme měsíc. Pst, že je přístroj po uplynutí času t[měsíc] od poslední opravy stále v bezvadném stavu P(T1>t) = e-2t. Označme T2 náhodnou veličinu představující délku setrvání projektoru v bezvadném stavu. Je-li přístroj pokažený, pak pst, že za čas t nedošlo k opravě P(T2>t)=e-20t. Určete stabilizovaný stav. Řešení: Proces má dva stavy: „OK“-přístroj je v pořádku a „KO“ – přístroj potřebuje opravu. Protože délky setrvání systému v obou stavech jsou náhodné veličiny s exponenciálním rozdělením, je popsaný proces Markovovský. Parametry exponenciálního rozdělení jsou intenzitami výstupu. Při pořadí stavů , např. „přístroj je v pořádku, přístroj potřebuje opravu“.

 2 2  Q   20 20 

Obr. 0.11- Graf diferenciálních přechodů pro stav projektoru

Systém má konečnou množinu stavů, graf diferenciálních přechodů je silně souvislý, tedy, podobně jako pro DTMC, platí, že systém je stabilizovaný. Stabilizovaný vektor získáme řešením rovnice (1.2). Matice Q má hodnost 1, řešením je jednoparametrický systém  10 1  a   a1 , a2  ; 2a1  20a2  0 . Normalizační podmínku a1+a2=1 splňuje vektor a   ;  .  11 11  Výsledek nám říká, že po nějakém čase, když už je systém ustálený, je pravděpodobnost, že je 10 přístroj v pořádku rovna a1  , pravděpodobnost, že datový přístroj potřebuje opravu je 11 1 a2  . 11

17