6. Odhady absolutních pravděpodobností a pravděpodobností přechodu v HMŘ 6.1. Poznámka: Předpokládejme, že HMŘ { }0n Nn;X ∈ s konečným počtem stavů k má vektor počátečních pravděpodobností p(0) = (p1(0), p2(0), …, pk(0)) a matici přechodu           = kk1k k111 pp pp L LLL L P . Tyto pravděpodobnosti však neznáme, můžeme je pouze odhadnout na základě dlouhodobého pozorování systému. Podívejme se nejprve na odhad pravděpodobností přechodu. Pro i,j = 1, …, k označme: cij … počet pozorování přechodu systému ze stavu i do stavu j ∑= = k 1j iji cc … celkový počet přechodů, které začínaly ve stavu i (je-li i absorpční stav, ci = 0) Bodové odhady pravděpodobností přechodu získáme takto:      = ≠ = 0proc0 0proc c c pˆ i i i ij ij . Je-li splněna podmínka ( ) 5cpˆ1pˆ iijij ≥− (tzv. podmínka dobré aproximace), můžeme spočítat též 100(1-α)% asymptotický interval spolehlivosti pro pij. Jeho meze jsou: ( ) 21 i ijij ij u c pˆ1pˆ pˆ α− − ± . Odhad počátečních pravděpodobností lze získat na základě náhodného výběru. Nechť d je rozsah náhodného výběru a di je počet těch složek náhodného výběru, které se na počátku pozorování nacházely ve stavu i, i = 1, 2, …, k. Přitom ∑= = k 1i idd . Bodový odhad pi(0): ( ) k,,2,1i, d d 0pˆ i i K== . Za splnění podmínky ( ) ( )[ ] 5d0pˆ10pˆ ii ≥− lze sestrojit 100(1-α)% asymptotický interval spolehlivosti pro pi(0). Jeho meze jsou: ( ) ( ) ( )[ ] 21 ii i u d 0pˆ10pˆ 0pˆ α− − ± . 6.2. Příklad: V jistém regionu bylo náhodně vybráno 2501 domácností. Bylo zjištěno, že k určitému datu 629 domácností nepředplácelo žádný deník, 750 předplácelo regionální deník a zbytek celostátní deník. Z těch domácností, které neměly žádné předplatné, hodlá v příštím měsíci 126 předplácet regionální a 63 celostátní deník.Z domácností, které předplácejí regionální deník, u něj v příštím měsíci zůstane 525 domácností a 75 začne předplácet celostátní deník. A nakonec z těch domácností, které předplácejí celostátní deník, 673 nezmění předplatné a 112 přejde na předplatné regionálního deníku. Modelujte situaci pomocí homogenního markovského řetězce a najděte bodové a intervalové odhady (se spolehlivostí 95 %) počátečních pravděpodobností a pravděpodobností přechodu. Řešení: Zavedeme homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {1, 2, 3}, kde Xn = 1, když v n-tém měsíci náhodně vybraná domácnost nemá žádné předplatné, Xn = 2, když má předplatné na regionální deník a Xn = 3, když má předplatné na celostátní deník. Údaje obsažené v textu úlohy uspořádáme do tabulky: 1 2 3 Σ 1 440 126 63 629 2 150 525 75 750 3 337 112 673 1122 Σ 2501 Nejprve odhadneme počáteční pravděpodobnosti podle vzorce ( ) k,,2,1i, d d 0pˆ i i K== . V našem případě k = 3, d1 = 629, d2 = 750, d3 = 1122, d = 2501. ( ) ( ) ( ) 4486,0 2501 1122 0pˆ,2999,0 2501 750 0pˆ,2515,0 2501 629 0pˆ 121 ====== Odhad vektoru počátečních pravděpodobností: ( ) ( )45,0;3,0;25,00pˆ = . Znamená to, že na počátku sledování 25 % domácností v daném regionu nemělo žádné předplatné, 30 % předplácelo regionální deník a 45 % celostátní deník. Před výpočtem intervalů spolehlivosti ověříme, zda jsou splněny podmínky dobré aproximace ( ) ( )[ ] 5d0pˆ10pˆ ii ≥− . Přitom ( ) ( ) ( ) 2501d, 2501 1122 0pˆ, 2501 750 0pˆ, 2501 629 0pˆ 321 ==== . Tedy i = 1: 4692501 2501 629 1 2501 629 =      − , i = 2: 5252501 2501 750 1 2501 750 =      − , i = 3: 6192501 2501 1122 1 2501 1122 =      − . Vidíme, že podmínky jsou splněny. Pro i = 1, 2, 3 a 05,0=α dosadíme do vzorce ( ) ( ) ( )[ ] 21 ii i u d 0pˆ10pˆ 0pˆ α− − ± . Dostaneme meze 95% asymptotických intervalů spolehlivosti pro p1(0), p2(0), p3(0). ( ) ( )2685,0;2345,00p1 ∈ , ( ) ( )3178,0;2819,00p2 ∈ , ( ) ( )4681,0;4291,00p3 ∈ vždy s pravděpodobností 95 %. Interpretujeme např. 1. interval spolehlivosti: Ve sledovaném regionu je k danému datu s pravděpodobností 95 % 23,45 % až 26,85 % domácností, které nepředplácejí žádný deník. Nyní se budeme věnovat odhadům pravděpodobností přechodu. Použijeme vzorec k,,1j,i, c c pˆ i ij ij K== . Znovu uvedeme tabulku se zadanými údaji: 1 2 3 Σ 1 440 126 63 629 2 150 525 75 750 3 337 112 673 1122 Σ 2501 V našem případě k = 3, c11 = 440, c12 = 126, c13 = 63, c1 = 629, c21 = 150, c22 = 525, c23 = 75, c2 = 750, c31 = 337, c32 = 112, c33 = 673, c3 = 1122. 1002,0 629 63 pˆ,2003,0 629 126 pˆ,6995,0 629 440 pˆ 131211 ====== 1,0 750 75 pˆ,7,0 750 525 pˆ,2,0 750 150 pˆ 132221 ====== 5998,0 1122 673 pˆ,0998,0 1122 112 pˆ,3004,0 1122 337 pˆ 333231 ======           = 0,60,10,3 0,10,70,2 0,10,20,7 ˆP Interpretujeme např. 1. řádek odhadnuté matice přechodu: Pokud v jednom měsíci náhodně vybraná domácnost neodebírala žádný deník, tak v příštím měsíci s pravděpodobností 0,7 opět nebude mít žádné předplatné, s pravděpodobností 0,2 si předplatí regionální deník a s pravděpodobností 0,1 celostátní deník. Před výpočtem intervalů spolehlivosti ověříme splnění podmínek dobré aproximace ( ) 5cpˆ1pˆ iijij ≥− . Připomínáme, že c11 = 440, c12 = 126, c13 = 63, c1 = 629, c21 = 150, c22 = 525, c23 = 75, c2 = 750, c31 = 337, c32 = 112, c33 = 673, c3 = 1122. i = 1: 57629 629 63 1 629 63 ,101629 629 126 1 629 126 ,132629 629 440 1 629 440 =      −=      −=      − i = 2: 68750 750 75 1 750 75 ,158750 750 525 1 750 525 ,120750 750 150 1 750 150 =      −=      −=      − i = 3: 2691122 1122 673 1 1122 673 ,1091122 1122 112 1 1122 112 ,2361122 1122 337 1 1122 337 =      −=      −=      − Ve všech devíti případech jsou podmínky dobré aproximace splněny, můžeme tedy spočítat meze 95% asymptotických intervalů spolehlivosti pro pravděpodobnosti přechodu. Pro i, j = 1, 2, 3 a 05,0=α dosadíme do vzorce ( ) 21 i ijij ij u c pˆ1pˆ pˆ α− − ± . ( ) ( ) ( ),1236,0;0767,0p,2316,0;169,0p,7354,0;6637,0p 131211 ∈∈∈ ( ) ( ) ( ),1215,0;0785,0p,7328,0;6672,0p,2286,0;1714,0p 232221 ∈∈∈ ( ) ( ) ( )6285,0;5712,0p,1174,0;0823,0p,3272,0;2735,0p 333231 ∈∈∈ . Interpretujeme např. interval spolehlivosti pro p11: Pokud v jednom měsíci náhodně vybraná domácnost neodebírala žádný deník, tak v příštím měsíci můžeme se spolehlivostí 95 % zaručit, že s pravděpodobností 66,37 % až 73,54 % opět nebude odebírat žádný deník. 7. Klasifikace stavů homogenního markovského řetězce 7.1. Označení: Označení prvků matice Pn Nechť { }0n Nn;X ∈ je homogenní markovský řetězec s množinou stavů J a s maticí přechodu P. Prvky matice Pn budeme značit pij(n). 7.2. Definice: Definice doby prvního návratu do stavu j Nechť homogenní markovský řetězec { }0n Nn;X ∈ vychází ze stavu j, tj. P(X0 = j) = 1. Zavedeme množinu { }jX;1nT nj =≥= , která udává pořadí okamžiků návratů do stavu j. Náhodná veličina { } Tpro TproTmin j jj j    ∅=∞ ∅≠ =τ se nazývá doba prvního návratu do stavu j. 7.3. Označení: Označení pravděpodobnostní funkce doby prvního návratu do stavu j Náhodná veličina τj je diskrétní náhodná veličina, nabývá hodnot 1, 2, 3, ... Její pravděpodobnostní funkci označíme fj(n), tedy fj(n) = P(τj = n), n = 1, 2, 3, ... (pro n = 0 položíme fj(0) = 0). Pravděpodobnost, že homogenní markovský řetězec vycházející ze stavu j, se vůbec někdy vrátí do stavu j, je tedy ∑ ∞ = = 1n jj )n(ff . Pravděpodobnost fj lze vyjádřit jako P(τj < ∞). 7.4. Věta: Souvislost pravděpodobnostní funkce doby 1. návratu s pravděpodobnostmi přechodu Pravděpodobnostní funkce doby 1. návratu do stavu j souvisí s pravděpodobnostmi přechodu takto: ∑= −=∈∀ n 1k jjjjj ),k(f)kn(p)n(p:Jj n = 1, 2, 3, ... Odtud lze fj(n) vyjádřit pomocí rekurentního vztahu: ∑∑ − = − = −−=⇒+−=∈∀ 1n 1k jjjjj 1n 1k jjjjjjj )k(f)kn(p)n(p)n(f)n(f)k(f)kn(p)n(p:Jj . Důkaz: Pro k = 1, 2, 3, ... označme jev { }kjXA jnk =τ∧== . Jevy Ak jsou neslučitelné a { }jXA n n 1k k == = U . Počítáme ( ) ( ) ( ) ( ) ( ) ( ) ( ) ∑∑ ∑∑ ∑ ∑ == = − = = == −==== ==∧≠∧∧≠∧====τ∧===τ= ===τ∧====      ===== n 1k jjj n 1k knj n 1k k1k10nj n 1k j0nj n 1k n 1k 0jn0k0 n 1k k0njj )kn(p)k(fjX/jXP)k(f jXjXjXjX/jXP)k(fkjX/jXPkP jX/kjXPjX/APjX/APjX/jXP)n(p K U (Při úpravách byla použita rovnost ( ) ( ) ( )CB/APC/BPC/BAP ∩=∩ .) 7.5. Příklad: Nechť { }0n Nn;X ∈ je homogenní markovský řetězec s maticí přechodu       β−β αα− = 1 1 P . Je-li vektor počátečních pravděpodobností p(0) = (1, 0), vypočtěte pravděpodobnost, že doba 1. návratu do stavu 0 bude n, n = 1, 2, 3, ... a vypočtěte pravděpodobnost, že řetězec se vůbec někdy vrátí do stavu 0. Řešení: Použijeme vzorec ( ) ∑ − = −−= 1n 1k jjjjjj )k(f)kn(p)n(pnf . Počítáme P2 =       β−+αββ−β+βα− αβ−+αα−αβ+α− =      β−β αα−       β−β αα− 2 2 )1()1()1( )1()1()1( 1 1 1 1 P3 = =      β−β αα−       β−+αββ−β+βα− αβ−+αα−αβ+α− 1 1 )1()1()1( )1()1()1( 2 2       β−+αββ−+αβα−− −αββ−+αβα−+α− = 3 11 00 3 )1()1(2)1()3(p1 )3(p1)1()1(2)1( f0(1) = p00 = 1 – α f0(2) = p00(2) – p00f0(1) = (1 – α)2 + αβ – (1 – α)2 = αβ f0(3) = p00(3) – p00(2)f0(1) – p00f0(2) = (1 – α)3 + 2(1 – α)αβ + (1 – β)αβ – [(1 – α)2 + αβ](1 – α) – (1 – α)αβ = =(1 – α)3 + 2(1 – α)αβ + (1 – β)αβ – (1 – α)3 – (1 – α)αβ – (1 – α)αβ = (1 –β)αβ Obecně:    =αββ =α− = 2,3,...npro)-(1 1npro1 )n(f 2-n0 7.6. Definice: Definice trvalého a přechodného stavu Nechť { }0n Nn;X ∈ je homogenní markovský řetězec s množinou stavů J. a) Stav Jj∈ se nazývá trvalý, jestliže fj = 1 (tj. P(τj < ∞). (Znamená to, že řetězec se do stavu j vrátí po konečně mnoha krocích.) b) Stav Jj∈ se nazývá přechodný, jestliže fj < 1 (tj. P(τj = ∞). (Znamená to, že řetězec se do stavu j s kladnou pravděpodobností nikdy nevrátí.) Množina trvalých stavů se značí JT, množina přechodných stavů JP. Přitom ∅=∩=∪ PTPT JJ,JJJ . 7.7. Věta: Kritérium pro klasifikaci trvalých a přechodných stavů. a) Stav j je trvalý, právě když ∞=∑ ∞ =1n jj )n(p . b) Stav j je přechodný, právě když ∞<∑ ∞ =1n jj )n(p . Důkaz: Nebudeme provádět. 7.8. Příklad: Provádíme posloupnost opakovaných nezávislých hodů kostkou. Nechť náhodná veličina Xn udává maximální číslo dosažené v prvních n hodech, n = 1, 2, 3, ... Zavedeme homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {1, 2, ..., 6}, kde Xn = j, když v prvních n hodech bylo nejvyšší dosažené číslo j. Najděte matici přechodu P a klasifikujte stavy na trvalé a přechodné. Řešení:                             = 100000 6 1 6 5 0000 6 1 6 1 6 4 000 6 1 6 1 6 1 6 3 00 6 1 6 1 6 1 6 1 6 2 0 6 1 6 1 6 1 6 1 6 1 6 1 P Zajímají nás jen diagonální prvky matice Pn , protože zkoumáme řadu ∑ ∞ =1n jj )n(p . ..., 6 1 )3(p, 6 1 )2(p, 6 1 p 3 11 2 1111       =      == ..., 6 2 )3(p, 6 2 )2(p, 6 2 p 3 22 2 2222       =      == Obecně: n jj 6 j )n(p       = , j = 1, ..., 6 Řada ∑ ∞ =       1n n 6 j absolutně konverguje pro j = 1, 2, 3, 4, 5 a diverguje pro j = 6. Tedy JT = {6}, JP = {1, 2, 3, 4, 5}. 7.9. Definice: Definice trvalého nenulového stavu a trvalého nulového stavu Nechť Jj∈ je trvalý stav homogenního markovského řetězce { }0n Nn;X ∈ . a) Stav j se nazývá trvalý nenulový, jestliže existuje střední hodnota µj náhodné veličiny τj. b) Stav j se nazývá trvalý nulový, jestliže střední hodnota náhodné veličiny τj neexistuje. 7.10. Důsledek: Kritérium pro klasifikaci trvalých nenulových stavů a trvalých nulových stavů Stav j je trvalý nenulový, jestliže řada ∑ ∞ =1n j )n(nf absolutně konverguje. Stav j je trvalý nulový, jestliže řada ∑ ∞ =1n j )n(nf diverguje. 7.11. Poznámka: Lze ukázat, že HMŘ s konečnou množinou stavů nemůže mít trvalé nulové stavy. 7.12. Definice: Definice periodického stavu, neperiodického stavu, ergodického stavu Nechť dj je největší společný dělitel čísel n ≥ 1, pro něž pjj(n) > 0. Je-li dj > 1, pak řekneme, že stav j je periodický s periodou dj. Je-li dj = 1, pak řekneme, že stav j je neperiodický. Trvalý nenulový neperiodický stav se nazývá ergodický stav. 7.13. Příklad: Na úsečce délky 5 jsou vyznačeny body 0, 1, ..., 5. V bodě 3 se nachází kulička. Kulička koná náhodnou procházku po úsečce tak, že s pravděpodobností p se posune o jednotku napravo a s pravděpodobností q = 1 – p se posune o jednotku nalevo. Dosáhne-li bodu 0 nebo bodu 5, setrvá tam. Popište proces pomocí homogenního markovského řetězce a klasifikujte stavy na periodické a neperiodické. Řešení: Zavedeme homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {0, 1, 2, 3, 4, 5}, kde Xn = j, když v okamžiku n je kulička v bodě j.                     = 100000 p0q000 0p0q00 00p0q0 000p0q 000001 P p00(n) = 1 pro ⇒∈∀ Nn stav 0 je neperiodický. p55(n) = 1 pro ⇒∈∀ Nn stav 5 je neperiodický. p11(1) = 0, p11(2) = pq, p11(3) = 0, p11(4) = pqp, ... Největší společný dělitel čísel 2, 4, 6, ... je 2, tedy stav 1 je periodický s periodou 2. Stejně to dopadne se stavy 2, 3, 4. 7.14. Věta: Výpočet střední hodnoty doby 1. návratu do ergodického stavu a trvalého nenulového periodického stavu a) Nechť Jj∈ je trvalý nenulový neperiodický stav (tj. ergodický stav). Pak )n(plim 1 jjn j ∞→ =µ . b) Nechť Jj∈ je trvalý nenulový periodický stav s periodou dj. Pak )nd(plim d jjj n j j ∞→ =µ . 7.15. Příklad: Nechť je dán homogenní markovský řetězec { }0n Nn;X ∈ s množinou stavů J = {0, 1, 2} a maticí přechodu                 = 2 1 3 1 6 1 4 1 2 1 4 1 3 1 3 1 3 1 P . Vypočtěte střední hodnoty dob 1. návratů do stavů 0, 1, 2. Řešení: Jelikož matice P je regulární matice, bude matice Pn konvergovat k limitní matici, jejíž všechny řádky jsou stejné a jsou rovny stacionárnímu vektoru a matice P. ( ) ( )                 = 2 1 3 1 6 1 4 1 2 1 4 1 3 1 3 1 3 1 a,a,aa,a,a 210210 25 9 a 25 10 a 25 6 a 1aaa 2 a 4 a 3 a a 3 a 2 a 3 a a 6 a 4 a 3 a a 2 1 0 210 210 2 210 1 210 0 = = = ⇒                 =++ ++= ++= ++=       = 25 9 , 25 10 , 25 6 p ,       = 9 25 , 10 25 , 6 25 µ Vychází-li řetězec např. ze stavu 1, tak v průměru po 2,5 krocích se tam vrátí.