MASARYKOVA UNIVERZITA

MASARYKOVA UNIVERZITA PRˇI´RODOVEˇDECKA´ FAKULTA ´ STAV MATEMATIKY A STATISTIKY U

Bakala´rˇska´ praće

BRNO 2012

VLASTISLAV FORCH

MASARYKOVA UNIVERZITA PRˇI´RODOVEˇDECKA´ FAKULTA ´ STAV MATEMATIKY A STATISTIKY U

Pravdeˇpodobny´ vy´sledek jednoduche´ pozicˇnı´ hry Bakala´rˇska´ praće

Vlastislav Forch

Vedoucı´ praće: Mgr. David Kruml, Ph.D.

Brno 2012

Bibliograficky´ za´znam Autor:

Vlastislav Forch Prˇ´ırodoveˇdecka´ fakulta, Masarykova univerzita ´ stav matematiky a statistiky U

Na´zev praće:

Pravdeˇpodobny´ vy´sledek jednoduche´ pozicˇnı´ hry

Studijnı´ program:

Aplikovana´ matematika

Studijnı´ obor:

Financˇnı´ a pojistna´ matematika

Vedoucı´ praće:

Mgr. David Kruml, Ph.D.

Akademicky´ rok:

2011/2012

Pocˇet stran:

ix + 34

Klıćˇova´ slova:

markovsky´ rˇeteˇzec; stav; pravdeˇpodobnost prˇechodu; matice prˇechodu; absorpce; MATLAB; pozicˇnı´ hra; hernı´ plań; strategie; hadi a zˇebrˇ´ıky

Bibliographic Entry Author:

Vlastislav Forch Faculty of Science, Masaryk University Department of Mathematics and Statistics

Title of Thesis:

Probable result of a simple extensive game

Degree Programme:

Applied Mathematics

Field of Study:

Financial and Insured Mathematics

Supervisor:

Mgr. David Kruml, Ph.D.

Academic Year:

2011/2012

Number of Pages:

ix + 34

Keywords:

Markov chain; state; probability of transition; transition matrix; absorption; MATLAB; extensive game; game plan; strategy; Snakes and Ladders

Abstrakt Praće se veˇnuje vy´pocˇtu pravdeˇpodobne´ho vy´sledku hry hadi a zˇebrˇ´ıky pomocı´ markovskyćh rˇeteˇzcu˚. V prvnı´ cˇa´sti se zameˇrˇuje na teorii markovskyćh rˇeteˇzcu˚. V druhe´ cˇa´sti jsou tyto teoreticke´ znalosti aplikovańy. Konec praće nastinˇuje rˇesˇenı´ obtı´zˇneˇjsˇ´ıch proble´mu˚.

Abstract This thesis focuses on computation of the probable result of the game Snakes and Ladders using Markov chains. In the first part we study theory of Markov chains. In the second part we use these knowledge. The end of the thesis deals with more difficult problems.

Podeˇkovańı´ Na tomto mı´steˇ bych chteˇl podeˇkovat Mgr. Davidu Krumlovi, Ph.D., vedoucı´mu me´ bakala´rˇske´ praće, za cenne´ rady a prˇipomıńky k praći. Deˇkuji take´ za ochotu a cˇas, ktery´ mi veˇnoval.

Prohla´sˇenı´ Prohlasˇuji, zˇe jsem svoji bakala´rˇskou praći vypracoval samostatneˇ s vyuzˇitı´m informacˇnıćh zdroju˚, ktere´ jsou v praći citovańy.

Brno 29. kveˇtna 2012

.......................... Vlastislav Forch

Obsah ´ vod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii U Kapitola 1. Jednoducha´ pozicˇnı´ hra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Pozicˇnı´ hra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Hadi a zˇebrˇ´ıky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Klasicka´ hra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Upravena´ hra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 1 1 2

Kapitola 2. Markovske´ rˇeteˇzce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Stochasticky´ proces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Markovsky´ rˇeteˇzec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Vlastnosti markovske´ho rˇeteˇzce . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Homogennı´ markovsky´ rˇeteˇzec . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Vlastnostni homogennı´ho markovske´ho rˇeteˇzce . . . . . . . . . . . . 2.3.2 Prˇechodovy´ diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Stavy homogennı´ho markovske´ho rˇeteˇzce . . . . . . . . . . . . . . . . . . . . 2.5 Absorpcˇnı´ rˇeteˇzec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 5 7 9 10 10 12 13

Kapitola 3. Hadi a zˇebrˇı´ky jako homogennı´ markovsky´ rˇeteˇzec . . . . . . . . . . . 3.1 Vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´ . . . . . . . . . . . . . . . . . . . . . . . 3.2 Matice prˇechodu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Vy´pocˇet vektoru˚ absolutnıćh pravdeˇpodobnostı´ . . . . . . . . . . . . . . . 3.4 Absorpcˇnı´ rˇeteˇzec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Vy´sledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 17 17 19 24 26

Kapitola 4. Dva hraćˇi, strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Dva hraćˇi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29 29 32

Seznam pouzˇite´ literatury . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

– vii –

´ vod U Tato bakala´rˇska´ praće, jak jizˇ na´zev napovı´da´, se zaby´va´ mozˇnostı´ vy´pocˇtu pravdeˇpodobne´ho vy´sledku jednoduche´ pozicˇnı´ hry. Za tuto hru byla zvolena vsˇeobecneˇ zna´ma´ deskova´ hra hadi a zˇebrˇ´ıky. Vyuzˇito bylo teorie markovskyćh rˇeteˇzcu˚, konkre´tneˇ je hra modelovańa jako absorpcˇnı´ homogennı´ markovsky´ rˇeteˇzec s diskre´tnı´m cˇasem i stavy. Tento model mu˚zˇe by´t vyuzˇit i pro dalsˇ´ı podobne´ hry, poprˇ´ıpadeˇ mu˚zˇe s mensˇ´ımi u´pravami rˇesˇit neˇktere´ vhodne´ ekonomicke´ proble´my. Markovske´ rˇeteˇzce naleznou uplatneˇnı´ take´ v pojistne´ matematice. Prˇi psanı´ praće byly uplatneˇny take´ poznatky z teorie her, zejmeńa v poslednı´ kapitole. Hra byla vybrańa hlavneˇ kvu˚li jednoduchosti svyćh pravidel a prˇehlednosti hernı´ho plańu, cozˇ ocenı´me prˇedevsˇ´ım prˇi sestavovańı´ matice prˇechodu, ktera´ je jednou z nejdu˚lezˇiteˇjsˇ´ıch veˇcı´ pro dalsˇ´ı vy´pocˇty. Hernı´ plań byl vsˇak zmensˇen. Drobneˇ byla upravena take´ pravidla hry, kdy uvazˇujeme pouze jednoho hraćˇe. Za nejza´sadneˇjsˇ´ı vy´sledek lze povazˇovat vy´pocˇet strˇednı´ hodnoty pocˇtu okamzˇiku˚, ktere´ rˇeteˇzec stra´vı´ v neabsorpcˇnıćh stavech nezˇ bude absorbovań. Tuto strˇednı´ hodnotu lze interpretovat jako pocˇet hodu˚ kostkou (tahu˚), ktere´ jsou potrˇebne´ k dohrańı´ hry. Pro nasˇi hru je to 13 hodu˚ kostkou, zacˇ´ına´me-li na prvnı´m poli. Hru vsˇak lze dohra´t i po pouhyćh 3 hodech kostkou. Pro jednotlive´ vy´pocˇty byl pouzˇit vy´pocˇetnı´ syste´m MATLAB. Jedna´ se o komercˇnı´ syste´m a jeho uzˇ´ıvańı´ je tedy zpoplatneˇno. Mu˚zˇeme jej vsˇak zdarma vyuzˇ´ıt ´ stavu matematiky a statistiky na Prˇ´ırodoveˇdecke´ fav pocˇ´ıtacˇovyćh ucˇebnaćh U kulteˇ Masarykovy univerzity. Alternativou k MATLABu mu˚zˇe by´t jazyk R, ktery´ je bezplatny´. Tento jazyk je dostupny´ naprˇ´ıklad z http://www.r-project.org/. Praće je rozcˇleneˇna do cˇtyrˇ kapitol. Prvnı´ kapitola se veˇnuje hrˇe samotne´, jejı´m pravidlu˚m a za´kladnı´m principu˚m. Poznatky k te´to kapitole jsou cˇerpańy ze zdroju˚ [1], [2] a [12]. Druha´ kapitola se veˇnuje teorii markovskyćh rˇeteˇzcu˚. Pro jejı´ sestavenı´ byla pouzˇita literatura [3], [4], [5] [6], [7], [8] a [9]. Takte´zˇ bylo vyuzˇito studijnıćh materia´lu˚ RNDr. Marie Budı´kove´, Dr. k prˇedmeˇtu M5444 Markovske´ rˇeteˇzce, ktery´ jsem navsˇteˇvoval. Tento teoreticky´ apara´t nenı´ kompletnı´ teoriı´ k markovsky´m rˇeteˇzcu˚m. Hra je reprezentovańa jako absorpcˇnı´ rˇeteˇzec, proto v te´to praći nenalezneme naprˇ´ıklad rˇeteˇzce regula´rnı´. V trˇetı´ kapitole nalezneme model hry hadi a zˇebrˇky jako homogennı´ markovsky´ rˇeteˇzec a samotne´ vy´pocˇty s pomocı´ syste´mu MATLAB. Z literatury zde byly – viii –

´ vod U

ix

vyuzˇity prˇedevsˇ´ım zdroje [10] a [11]. Pro sestavenı´ grafu zna´zornˇujıćı´ pravdeˇpodobnost dohrańı´ hry prˇi m-te´m hodu kostkou bylo vyuzˇito praće [13]. Poslednı´, cˇtvrta´ kapitola se veˇnuje ota´zce dvou hraćˇu˚ a hrˇe, ve ktere´ ma´ hraćˇ vıće figurek. Pro napsańı´ te´to kapitoly bylo vyuzˇito zdroju˚ [1] a [2].

Kapitola 1 Jednoducha´ pozicˇnı´ hra 1.1

Pozicˇnı´ hra

Pozicˇnı´ hry jsou cˇasto hry pro dva hraćˇe, kdy oba majı´ urcˇitou mnozˇinu strategiı´, ze ktere´ mohou volit. Hraćˇi se strˇ´ıdajı´ v tazıćh, prˇicˇemzˇ jeden hraćˇ vzˇdy reaguje na tah druhe´ho hraćˇe a volı´ nejlepsˇ´ı mozˇnou strategii z te´ pozice, ve ktere´ se nacha´zı´ ˇ ada teˇchto her se hraje na desce, kterou mu˚zˇeme nazvat hernı´ po tahu protihraćˇe. R plań. Mezi nejzna´meˇjsˇ´ı pozicˇnı´ hry patrˇ´ı sˇachy, da´ma, cˇloveˇcˇe, nezlob se, cˇi trˇeba karetnı´ hra va´lka. Z modernıćh her pak mu˚zˇeme jmenovat naprˇ´ıklad Activity. Take´ hru hadi a zˇebrˇ´ıky, jı´zˇ se podrobneˇ veˇnuje tato praće, mu˚zˇeme povazˇovat za pozicˇnı´ hru. Hra hadi a zˇebrˇ´ıky je z pohledu teorie her hrou jednoho hraćˇe, ktery´m je prˇ´ıroda. Ta ha´zı´ kostkou a hraćˇi pak podle hodu posouvajı´ svou figurku. Prostor pro plnohodnotne´ vyuzˇitı´ strategie se zde nasky´ta´ v prˇ´ıpadeˇ, zˇe ma´ hraćˇ vıće figurek a mu˚zˇe po hodu kostkou zvolit, kterou figurkou ta´hne.

1.2 1.2.1

Hadi a zˇebrˇı´ky Klasicka´ hra

Hadi a zˇebrˇ´ıky je klasicka´ deskova´ hra. Hernı´ plań ma´ nejcˇasteˇji sto polı´ usporˇa´danyćh do cˇtverce o straneˇ deseti polı´. Tato pole jsou ocˇ´ıslovańa od 1 do 100. Dvojice na´hodnyćh polı´ jsou spojeny takzvany´mi zˇebrˇ´ıky, prˇ´ıpadneˇ hady. Jejich pocˇet by´va´ zpravidla vyrovnany´ a odvı´jı´ se od rozmeˇru˚ desky. • Hra je urcˇena pro 2 azˇ 6 hracˇu˚. • Kazˇdy´ hraćˇ umı´stı´ svoji figurku na pole cˇ´ıslo 1. • Hraćˇi hazı´ po rˇadeˇ kostkou ve smeˇru hodinovyćh rucˇicˇek. • Hraćˇ svou figurku posune vzˇdy o tu hodnotu, ktera´ padne na jeho kostce. –1–

Kapitola 1. Jednoducha´ pozicˇnı´ hra

2

• Pokud hraćˇ vstoupı´ na pole, kde zacˇ´ına´ zˇebrˇ´ık nebo had, vysˇplha´ na pole, kde tento zˇebrˇ´ık koncˇ´ı, poprˇ´ıpadeˇ sjede po hadovi dolu˚ na jeho konec. • Vstoupı´-li hraćˇ na pole, kde se nacha´zı´ figurka jine´ho hraćˇe (protihraćˇe), musı´ protihraćˇ svou figurku prˇesunout zpeˇt na pole startovnı´. • Vyhra´va´ ten, kdo jako prvnı´ dosa´hne pole cˇ´ıslo 100.

Obra´zek 1.1: Hernı´ plań 10 × 10 polı´

1.2.2

Upravena´ hra

Pro potrˇeby te´to praće bylo nutne´ pozmeˇnit pravidla a sestavit mensˇ´ı hernı´ plań nezˇ je beˇzˇne´, prˇedevsˇ´ım kvu˚li sestavenı´ matice prˇechodu homogennı´ho markovske´ho rˇeteˇzce, ktere´ se budeme podrobneˇ veˇnovat pozdeˇji. Pro prˇedstavu uved’me, zˇe pokud bychom zachovali rozmeˇry hernı´ho plańu 10 × 10 polı´ se sedmi hady a sedmi zˇebrˇ´ıky, matice prˇechodu pro jednoho hraćˇe s jednou figurkou by meˇla rozmeˇry 86 × 86. Upraveny´ hernı´ plań ma´ pouze 5×5 polı´. Snı´zˇen byl take´ pocˇet hadu˚ a zˇebrˇ´ıku˚ na dva od kazˇde´ho. 25 polı´ plańu budou cˇ´ıslovańa od 0 do 20, kde pole, na nichzˇ zacˇ´ına´ zˇebrˇ´ık nebo had, cˇ´ıslovańa nebudou. Tento krok bude rozebrań pozdeˇji v souvislosti s homogennı´mi markovsky´mi rˇeteˇzci. Pokud by meˇl hraćˇ po sve´m tahu figurku na jednom z teˇchto (necˇ´ıslovanyćh) polı´, posune ji nahoru nebo dolu˚ podle toho, zda na polıćˇku zacˇ´ına´ zˇebrˇ´ık cˇi had, stejneˇ jako v klasicke´ hrˇe. Prˇestozˇe nejsou tato pole ocˇ´ıslovańa, prˇi pohybu figurkou se pocˇ´ıta´ i s nimi, stejneˇ jako by cˇ´ıslovańa byla. Naprˇ´ıklad: Padne-li prˇi prvnı´m hodu kostkou hodnota 5, prˇesune hraćˇ figurku na pole cˇ´ıslo 4. Bude-li hodnota na kostce 3, prˇemı´stı´ se hraćˇ na pole s cˇ´ıslem 10, jelikozˇ se dostane na zacˇa´tek zˇebrˇ´ıku, ktery´ koncˇ´ı na poli 10. Pro vy´pocˇet budeme uvazˇovat pouze jednoho hraćˇe s jednou figurkou. Hraćˇem ve smyslu teorie her je vsˇak prˇ´ıroda, ktera´ ha´zı´ kostkou a volı´ ze svyćh sˇesti

Kapitola 1. Jednoducha´ pozicˇnı´ hra

3

mozˇnyćh strategiı´ (hodnot na kostce). Figurka je pak prˇemı´steˇna podle vy´sledku hodu. • Hraćˇ umı´stı´ svou figurku na pole cˇ´ıslo 0 a ha´zı´ kostkou. • Po kazˇde´m hodu se hraćˇ posune o hodnotu, ktera´ padla na hracı´ kostce. • Vstoupı´-li hraćˇ na pole, kde zacˇ´ına´ zˇebrˇ´ık nebo had, prˇesune figurku na jeho konec. • Cı´lem hry je dostat se na pole cˇ´ıslo 20. Hraćˇi ovsˇem musı´ padnout na kostce stejna´ hodnota, jako je pocˇet polı´, ktera´ mu zby´vajı´ na pole poslednı´. Bude-li hodnota na kostce vysˇsˇ´ı, hraćˇ zu˚sta´va´ na stejne´m poli jako prˇed hodem a ha´zı´ znovu.

Obra´zek 1.2: Hernı´ plań 5 × 5 polı´

Kapitola 2 Markovske´ rˇeteˇzce Nejprve ze vsˇeho si vybudujeme teoreticky´ apara´t, na jehozˇ za´kladeˇ pak mu˚zˇeme prˇeve´st hru hadi a zˇebrˇ´ıky na homogennı´ markovsky´ rˇeteˇzec. Jelikozˇ se prˇedpokla´dajı´ alesponˇ za´kladnı´ znalosti cˇtena´rˇe z pocˇtu pravdeˇpodobnosti, v teoreticke´ cˇa´sti zmıńı´me nejdrˇ´ıve stochasticke´ procesy a pote´ markovske´ rˇeteˇzce s diskre´tnı´m cˇasem, jejichzˇ specia´lnı´m prˇ´ıpadem jsou homogennı´ markovske´ rˇeteˇzce. S jejich pomocı´ budeme pocˇ´ıtat pravdeˇpodobny´ vy´sledek hry.

2.1

Stochasticky´ proces

Definice 2.1. Necht’je dań pravdeˇpodobnostnı´ prostor (Ω, A, P), mnozˇina T ⊆ R reprezentujıćı´ cˇas a rea´lna´ funkce X : Ω × T → R definovana´ pro kazˇde´ ω ∈ Ω a t ∈ T. Necht’pro vsˇechna t ∈ T je X (ω, t) na´hodna´ velicˇina vzhledem k A. Potom { X (ω, t) : ω ∈ Ω, t ∈ T } nazy´va´me stochasticky´ proces. Pozna´mka. V dalsˇ´ım textu zavedeme pro na´hodnou velicˇinu znacˇenı´ Xt a stochasticky´ proces budeme znacˇit jako { Xt , t ∈ T }. Definice 2.2. Necht’ { Xt , t ∈ T } je stochasticky´ proces. • Jestlizˇe je T spocˇetna´, linea´rneˇ usporˇa´dana´ mnozˇina (tj. t0 < t1 < · · · < tn ), jde o stochasticky´ proces s diskre´tnı´m cˇasem. • Je-li T interval, mluvı´me o stochasticke´m procesu se spojity´m cˇasem. Definice 2.3. Necht’ { Xt , t ∈ T } je stochasticky´ proces. Mnozˇinu vsˇech hodnot, jichzˇ mu˚zˇe naby´t na´hodna´ velicˇina Xt nazy´va´me mnozˇina stavu˚ a oznacˇ´ıme ji J, jejı´ prvky pak budeme nazy´vat stavy. • Je-li mnozˇina stavu˚ stochasticke´ho procesu spocˇetna´ (∀t ∈ T je na´hodna´ velicˇina Xt diskre´tnı´), jedna´ se o stochasticky´ proces s diskre´tnı´mi stavy. • Pokud je ∀t ∈ T na´hodna´ velicˇina Xt spojita´, jde o stochasticky´ proces se spojity´mi stavy. –4–

Kapitola 2. Markovske´ rˇeteˇzce

5

V prˇ´ıpadeˇ stochastickyćh procesu˚ s diskre´tnı´mi stavy se mnozˇina stavu˚ promı´ta´ nejcˇasteˇji do mnozˇiny prˇirozenyćh cˇ´ısel (J = {1, 2, 3, . . . }), ktera´ mu˚zˇe by´t doplneˇna nulou (J = {0, 1, 2, 3, . . . }). Toto cˇ´ıslovańı´ ma´ vsˇak vy´znam pouze jako oznacˇenı´ stavu˚, neuda´va´ zˇa´dnou hodnotu. Na za´veˇr te´to cˇa´sti definujeme stochasticky´ vektor a stochastickou matici. Definice 2.4. Necht’ma´ rˇa´dkovy´ vektor nejvy´sˇe spocˇetne´ mnozˇstvı´ neza´pornyćh slozˇek se soucˇtem, jenzˇ je roven 1, pak tento vektor bude nazy´vań stochasticky´ vektor. Je-li kazˇdy´ rˇa´dek cˇtvercove´ matice stochasticky´m vektorem, nazy´va´me tuto matici stochastickou maticı´.

2.2

Markovsky´ rˇeteˇzec

Definice 2.5. Necht’ N0 = {0, 1, 2, . . . } je indexova´ mnozˇina, jejı´ prvky nazveme okamzˇiky a J = {1, 2, . . . , n} prˇ´ıpadneˇ J = {0, 1, 2, . . . , n} je spocˇetna´ mnozˇina stavu˚1 . Stochasticky´ proces { Xn , n ∈ N0 }, pro ktery´ na´hodna´ velicˇina Xn naby´va´ hodnot z mnozˇiny stavu˚ J, nazveme markovsky´m rˇeteˇzcem s diskre´tnı´m cˇasem, splnˇuje-li na´sledujıćı´ dveˇ podmıńky: •

∀j ∈ J •

∃ n ∈ N0 : P ( X n = j ) > 0

P ( Xn = jn | Xn−1 = jn−1 ∧ Xn−2 = jn−2 ∧ · · · ∧ X0 = j0 ) = P ( Xn = jn | Xn−1 = jn−1 )

(2.1)

(2.2)

pro vsˇechna n ∈ N0 a vsˇechna j0 , j1 , . . . , jn ∈ J takova´, zˇe P ( Xn−1 = jn−1 ∧ Xn−2 = jn−2 ∧ · · · ∧ X0 = j0 ) > 0. Markovske´ rˇeteˇzce jsou tedy stochasticke´ procesy, ktere´ pocˇ´ıtajı´ s diskre´tnostı´ cˇasu i stavu˚ a splnˇujı´ dva vztahy. Vztah (2.1) popisuje vyloucˇenı´ nepotrˇebnyćh stavu˚. Tento vztah rˇ´ıka´, zˇe ke kazˇde´mu j ∈ J existuje alesponˇ jeden takovy´ okamzˇik n ∈ N0 , v neˇmzˇ je pravdeˇpodobnost, zˇe se markovsky´ rˇeteˇzec nale´za´ pra´veˇ ve stavu j, kladna´. Vztah (2.2) vyjadrˇuje markovskou vlastnost. Ta rˇ´ıka´, zˇe na budoucı´ stav majı´ dosavadnı´ stavy rˇeteˇzce vliv jen prostrˇednictvı´m stavu prˇ´ıtomne´ho. To znamena´, zˇe v okamzˇiku n je pravdeˇpodobnost vy´skytu stavu jn za´visla´ pouze na bezprostrˇedneˇ prˇedcha´zejıćı´m stavu v okamzˇiku n − 1. Nynı´ zavedeme znacˇenı´ typicke´ pro markovske´ rˇeteˇzce: 1 Obecne ˇ

mu˚zˇeme stavy znacˇit maly´mi pı´smeny, poprˇ´ıpadeˇ indexy j0 , j1 , . . . , jn .


6

• Nacha´zı´-li se markovsky´ rˇeteˇzec v cˇase n ve stavu j, pouzˇijeme na´sledujıćı´ znacˇenı´. { Xn = j } • Pravdeˇpodobnost, zˇe se markovsky´ rˇeteˇzec nacha´zı´ ve stavu j v okamzˇiku n (tj. P ( Xn = j)), nazveme absolutnı´ pravdeˇpodobnost stavu j v cˇase n a symbolicky zapı´sˇeme p j ( n ). • Vektor absolutnıćh pravdeˇpodobnostı´ v cˇase n zapı´sˇeme jako p(n) = p j0 (n), p j1 (n), . . . , p jn (n) . • Absolutnı´ pravdeˇpodobnost stavu j v cˇase n = 0 (tj. P ( X0 = j)) nazy´va´me pocˇa´tecˇnı´ pravdeˇpodobnost stavu j a znacˇ´ıme: p j (0). • Vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´ pak zapı´sˇeme na´sledovneˇ: p(n) = p j0 (0), p j1 (0), . . . , p jn (0) . • Podmıńeˇna pravdeˇpodobnost P ( Xn+1 = j | Xn = i ) = pij (n, n + 1) se nazy´va´ pravdeˇpodobnost prˇechodu ze stavu i v cˇase n do stavu j v cˇase n + 1 (take´ pravdeˇpodobnost prˇechodu 1. rˇa´du). • Podobneˇ P ( Xn+m = j | Xn = i ) = pij (n, n + m) se nazy´va´ pravdeˇpodobnost prˇechodu ze stavu i v cˇase n do stavu j v cˇase n + m (neˇkdy te´zˇ pravdeˇpodobnost prˇechodu m-te´ho rˇa´du), pro prˇirozene´ m ≥ 1. Pomocı´ pravdeˇpodobnostı´ prˇechodu mu˚zˇeme sestavit matici prˇechodu 1. cˇi vysˇsˇ´ıho rˇa´du: • Matice prˇechodu 1. rˇa´du: 

 p j0 j0 (n, n + 1) p j0 j1 (n, n + 1) . . . p j0 jn (n, n + 1)  p (n, n + 1) p (n, n + 1) . . . p (n, n + 1)  j1 j1 j1 jn  j j0  P(n, n + 1) =  1 . .. .. .. . .   . . . . p jn j0 (n, n + 1) p jn j1 (n, n + 1) . . . p jn jn (n, n + 1)


7

• Matice prˇechodu m-te´ho rˇa´du: 

 p j0 j0 (n, n + m) p j0 j1 (n, n + m) . . . p j0 jn (n, n + m)  p (n, n + m) p (n, n + m) . . . p (n, n + m)  j1 j1 j1 jn  j j0  P(n, n + m) =  1  .. .. . . .. ..   . . p jn j0 (n, n + m) p jn j1 (n, n + m) . . . p jn jn (n, n + m) opeˇt pro prˇirozene´ m ≥ 1.

2.2.1

Vlastnosti markovske´ho rˇeteˇzce

Veˇta 2.1. Necht’ { Xn , n ∈ N0 } je markovsky´ rˇeteˇzec. Jestlizˇe existujı´ nı´zˇe uvedene´ podmıńeˇne´ pravdeˇpodobnosti, platı´ pro ∀n, m, m1 , m2 ∈ N0 ∀i, j, k ∈ J: a) P ( Xn + m = j | Xn = i ) ≥ 0

tj.

pij (n, n + m) ≥ 0

Pravdeˇpodobnost prˇechodu ze stavu i v cˇase n do stavu j v cˇase n + m je vzˇdy neza´porna´. ( P ( Xn = j | Xn = i ) =

1

pro

i=j

0

pro

i 6= j ( tj.

pij (n, n) =

1

pro

i=j

0

pro

i 6= j

Pravdeˇpodobnost prˇechodu ve stejne´m okamzˇiku je jev jisty´, jestlizˇe nedojde ke zmeˇneˇ stavu (tj. i = j). V opacˇne´m prˇ´ıpadeˇ (tj. i 6= j) je tato pravdeˇpodobnost nulova´. b)

∑ P ( Xn + m = j | Xn = i ) = 1 j∈ J

tj.

∑ pij (n, n + m) = 1 j∈ J

Soucˇet prvku˚ kazˇde´ho jednoho rˇa´dku matice prˇechodu, tedy soucˇet pravdeˇpodobnostı´ prˇechodu ze stavu i do vsˇech stavu˚ rˇeteˇzce (vcˇetneˇ setrvańı´ ve stavu i) je vzˇdy roven 1. Kazˇdy´ rˇa´dek matice prˇechodu je tedy stochasticky´m vektorem a cela´ matice prˇechodu je pak stochastickou maticı´ podle definice 2.4. c) Chapmanova-Kolmogorovova rovnice:

∑ ( Xn + m1 = k

P ( Xn + m1 + m2 = j | Xn = i ) =

| Xn = i ) P ( Xn + m1 + m2 = j | Xn + m1 = k )

k∈ J

tj.

pij (n, n + m1 + m2 ) =

∑ pik (n, n + m1 ) pkj (n + m1, n + m1 + m2 )

k∈ J

(2.3)


8

Je-li rˇeteˇzec ve stavu i v cˇase n, do stavu j v cˇase n + m1 + m2 se dostane tak, zˇe v cˇase n + m1 prˇestoupı´ do libovolne´ho stavu k a pote´ do stavu j v cˇase n + m1 + m2 . d) Za´kon evoluce: P ( Xn + m = j ) =

∑ P ( Xn = k ) P ( Xn + m = j | Xn = k )

k∈ J

tj.

p j (n + m) =

∑ pk (n) pkj (n, n + m)

(2.4)

k∈ J

Do stavu j v cˇase n + m se lze dostat prˇes libovolny´ stav k v cˇase n. Du˚kaz. a) Podle definice 2.5, konkre´tneˇ vztahu (2.1) vyloucˇenı´ nepotrˇebnyćh stavu˚: P ( Xn = j ∧ Xn = i ) ≥ 0 a P ( Xn = i ) > 0. Pak:

P ( Xn = j ∧ Xn = i ) ≥0 P ( Xn = i ) ( 1 pro i = j P ( Xn = j ∧ Xn = i ) = ( Xn = j | Xn = i ) = P ( Xn = i ) 0 pro i 6= j P ( Xn = j | Xn = i ) =

b) 

∑ P ( Xn + m = j | Xn = i ) = P  j∈ J

 [

{ Xn + m = j } | Xn = i  =

j∈ J

P (Ω ∩ { Xn = i }) =1 P ( Xn = i ) c) P ( Xn + m1 + m2 = j | Xn = i ) = P ( Xn + m1 + m2 = j ∧ Xn = i ) P ( Xn = i )

=

P({ Xn+m1 +m2 = j}∩Ω∩{ Xn =i }) P ( Xn = i )

P({ Xn+m1 +m2 = j}∩ k∈ J { Xn+m1 =k }∩{ Xn =i }) P ( Xn = i )

=

S

∑ k ∈ J P ( Xn = i ∧ Xn + m1 = k ∧ Xn + m1 + m2 = j ) P ( Xn = i )

=

=

∑ k ∈ J P ( Xn = i ) P ( Xn + m1 = k | Xn = i ) P ( Xn + m1 + m2 = j | Xn + m1 = k ∧ Xn = i ) P ( Xn = i ) ∑ k ∈ J P ( Xn = i ) P ( Xn + m1 = k | Xn = i ) P ( Xn + m1 + m2 = j | Xn + m1 = k ) P ( Xn = i )

∑ P ( Xn + m1 = k

k∈ J

=

=

| Xn = i ) P ( Xn + m1 + m2 = j | Xn + m1 = k )


9

d) P ( Xn+m = j) = P (Ω ∩ { Xn+m = j}) =   P

[

{ Xn = k } ∩ { Xn + m = j }  =

∑ P ( Xn = k

∧ Xn + m = j ) =

k∈ J

k∈ J

∑ P ( Xn = k ) P ( Xn + m = j | Xn = k )

k∈ J

Pozna´mka. Prˇedchozı´ veˇtu 2.1 lze zapsat take´ maticoveˇ. a) P(n, n + m) ≥ 0, kde 0 je nulova´ matice, P(n, n) = I, kde I je jednotkova´ matice b) P(n, n + m)e = e, kde e je sloupcovy´ vektor ze samyćh jednicˇek c) P(n, n + m1 + m2 ) =P(n, n + m1 )P(n + m1 , n + m1 + m2 ) d) p(n + m) =p(n)P(n, n + m)

2.3

Homogennı´ markovsky´ rˇeteˇzec

Definice 2.6. Markovsky´ rˇeteˇzec { Xn , n ∈ N0 } s mnozˇinou stavu˚ J nazveme homogennı´m, pokud pravdeˇpodobnost prˇechodu ze stavu i do stavu j v cˇase n + 1, pij (n, n + 1), neza´visı´ na cˇasove´m okamzˇiku n, tedy pro vsˇechny hodnoty i, j ∈ J   p00 p01 . . . p0n p   10 p11 . . . p1n  a n ∈ N0 platı´ pij (n, n + 1) = pij . Pak matici P=  . .. ..  nazy´va´me ..  .. . . .  pn0 pn1 . . . pnn maticı´ prˇechodu a cˇ´ıslo pij pravdeˇpodobnostı´ prˇechodu. Pravdeˇpodobnost prˇechodu u homogennı´ho markovske´ho rˇeteˇzce tedy nenı´ za´visla´ na cˇase. Homogenita tedy v tomto prˇ´ıpadeˇ znamena´, zˇe mechanismus zpu˚sobujıćı´ zmeˇny stavu rˇeteˇzce (matice prˇechodu P) je v cˇase nemeˇnny´. Pravdeˇpodobnosti prˇechodu vysˇsˇ´ıch rˇa´du˚ pij (n, n + m) za´visı´ pouze na rozdı´lu prˇ´ıslusˇnyćh cˇasovyćh okamzˇiku˚, tedy na hodnoteˇ m. Pozna´mka. Znacˇenı´ zu˚sta´va´ stejne´ jako u markovskyćh rˇeteˇzcu˚, pouze u pravdeˇpodobnostı´ prˇechodu 1. rˇa´du pij podle prˇedchozı´ definice 2.6 vynecha´va´me (n, n + 1), pravdeˇpodobnosti prˇechodu vysˇsˇ´ıch rˇa´du˚ zapisujeme jako pij (m), kde m ≥ 1. Matici prˇechodu 1. rˇa´du pak opeˇt oznacˇme podle definice 2.6 jako P, matice prˇechodu vysˇsˇ´ıch rˇa´du˚ pak znacˇ´ıme P(m), kde m ≥ 1.


2.3.1

10

Vlastnostni homogennı´ho markovske´ho rˇeteˇzce

Veˇta 2.2. Necht’ { Xn , n ∈ N0 } je homogennı´ markovsky´ rˇeteˇzec s vektorem pocˇa´tecˇnıćh pravdeˇpodobnostı´ p(0) a maticı´ prˇechodu P. Pak pro ∀m ∈ N0 platı´: a) P ( m ) = Pm

(2.5)

Matice prˇechodu vysˇsˇ´ıho rˇa´du˚ P(m), pro m ≥ 1 je totozˇna´ s m-tou mocninou matice prˇechodu homogennı´ho markovske´ho rˇeteˇzce P, tedy s maticı´ Pm . b) p ( m ) = p (0 )Pm K zisku vektoru absolutnıćh pravdeˇpodobnostı´ v cˇase m postacˇ´ı znalost vektoru pocˇa´tecˇnıćh pravdeˇpodobnostı´ p(0) a mocnin matice prˇechodu P. Du˚kaz.

a) Z (2.3) (Chapmanovy-Kolmogorovovy rovnice) plyne: P ( m ) = P ( m − 1 + 1 ) = P ( m − 1 ) P = P ( m − 2 + 1 ) P = P ( m − 2 ) P2 =

· · · = P (0)P m = P m b) Z (2.4) (za´kona evoluce) plyne: p ( m ) = p ( m − 1 + 1 ) = p ( m − 1 ) P = p ( m − 2 + 1 ) P = p ( m − 2 ) P2 =

· · · = p(0)P m

Pozna´mka. Prvnı´ dveˇ vlastnosti z veˇty 2.1 platı´ i pro homogennı´ markovske´ rˇeteˇzce. Pravdeˇpodobnost prˇechodu pij je vzˇdy neza´porna´, pravdeˇpodobnost prˇechodu prˇi nezmeˇneˇne´m cˇasove´m okamzˇiku pij (n, n) je nulova´ pro i 6= j a jedna´ se o jev jisty´ pokud i = j. Matice prˇechodu P je stochasticka´ matice a jejı´ rˇa´dky jsou pak stochasticke´ vektory. Du˚kazy teˇchto tvrzenı´ nebudeme prova´deˇt, jsou obdobne´ jako u jizˇ zmıńeˇne´ veˇty 2.1.

2.3.2

Prˇechodovy´ diagram

Homogennı´ markovsky´ rˇeteˇzec lze zna´zornit i graficky, a to dı´ky prˇechodove´mu diagramu, ktery´ mu˚zˇe by´t v nerozvinute´m cˇi rozvinute´m tvaru. Prˇechodovy´ diagram v nerozvinute´m tvaru je orientovany´ ohodnoceny´ graf, jehozˇ vrcholy zna´zornˇujı´ stavy a orientovane´ hrany prˇedstavujı´ nenulove´ pravdeˇpodobnosti prˇechodu 1. rˇa´du. Tyto hrany jsou ohodnoceny podle pravdeˇpodobnostı´ prˇechodu. (Naprˇ´ıklad obra´zek 2.1.) Diagram v rozvinute´m tvaru ukazuje vsˇechny mozˇne´ cesty rˇeteˇzcem z konkre´tnı´ho stavu. Tento diagram pak zna´zornı´me pomocı´ stromu (obra´zek 2.2). Pomocı´


11

prˇechodove´ho diagramu v rozvinute´m tvaru mu˚zˇeme spocˇ´ıtat i vektor absolutnıćh pravdeˇpodobnostı´ p(n). Postupuje se tak, zˇe pro kazˇdy´ stav v okamzˇiku n secˇteme soucˇiny vah teˇch hran, ktere´ v okamzˇiku n v dane´m stavu koncˇ´ı. Prˇ´ıklad: Uvazˇujme homogennı´ markovsky´ rˇeteˇzec s maticı´ prˇechodu P.  0 12 21 0 0 1 1 1  4 4 2 P= 1 0 0 3 4 4 0 0 0 1 

Prˇedpokla´dejme, zˇe rˇeteˇzec zacˇal ve stavu 0. Vypocˇteˇte vektor absolutnıćh pravdeˇpodobnostı´ v cˇase n = 2 pomocı´ prˇechodove´ho diagramu. Rˇesˇenı´: Nejprve pro matici prˇechodu P sestavı´me prˇechodovy´ diagram v rozvinute´m i nerozvinute´m tvaru.

Obra´zek 2.1: Prˇechodovy´ diagram v nerozvinute´m tvaru

Obra´zek 2.2: Prˇechodovy´ diagram v rozvinute´m tvaru Nynı´ spocˇ´ıta´me absolutnı´ pravdeˇpodobnosti jednotlivyćh stavu˚ po 2 krocıćh. p0 (2) =

1 1 1 · = 2 4 8


12

1 1 1 · = 2 4 8 1 1 1 p2 (2) = · = 2 4 8 5 1 1 1 3 p3 (2) = · + · = 2 2 2 4 8 Nakonec sestavı´me vektor absolutnıćh pravdeˇpodobnostı´. 1 1 1 5 p(2) = , , , 8 8 8 8 p1 (2) =

2.4

Stavy homogennı´ho markovske´ho rˇeteˇzce

Necht’ { Xn , n ∈ N0 } je homogennı´ markovsky´ rˇeteˇzec s mnozˇinou stavu˚ J. Jak jizˇ vı´me ze vztahu (2.5), matici prˇechodu vysˇsˇ´ıch rˇa´du˚ mu˚zˇeme zapisovat jako Pm , kde m ≥ 1. Prvky te´to matice pak znacˇ´ıme pij (m). V literaturˇe se mu˚zˇeme setkat i se znacˇenı´m pijm , kde index m oznacˇuje porˇadı´ cˇasove´ho okamzˇiku, nikoliv mocninu. Definice 2.7. Necht’se homogennı´ markovsky´ rˇeteˇzec { Xn , n ∈ N0 } v cˇase n = 0 nacha´zı´ ve stavu j, tj. P( X0 = j) = p j (0) = 1. Zavedeme mnozˇinu Tj = {n ≥ 1 : Xn = j}. Ta uda´va´ porˇadı´ okamzˇiku˚, v nichzˇ se rˇeteˇzec vracı´ do stavu j. Na´hodnou velicˇinu τj definovanou jako ( τj =

min{ Tj }

pro

Tj 6= ∅

∞

pro

Tj = ∅

nazveme dobou prvnı´ho na´vratu do stavu j. Definice 2.8. Necht’ { Xn , n ∈ N0 } je homogennı´ markovsky´ rˇeteˇzec s mnozˇinou stavu˚ J. • Stav j ∈ J je trvaly´, pokud P(τj < ∞) = 1. • Je-li P(τj = ∞) > 0, stav j ∈ J je prˇechodny´. Do trvale´ho stavu se rˇeteˇzec vra´tı´ po konecˇneˇ mnoha krocıćh. U prˇechodne´ho stavu existuje kladna´ pravdeˇpodobnost, zˇe se rˇeteˇzec do tohoto stavu nevra´tı´. Mnozˇinu trvalyćh stavu˚ mu˚zˇeme oznacˇit jako JT , prˇechodnyćh jako JP . Prˇitom je zrˇejme´, zˇe JT ∪ JP = J a JT ∩ JP = ∅. Definice 2.9. Necht’ j ∈ J je trvaly´ stav homogennı´ho markovske´ho rˇeteˇzce { Xn , n ∈ N0 } a necht’µ j je strˇednı´ hodnota na´hodne´ velicˇiny τj . • Existuje-li µ j , pak stav j ∈ J nazveme trvaly´m nenulovy´m.


13

• Stav j ∈ J se nazy´va´ trvaly´ nulovy´, pokud strˇednı´ hodnota µ j neexistuje. Definice 2.10. Necht’ j ∈ J a d j je nejveˇtsˇ´ı spolecˇny´ deˇlitel cˇ´ısel m ≥ 1, pro ktera´ platı´ p jj (m) > 0. • Stav j ∈ J je periodicky´ s periodou d j , pokud d j > 1. • Je-li d j = 1, pak stav j ∈ J nazveme neperiodicky´m. Definice 2.11. Stav j ∈ J nazveme ergodicky´m, je-li tento stav trvaly´ nenulovy´ neperiodicky´. U ergodicke´ho stavu tedy mu˚zˇe na´vrat do vyćhozı´ho stavu nastat kdykoliv. Pomocı´ pravdeˇpodobnostı´ prˇechodu po n krocıćh pij (n) mu˚zˇeme rozlisˇit stavy dosazˇitelne´ a nedosazˇitelne´ z urcˇityćh stavu˚. Definice 2.12. Stav j ∈ J nazveme dosazˇitelny´m ze stavu i ∈ J, existuje-li pij (n) > 0 pro neˇjake´ n ∈ N0 , tj. existuje-li nenulova´ pravdeˇpodobnost prˇechodu ze stavu i do j po n krocıćh. V opacˇne´m prˇ´ıpadeˇ (∀n ∈ N0 : pij (n) = 0) se jedna´ o stav nedosazˇitelny´. Definice 2.13. Dva stavy i, j ∈ J, i 6= j, nazveme sousledny´mi, jsou-li vza´jemneˇ dosazˇitelne´. Tj. existuje-li pij (n) > 0 a za´rovenˇ p ji (m) > 0 pro libovolna´ n, m ∈ N0 Pozna´mka. Skupinu takovyćh stavu˚ pak mu˚zˇeme nazvat uzavrˇenou trˇ´ıdou. Nacha´zı´-li se vsˇechny stavy rˇeteˇzce v jedne´ te´to trˇ´ıdeˇ, nazy´va´me rˇeteˇzec nerozlozˇitelny´m, v opacˇne´m prˇ´ıpadeˇ rozlozˇitelny´m. Tvorˇ´ı-li vsˇechny stavy rˇeteˇzce uzavrˇenou trˇ´ıdu a jsou-li navıć ergodicke´, pak nazveme rˇeteˇzec regula´rnı´m. Definice 2.14. Necht’j, k ∈ J, platı´-li pro neˇktery´ ze stavu˚ rˇeteˇzce pkk = 1 a za´rovenˇ ∃ j : p jk > 0. Tedy setrvańı´ ve stavu k je jisty´ jev a rˇeteˇzec mu˚zˇe vstoupit do tohoto stavu. Pak nazy´va´me tento stav pohlcujıćı´ (absorpcˇnı´ ). Pozna´mka. Vstoupı´-li rˇeteˇzec do absorpcˇnı´ho stavu, rˇekneme, zˇe je absorbovań.

2.5

Absorpcˇnı´ rˇeteˇzec

Definice 2.15. Homogennı´ markovsky´ rˇeteˇzec { Xn , n ∈ N0 } s koncecˇnou mnozˇinou stavu˚ J nazy´va´me absorpcˇnı´ rˇeteˇzec, pokud vsˇechny jeho trvale´ stavy jsou absorpcˇnı´. Veˇta 2.3. V absorpcˇnı´m markovske´m rˇeteˇzci je pravdeˇpodobnost absorbovańı´ procesu rovna 1.


14

Du˚kaz. Uka´zˇeme pouze hlavnı´ mysˇlenku du˚kazu. Z kazˇde´ho neabsorpcˇnı´ho stavu j lze prˇejı´t do absorpcˇnı´ho stavu k, ne nutneˇ za jeden cˇasovy´ okamzˇik (p jk (n) > 0). Oznacˇ´ıme c j nejmensˇ´ı pocˇet okamzˇiku˚ nutnyćh k prˇechodu do absorpcˇnı´ho stavu, za prˇedpokladu, zˇe se rˇeteˇzec v cˇase n = 0 nacha´zı´ ve stavu j, tedy rˇeteˇzec vyjde ze stavu j. Pravdeˇpodobnost, zˇe rˇeteˇzec za tuto dobu neprˇejde do absorpcˇnı´ho stavu oznacˇ´ıme p j . Pak tato pravdeˇpodobnost p j je nutneˇ z otevrˇene´ho intervalu (0, 1). Da´le necht’ c je nejveˇtsˇ´ı z cˇ´ısel c j a p nejveˇtsˇ´ı z p j . Pak pravdeˇpodobnost, zˇe rˇeteˇzec nebude absorbovań v cˇase c je mensˇ´ı nezˇ p. Pravdeˇpodobnost, zˇe nebude absorbovań ani za 2c cˇasovyćh okamzˇiku˚ je mensˇ´ı nezˇ p2 , atd. Jelikozˇ 0 < p < 1, tyto pravdeˇpodobnost se blı´zˇ´ı nule, podle lim pn = 0.

n→∞

Absorpce je pak jev opacˇny´ a jejı´ pravdeˇpodobnsot se blı´zˇ´ı 1. Definice 2.16. Necht’ { Xn , n ∈ N0 } je homogennı´ markovsky´ rˇeteˇzec, ktery´ je absorpcˇnı´, s konecˇnou mnozˇinou stavu˚ J. Necht’ma´ a absorpcˇnıćh a n neabsorpcˇnıćh stavu˚. Mnozˇinu absorpcˇnıćh stavu˚ oznacˇ´ıme J A a neabsorpcˇnıćh JN . Prˇecˇ´ıslujeme stavy tak, aby po mnozˇineˇ absorpcˇnıćh stavu˚ J A na´sledovaly neabsorpcˇnı´ stavy v mnozˇineˇ JN a matici prˇechodu P pak prˇepı´sˇeme na tvar P=

I* 0 , A N

kde I* je jednotkova´ matice o rozmeˇrech a × a, 0 je nulova´ matice rozmeˇru˚ a × n. Matice A obsahuje pravdeˇpodobnosti prˇechodu z neabsorpcˇnıćh do absorpcˇnıćh stavu˚ a je typu n × a. Matice N rozmeˇru˚ n × n je maticı´ prˇechodu mezi neabsorpcˇnı´mi stavy. Matici F = (I − N)−1 , kde I je jednotkova´ matice stejnyćh rozmeˇru˚ jako matice N, nazy´va´me fundamenta´lnı´ maticı´ absorpcˇnı´ho rˇeteˇzce. Prvky f ij matice F uda´vajı´ strˇednı´ hodnotu pocˇtu okamzˇiku˚, ktere´ rˇeteˇzec, jenzˇ vyjde ze stavu i, stra´vı´ ve stavu j, nezˇ prˇejde do absorpcˇnı´ho stavu. Soucˇet prvku˚ v i-te´m rˇa´dku matice F uda´va´ strˇednı´ hodnotu pocˇtu okamzˇiku˚, ktere´ rˇeteˇzec stra´vı´ v neabsorpcˇnıćh stavech, jestlizˇe vyjde ze stavu i a skoncˇ´ı v absorpcˇnı´m stavu. Maticoveˇ to lze zapsat jako t = Fe, kde e je sloupcovy´ vektor ze samyćh jednicˇek rozmeˇru˚ n × 1. Veˇta 2.4. Necht’ { Xn , n ∈ N0 } je absorpcˇnı´ homogennı´ markovsky´ rˇeteˇzec, stav i ∈ J je neabsorpcˇnı´ a k ∈ J je absorpcˇnı´. Oznacˇme uik pravdeˇpodobnost, zˇe rˇeteˇzec bude absorbovań ve stavu k, kdyzˇ vysˇel ze stavu i. Sestavı´me matici U = (uik )i,k∈ J . Pak U = FA, kde F je fundamenta´lnı´ matice a A je matice pravdeˇpodobnostı´ prˇechodu z neabsorpcˇnıćh do absorpcˇnıćh stavu˚.


15

Du˚kaz. Stavu k lze dosa´hnout beˇhem jednoho okamzˇiku s pravdeˇpodobnostı´ uik nebo prˇechodem prˇes jiny´ neabsorpcˇnı´ stav j ∈ J s pravdeˇpodobnostı´ pij a pote´ do absorpcˇnı´ho stavu k s pravdeˇpodobnostı´ u jk . Tedy uik =

∑ pij u jk . j∈ J

Kapitola 3 Hadi a zˇebrˇı´ky jako homogennı´ markovsky´ rˇeteˇzec Nynı´ ma´me dostatecˇny´ teoreticky´ apara´t k prˇevedenı´ hry hadi a zˇebrˇ´ıky na homogennı´ markovsky´ rˇeteˇzec. Hra pocˇ´ıta´ jak s diskre´tnı´mi stavy, tak cˇasem. Stavy jsou jednotliva´ pole hernı´ho plańu ocˇ´ıslovańa od 0 do 20. Tedy J = {0, 1, 2, . . . , 20}. Cˇasovy´mi okamzˇiky cˇi kroky pak budou hody kostkou. Hod kostkou a na´sledne´ posunutı´ figurky nazveme tahem. Vyloucˇenı´ nepotrˇebnyćh stavu˚ jsme provedli jizˇ v sekci 1.2.2, kdy jsme na hernı´m plańu neocˇ´ıslovali pole, na kteryćh zacˇ´ınajı´ zˇebrˇ´ıky nebo hadi. Na teˇchto polıćh nezu˚stane figurka po zˇa´dne´m z tahu˚. Odpovı´dajıćı´ rˇa´dky a sloupce matice prˇechodu P by pro tato pole byly nulove´. Hra take´ splnˇuje markovskou vlastnost. Pravdeˇpodobnost, zˇe se figurka bude nacha´zet po n-te´m hodu na poli jn , za´visı´ pouze na tom, kde se nacha´zı´ po hodu n − 1, nikoli na tom, na jakyćh polıćh se nacha´zela po hodech n − 2, n − 3, . . . Homogenitu pak zajisˇt’uje nemeˇnnost hernı´ho plańu v cˇase a sta´le stejny´ interval pocˇtu ok na kostce, jako dva faktory, ktere´ ovlivnˇujı´ pravdeˇpodobnosti prˇechodu. Matici prˇechodu prvnı´ho rˇa´du pak nazveme jednodusˇe maticı´ prˇechodu P. K tomu, abychom podle veˇty 2.2 o vlastnostech homogennı´ho markovske´ho rˇeteˇzce zı´skali vektory absolutnıćh pravdeˇpodobnostı´ v cˇase m, dı´ky ktery´m zı´ska´me pravdeˇpodobnosti vy´skytu figurky po m hodech kostkou, potrˇebujeme vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´ p(0), matici prˇechodu P a jejı´ mocniny, ktere´ spocˇ´ıta´me pomocı´ syste´mu MATLAB.

– 16 –

Kapitola 3. Hadi a zˇebrˇ´ıky jako homogennı´ markovsky´ rˇeteˇzec

3.1

17

Vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´

Jak je jizˇ uvedeno v pravidlech, prˇi zaha´jenı´ hry umı´stı´ hraćˇ svou figurku na pole cˇ´ıslo 0. Tedy P ( X0 = 0) = p0 (0) = 1. Tj. s pravdeˇpodobnostı´ 1 (100 %) se v cˇase 0 (zaha´jenı´ hry) bude figurka nale´zat na poli 0. Ostatnı´ pole budou obsazena s nulovou pravdeˇpodobnostı´. Vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´ p(0) = ( p0 (0), p1 (0), p2 (0), . . . , p19 (0), p20 (0)) bude po dosazenı´ pravdeˇpodobnostı´ na´sledujıćı´: p(0) = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0).

3.2

Matice prˇechodu

Prˇi sestavovańı´ matice prˇechodu budeme prˇedpokla´dat vyva´zˇenost hracı´ kostky. Pravdeˇpodobnost, zˇe padne jaka´koliv mozˇna´ hodnota (1 - 6) je vzˇdy stejna´, tj. 61 . Hodnoty v prvnı´m rˇa´dku matice P uda´vajı´ pravdeˇpodobnost s jakou se figurka po jednom hodu kostkou prˇesune z pole 0 na jine´ pole. Symbolicky tuto pravdeˇpodobnost zapı´sˇeme jako p0i , kde i = 0, 1, 2, . . . , 20. 1 1 1 1 1 p0,0 = 0, p0,1 = , p0,2 = , p0,3 = , p0,4 = , p0,5 = , 6 6 6 6 6 1 p0,6 = 0, . . . , p0,9 = 0, p0,10 = , p0,11 = 0, . . . , p0,20 = 0 6 Vidı´me, zˇe pravdeˇpodobnost setrvańı´ ve stavu 0 je nulova´. Pokud hraćˇi padne hodnota 1 posune se na pole 1, pokud bude pocˇet ok na kostce roven dveˇma, prˇesune svoji figurku na pole 2. Padne-li na kostce cˇ´ıslo 3, meˇl by hraćˇ posunout svoji figurku na neocˇ´ıslovane´ pole, kde zacˇ´ına´ zˇebrˇ´ık, jak vidı´me na hernı´m plańu na obra´zku 1.2. Podle pravidel vsˇak hraćˇ prˇesune svoji figurku na pole 10, kde tento zˇebrˇ´ık koncˇ´ı. Proto je pravdeˇpodobnost prˇechodu p0,10 = 61 . Hodı´-li hraćˇ na kostce 4, 5 nebo 6, posune se po rˇadeˇ na pole 3, 4 nebo 5, pro kazˇdou z hodnot s pravdeˇpodobnostı´ 16 . Na ostatnı´ pole nelze prˇi jednom hodu kostkou z pole cˇ´ıslo 0 dosa´hnout, pravdeˇpodobnost prˇechodu do teˇchto stavu˚ z pole 0 je tedy rovna nule. Druhy´ rˇa´dek matice uda´va´ pravdeˇpodobnosti prˇechodu z pole 1 na ostatnı´ pole hernı´ho plańu. Podobneˇ jako u pole 0 nemu˚zˇe hraćˇ setrvat po hodu kostkou na poli 1. Takte´zˇ se nemu˚zˇe vra´tit na pole s cˇ´ıslem 0. Pokud na hracı´ kostce padne 2, hraćˇ prˇesune svou figurku po zˇebrˇ´ıku na pole s cˇ´ıslem 10. Pravdeˇpodobnost, zˇe na kostce padne hodnota dva je opeˇt 16 . Stejneˇ je tomu u ostatnıćh hodnot 1, 3, 4, 5 a 6, prˇi nichzˇ se figurka posune po rˇadeˇ na pole 2, 3, 4, 5 a 6. Pravdeˇpodobnost


18

dosazˇenı´ jinyćh stavu˚, nezˇ zde zmıńeˇnyćh, je nulova´. Nenulove´ pravdeˇpodobnosti prˇechodu ve druhe´m rˇa´dku budou na´sledujıćı´: 1 1 1 1 1 1 p1,2 = , p1,3 = , p1,4 = , p1,5 = , p1,6 = a p1,10 = . 6 6 6 6 6 6 Obdobneˇ sestavı´me i ostatnı´ rˇa´dky matice prˇechodu P, prˇicˇemzˇ pravdeˇpodobnosti prˇechodu na pole, kde zacˇ´ınajı´ zˇebrˇ´ıky a hadi, osˇetrˇ´ıme stejneˇ jako v prˇedchozıćh dvou odstavcıćh. Zastavme se jesˇteˇ u poslednıćh peˇti rˇa´dku˚ matice P. Jak jizˇ vı´me z pravidel, pokud hraćˇi nepadne prˇesny´ pocˇet ok na hracı´ kostce, jaky´ potrˇebuje na prˇesun na poslednı´ pole ve hrˇe, zu˚sta´va´ figurka na stejne´m poli jako prˇed hodem kostkou a hraćˇ ha´zı´ znovu. Stojı´-li hraćˇ na poli cˇ´ıslo 16, mu˚zˇe se s pravdeˇpodobnostı´ 16 prˇesunout na pole 17, 18 a 19, hodı´-li po rˇadeˇ kostkou hodnotu 1, 2 a 3. Padne-li hodnota 4, prˇesune hraćˇ svou figurku po hadovi na pole 11. Hraćˇ vyhraje hru, pokud padne na kostce hodnota 5. Prˇi hodu sˇesti ok vsˇak figurka zu˚sta´va´ na poli 16. Nenulove´ pravdeˇpodobnosti prˇechodu z pole 16 budou: 1 1 1 1 1 p16,11 = , p16,16 = , p16,17 = , p16,18 = , p16,19 = 6 6 6 6 6

a

1 p16,20 = . 6

Pravdeˇpodobnost setrvańı´ ve stavu 17, p17,17 , bude rovna 62 = 13 . Hraćˇ v tomto stavu setrva´, padne-li hodnota 5 nebo 6. Pravdeˇpodobnost setrvańı´ ve stavu 18 se zvy´sˇ´ı opeˇt o 16 , tedy na 12 , atd . . . Dostane-li se hraćˇ do stavu 20, vyhra´va´ hru. Z teorie markovskyćh rˇeteˇzcu˚ rˇekneme, zˇe rˇeteˇzec bude absorbovań. Jedina´ nenulova´ pravdeˇpodobnost prˇechodu v poslednı´m rˇa´dku matice P bude tedy p20,20 = 1. Matice prˇechodu P pro nasˇi hru hadi a zˇebrˇ´ıky vypada´ na´sledovneˇ:




0 0  0  0   0  0  0  0  0  0   P = 0  0  0  0  0  0   0  0  0  0 0

3.3

1 6

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 6 1 6

1 6 1 6 1 6

1 6 1 6 1 6 1 6

1 6 1 6 1 6 1 6 1 6

0 0 0 0 0 0 0 0 0 0 1 6 0 0 0 1 6 0 0 0 1 6 0 0 0 1 6 0 0 0 1 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 16 1 1 6 0 0 0 6 1 1 1 6 6 0 0 6 1 1 1 6 6 6 0 0 1 1 1 1 6 6 6 6 0 1 6

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 6 1 6

0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 6 1 6 1 6

0 0 0 0 0 0 0 0 0 0 0 0 0

1 6 1 6 1 6 1 6

0 0 0 0 0 0 0 0 0 0 0 0

1 6 1 6 1 6 1 6 1 6

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 6 1 6 1 6 1 6

0 0 0 0 0 0 0 0 1 6 1 6 1 6 1 6

19

0 0 0 0 0 0 0 0 0 1 6 1 6 1 6 1 6

0 0 0 0 0 0 1 6 0 0 1 6 0 0 1 6 0 0 1 6 0 0 1 6 0 0 1 6 0 0 0 0 0

 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0  1 0 6 0 0 0 0 0   0 16 0 0 0 0 0   0 16 0 0 0 0 0   0 16 0 0 0 0 0   0 16 0 0 0 0 0   0 16 0 0 0 0 0    1 0 0 0 0 0 0  6  1 1 6 6 0 0 0 0 0  1 1 1 1  6 6 6 6 0 0 0 1 1 1 1 1  6 6 6 6 6 0 0 1 1 1 1 1 1  6 6 6 6 6 6 0 1 1 1 1 1 0 6 6 6 6 6 0  0 0 16 16 16 16 16    0 0 16 16 16 16 16   0 0 0 13 16 16 16   0 0 0 0 12 16 16   0 0 0 0 0 23 16  0 0 0 0 0 0 1

Vy´pocˇet vektoru˚ absolutnıćh pravdeˇpodobnostı´

V te´to cˇa´sti uka´zˇeme, jak pomocı´ vy´pocˇetnı´ho syste´mu MATLAB zı´ska´me vektory absolutnıćh pravdeˇpodobnostı´ po m hodech kostkou. Dı´ky teˇmto vektoru˚m p(m) = ( p0 (m), p1 (m), . . . , p20 (m)) zı´ska´me pravdeˇpodobnost vy´skytu figurky na polıćh hernı´ho plańu. Poslednı´ slozˇka tohoto vektoru pak uda´va´ pravdeˇpodobnost absorpce rˇeteˇzce, tedy pravdeˇpodobnost dohrańı´ hry. Nejdrˇ´ıv zadefinujeme matici prˇechodu P. Prˇi zada´vańı´ matice oddeˇlujeme jednotlive´ prvky v rˇa´dcıćh mezerou (space) nebo cˇa´rkou (,). Pro oddeˇlenı´ jednotlivyćh rˇa´dku˚ matice pak pouzˇijeme strˇednı´k (;). Prˇ´ıkaz ukoncˇ´ıme takte´zˇ strˇednı´kem, dı´ky cˇemuzˇ se vy´sledna´ matice nevypı´sˇe, cozˇ u nasˇ´ı matice prˇechodu s rozmeˇry 21 × 21 uvı´ta´me. Prvky matice jsou uzavrˇeny v hranatyćh za´vorkaćh. >> P=[0 1/6 1/6 1/6 1/6 1/6 0 0 . . . 0 0 0 0 0 1]; Pozna´mka. Vzhledem k de´lce prˇ´ıkazu jsem se rozhodl nevypisovat jej cely´, pouze zacˇa´tek a konec. Podrobneˇji o praći s maticemi v MATLABu v [10] a [11]. Da´le potrˇebujeme vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´ p(0).


20

>> p0 = [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]; Syntaxe prˇ´ıkazu je obdobna´ jako u matice prˇechodu P. Vektor jsme zadefinovali jako matici o rozmeˇrech 1 × 21. Na konec prˇ´ıkazu opeˇt prˇida´me strˇednı´k. Podle veˇty 2.2 o vlastnostech homogennı´ho markovske´ho rˇeteˇzce mu˚zˇeme spocˇ´ıtat vektory absolutnıćh pravdeˇpodobnostı´ pro jednotliva´ m = 1, 2, 3, 4, . . . podle vzorce p(m) = p(0)Pm . Na´sobenı´ v MATLABu provedeme jednodusˇe pomocı´ symbolu *. Umocnˇovańı´ matice prˇechodu pak pomocı´ symbolu ^. Umocnˇovańı´ matic vysˇsˇ´ıch rˇa´du˚ vsˇak mu˚zˇe by´t i pro vy´pocˇetnı´ syste´my cˇasoveˇ na´rocˇny´ proble´m a prˇi zaokrouhlovańı´ mu˚zˇou vznikat neprˇesnosti. Cˇa´stecˇny´m rˇesˇenı´m tohoto proble´mu by bylo nalezenı´ Jordanova kanonicke´ho tvaru matice prˇechodu a umocnˇovańı´ prova´deˇt pomocı´ neˇj. Jordanu˚v kanonicky´ tvar matice prˇechodu P oznacˇme J. Tato matice J se skla´da´ s tzv. jordanovyćh bloku˚, ktere´ se skla´dajı´ z vlastnıćh cˇ´ısel matice P na diagona´le teˇchto bloku˚ a prˇ´ıpadneˇ jednicˇek nad hlavnı´ diagona´lou. Pokud bychom nasˇli tuto matici J a matici Q takovou, zˇe P = Q · J · Q−1 , mocniny matice prˇechodu bychom spocˇ´ıtali pomocı´ vztahu n P n = Q · J · Q−1 = Q · Jn · Q−1 . Prˇi tomto vy´pocˇtu vsˇak narazı´me na dva proble´my. Prvnı´m proble´mem je samotny´ vy´pocˇet vlastnıćh cˇ´ısel λ, druhy´m pak nalezenı´ matice Q. Pro vy´pocˇet matic J a Q existuje v syste´mu MATLAB prˇ´ıkaz [J,Q] = jordan (P), ktery´ do promeˇnne´ J ulozˇ´ı Jordanu˚v kanonicky´ tvar matice prˇechodu P a do promeˇnne´ Q pak matici Q. MATLAB vsˇak pro nasˇi matici o rozmeˇrech 21 × 21 prvku˚ nenı´ schopen tyto matice spocˇ´ıtat. Vy´pocˇet vlastnıćh cˇ´ısel pomocı´ prˇ´ıkazu eig(P) uzˇ je bezproble´movy´. Bohuzˇel neˇktera´ vlastnı´ cˇ´ısla jsou komplexnı´, cozˇ da´le zteˇzˇuje ostatnı´ vy´pocˇty. Nalezenı´ Jordanova tvaru J matice prˇechodu a prˇ´ıslusˇne´ matice Q je tedy vy´pocˇetneˇ natolik komplikovane´, prˇedevsˇ´ım pro matice vysˇsˇ´ıch rˇa´du˚, zˇe se spokojı´me s klasicky´m umocnˇovańı´m matic. Jinou mozˇnostı´ by bylo prvnı´ vy´sledny´ vektor p(1) opeˇt na´sobit maticı´ prˇechodu P pro zı´skańı´ vektoru p(2). Po opeˇtovne´m na´sobenı´ pra´veˇ zı´skane´ho vektoru maticı´ P vznikne vektor p(3) atd. Pozna´mka. V na´sledujıćı´m textu jsou vy´stupu syste´mu Matlab psańy velikostı´ pı´sma pro indexy.


21

m=1: >> p1 = p0 * P^1 p1 = Columns 1 through 7 0

0.1667

0.1667

0.1667

0.1667

0.1667

0

0

0.1667

0

0

0

0

0

0

0

0

Columns 8 through 14 0

0

Columns 15 through 21 0

0

Vektor absolutnıćh pravdeˇpodobnostı´ po jednom hodu kostkou oznacˇ´ıme p1. Jak vidı´me z vy´sledku, jedna´ se o prvnı´ rˇa´dek matice prˇechodu. Po jednom hodu kostkou nezle hru dokoncˇit. m=2: >> p2 = p0 * P^2 p2 = Columns 1 through 7 0

0

0.0556

0.0556

0.0833

0.1111

0.1389

0.0556

0.0833

0.0278

0.0278

0.0278

0

0

0

0

0

Columns 8 through 14 0.1111

0.0833


0.1111

Po druhe´m hodu kostkou se figurka mu˚zˇe nale´zat na polıćh cˇ´ıslo 3 azˇ 16, prˇicˇemzˇ s nejveˇtsˇ´ı pravdeˇpodobnostı´ bude na poli 7. m=3: >> p3 = p0 * P^3 p3 = Columns 1 through 7 0

0

0.0787

0.0093

0.0185

0.0324

0.0509

0.0880

0.0926

0.0787

0.0417

0.0324

0.0370

0.0370

0.0324

0.0278

0.0185


0.0833


0.1296


22

Po trˇetı´m hodu kostkou je pravdeˇpodobnost dohrańı´ hry (absorpce) rovna

1 54 .


0

0.0648

0.0131

0.0147

0.0177

0.0231

0.0432

0.0679

0.1065

0.0571

0.0502

0.0594

0.0718

0.0687

0.0694

0.0625


0.0309


0.0918

S dalsˇ´ım tahem se pravdeˇpodobnost dohrańı´ hry zvysˇuje na

1 16 .


0

0.0328

0.0108

0.0130

0.0154

0.0184

0.0197

0.0352

0.0984

0.0414

0.0458

0.0701

0.0940

0.0986

0.1125

0.1227


0.0167


0.0781

Pravdeˇpodobnost vy´hry po pa´te´m hodu kostkou se blı´zˇ´ı 18 . Po sˇeste´m hodu se pravdeˇpodobnost prˇiblı´zˇ´ı k 15 . S dalsˇ´ımi hody se absolutnı´ pravdeˇpodobnost p20 (m) sta´le zvysˇuje. Po deseti hodech kostkou je pravdeˇpodobnost te´meˇrˇ 12 . m = 40 : >> p40 = p0 * P^40 p40 = Columns 1 through 7 0

0

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0008

0.0002

0.0002

0.0004

0.0006

0.0008

0.0020

0.9944


0.0000


0.0003


23

Po 40. tahu je hra dohrańa s pravdeˇpodobnostı´ vıće nezˇ 99 %. m = 80 : >> p80 = p0 * P^80 p80 = Columns 1 through 7 0

0

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

1.0000


0.0000


0.0000

S dalsˇ´ımi hody se pravdeˇpodobnost vy´hry sta´le vıće blı´zˇ´ı k 1. Cozˇ je podle veˇty 2.3 ocˇeka´vany´ vy´sledek. Vy´sledky MATLABu ukazujı´, zˇe po 80. hodu bude hra dohrańa s pravdeˇpodobnostı´ 100 %. To je ovsˇem dı´ky zaokrouhlovańı´ vy´pocˇetnı´ho syste´mu. Pokud se podı´va´me na hernı´ plań (obra´zek 1.2), vidı´me, zˇe hraćˇova figurka mu˚zˇe sta´t na poli 19 a sta´le se nedostat na pole 20. Existuje tedy pravdeˇpodobnost, zˇe hra nebude dohrańa ani po 80 hodech, ta je vsˇak te´meˇrˇ nulova´. Vy´voj pravdeˇpodobnosti absorpce, za prˇedpokladu vyćhozı´ho pole cˇ´ıslo 0, mu˚zˇeme vyja´drˇit i graficky. K sestavenı´ na´sledujıćı´ho grafu byl pouzˇit jazyk R.

pravdepodobnost absorpce

1.0

0.8

0.6

0.4

0.2

0.0 0

20

40

60

poradí hodu kostkou

Obra´zek 3.1: Pravdeˇpodobnost absorpce v cˇase m

80


3.4

24

Absorpcˇnı´ rˇeteˇzec

Podle teoreticke´ cˇa´sti 2.5 o absorpcˇnıćh homogennıćh markovskyćh rˇeteˇzcıćh nejdrˇ´ıve spocˇ´ıta´me fundamenta´lnı´ matici F. Prˇecˇ´ıslujeme stavy tak, jak je uvedeno v definici 2.16. Vznikne matice I* 0 P= , A N ktera´ bude pro nasˇi hru na´sledujıćı´: 

1 0  0  0   0  0  0  0  0  0   P = 0  0  0  0  0  0  1 6 1 6 1   61  6 1 6

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 6 6 6 6 6 0 0 16 61 16 16 61 0 0 61 16 16 61 0 0 0 61 16 61 0 0 0 0 16 61 0 0 0 0 0 16 0 16 0 0 0 0 0 16 0 0 0 0 0 16 0 0 0 0 0 16 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 61 0 0 0 0 0 0 0 16 0 0 0 0 1 1 6 0 0 6 0 0 0 0 1 1 6 6 0 0 0 0 0 0 1 1 1 6 6 6 0 0 0 0 0 1 1 1 1 6 6 6 6 0 0 0 0 1 1 1 1 6 6 6 6 0 0 0 0 0 61 16 16 16 0 0 0 0 0 61 16 16 16 0 0 0 0 0 61 16 16 61 16 0 0 0 0 61 16 61 16 0 0 0 0 0 16 61 16 0 0 0 0 0 0 61 16 0 0 0 0 0 0 0 61 0 0 0 0 61 0 0 0 0 0 0 0 61 0 0 0 0 0 0 0 61 0 0 0 0 0 0 0 61 0 0 0 0 0 0 0 61 0 0 0 0 0 0 0 61 0 0 0

0 0 0 0

0 0 0 0 1 0 6 1 6 0 1 6 0 1 6 0 1 6 0 1 6 0 0 0 1 6 0 1 6 1 6 1 6 1 6

1 6 1 6 1 6 1 6 1 6 1 6

0 0 0 0 0 0 0 0 0 0 0 0 1 6 1 6 1 6 1 6 1 6 1 6 1 3

0 0 0 0 0 0 0 0 0 0 0 0 0 1 6 1 6 1 6 1 6 1 6 1 6 1 2

0 0 0 0 0 0 0 0 0 0 0

 0 0  0  0   0  0  0  0  0  0   0  0  0  0  1 6 1 6 1 6 1  6 1  6 1 6 2 3

Cˇa´ry v matici oddeˇlujı´ jednotlive´ submatice I*, 0, A a N. Pro vy´pocˇet fundamenta´lnı´ matice je potrˇeba pouze submatice N, ktera´ se nacha´zı´ v prave´m dolnı´m rohu. Tato matice uda´va´ pravdeˇpodobnosti prˇechodu mezi neabsorpcˇnı´mi stavy. Tuto matici mu˚zˇeme pomocı´ MATLABu zı´skat i prˇed prˇecˇ´ıslovańı´m stavu˚ a to na´sledujıćı´m prˇ´ıkazem, ktery´ vra´tı´ matici bez poslednı´ho rˇa´dku a sloupce. >> N=P(1:20,1:20); Zjistı´me rˇa´d matice N, ktery´ pouzˇijeme prˇi tvorbeˇ jednotkove´ matice stejne´ho rˇa´du.


25

>> rad=size(N,1) rad = 20 >> I=eye(rad); Nynı´ jizˇ mu˚zˇeme spocˇ´ıtat fundamenta´lnı´ matici F pomocı´ na´sledujıćı´ho prˇ´ıkazu. >> F=inv(I-N); Opeˇt jsme zabrańili vypsańı´ matice pomocı´ symbolu strˇednı´k (;) na konci prˇ´ıkazu. Matice F na vy´stupu MATLABu zabı´ra´ mnoho mı´sta, na´s vsˇak zajı´ma´ prˇedevsˇ´ım prvnı´ rˇa´dek te´to matice. Ten uda´va´ strˇednı´ hodnotu pocˇtu okamzˇiku˚, ktere´ stra´vı´ rˇeteˇzec v neabsorpcˇnıćh stavech nezˇ bude absorbovań, prˇi prˇedpokladu, zˇe vysˇel ze stavu 0. Nynı´ vypı´sˇeme tento vektor, tvorˇ´ıcı´ prvnı´ rˇa´dek matice F. >> f0=F(1,:) f0 = Columns 1 through 7 1.0000

0.1667

0.4500

0.2694

0.3143

0.3667

0.2612

0.2446

0.5024

1.2904

0.3809

0.4030

0.6684

1.0025

1.2408

2.2911


0.2481


0.7973

Z vy´sledku vidı´me, zˇe rˇeteˇzec stra´vı´ ve stavu 0 v pru˚meˇru 1 okamzˇik, ve stavu 2 stra´vı´ 16 okamzˇiku atd. Nejvıće cˇasu stra´vı´ figurka na poli 19, a to te´meˇrˇ 2,3 okamzˇiku. To je zaprˇ´ıcˇineˇno vysokou pravdeˇpodobnostı´ setrvańı´ v na tomto poli. Po secˇtenı´ slozˇek vektoru f0 zı´ska´me pru˚meˇrny´ cˇas potrˇebny´ k dohrańı´ hry, zacˇ´ına´me-li na poli 0. >> cas=sum(f0) cas = 12.6448


26

K dohrańı´ hry je tedy potrˇeba pru˚meˇrneˇ necelyćh 13 hodu˚ kostkou. Podle veˇty 2.4 mu˚zˇeme jesˇteˇ spocˇ´ıtat pravdeˇpodobnosti prˇechodu do absorpcˇnı´ho stavu. Pro na´sˇ rˇeteˇzec, ktery´ ma´ pouze jeden absorpcˇnı´ stav, budou ale podle veˇty 2.3 pravdeˇpodobnosti uik rovny 1. Tento vy´pocˇet tedy budeme bra´t jako kontrolu. Nejprve z matice P zı´ska´me v MATLABu submatici A a pote´ dı´ky soucˇinu fundamenta´lnı´ matice F a matice A zı´ska´me matici U. Slozˇky te´to matice jsou pravdeˇpodobnosti uik . Matice A je v neprˇecˇ´ıslovane´ matici prˇechodu P prvnıćh 20 prvku˚ poslednı´ho sloupce. >> A=P(1:20,21); >> U=F*A U~= 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000

Vidı´me tedy, zˇe nasˇe vy´pocˇty byly spra´vne´. Z kazˇde´ho pole, na ktere´m se mu˚zˇe figurka ocitnout, bude absorbovańa polem 20 s pravdeˇpodobnostı´ 1.

3.5

Vy´sledky

Vy´sledky zı´skane´ pomocı´ vy´pocˇtu˚ z te´to kapitoly mu˚zˇeme shrnout do na´sledujıćıćh dvou tabulek. Jednotlive´ sloupce uda´vajı´ pravdeˇpodobnost absorpce po m hodech kostkou, za prˇedpokladu, zˇe se figurka nacha´zı´ na i-te´m poli. Jedna´ se o pravdeˇpodobnost prˇechodu ze stavu i do stavu 20 v cˇase m, proto tuto pravdeˇpodobnost oznacˇ´ıme pi,20 (m) pro i = 0, 1, . . . , 19. Poslednı´ rˇa´dek pak uda´va´ strˇednı´ hodnotu pocˇtu tahu˚ potrˇebnyćh k dohrańı´ hry, opeˇt za prˇedpokladu, zˇe se figurka nale´za´ na poli i.

i m 1 2 3 4 5 6 7 8 9 10 15 20 30 40 50 60 70 80 Ei

0 p0,20 (m) 0,0000 0,0000 0,0185 0,0625 0,1227 0,1982 0,2789 0,3566 0,4291 0,4955 0,7358 0,8637 0,9639 0,9905 0,9975 0,9993 0,9998 1,0000 12,6448

1 p1,20 (m) 0,0000 0,0000 0,0231 0,0687 0,1322 0,2108 0,2918 0,3688 0,4404 0,5059 0,7416 0,8667 0,9647 0,9907 0,9975 0,9993 0,9998 1,0000 12,4871

2 p2,20 (m) 0,0000 0,0000 0,0278 0,0756 0,1443 0,2256 0,3065 0,3827 0,4534 0,5177 0,7481 0,8701 0,9656 0,9909 0,9976 0,9994 0,9998 1,0000 12,3062

4 p4,20 (m) 0,0000 0,0278 0,0648 0,1211 0,2006 0,2830 0,3605 0,4327 0,4990 0,5587 0,7703 0,8816 0,9687 0,9917 0,9978 0,9994 0,9998 1,0000 11,5899

5 p5,20 (m) 0,0000 0,0278 0,0648 0,1312 0,2157 0,2981 0,3749 0,4464 0,5116 0,5701 0,7765 0,8848 0,9695 0,9919 0,9979 0,9994 0,9999 1,0000 11,4130

6 p6,20 (m) 0,0000 0,0278 0,0602 0,1258 0,2073 0,2876 0,3645 0,4367 0,5026 0,5619 0,7720 0,8825 0,9689 0,9918 0,9978 0,9994 0,9998 1,0000 11,5406

Tabulka 3.1: Vy´sledky cˇa´st 1

3 p3,20 (m) 0,0000 0,0278 0,0694 0,1181 0,1906 0,2716 0,3493 0,4219 0,4888 0,5494 0,7651 0,8789 0,9680 0,9915 0,9978 0,9994 0,9998 1,0000 11,7212

7 p7,20 (m) 0,0000 0,0278 0,0694 0,1481 0,2334 0,3138 0,3900 0,4606 0,5244 0,5815 0,7826 0,8880 0,9704 0,9922 0,9979 0,9995 0,9999 1,0000 11,2206

8 p8,20 (m) 0,0000 0,0278 0,0833 0,1728 0,2591 0,3390 0,4141 0,4829 0,5446 0,5997 0,7924 0,8931 0,9717 0,9925 0,9980 0,9995 0,9999 1,0000 10,9127

9 p9,20 (m) 0,0000 0,0000 0,0833 0,1813 0,2689 0,3499 0,4254 0,4936 0,5546 0,6087 0,7974 0,8957 0,9724 0,9927 0,9981 0,9995 0,9999 1,0000 10,8020

Kapitola 3. Hadi a zˇebrˇ´ıky jako homogennı´ markovsky´ rˇeteˇzec 27

i m 1 2 3 4 5 6 7 8 9 10 15 20 30 40 50 60 70 80 Ei

10 p10,20 (m) 0,0000 0,0278 0,1250 0,2215 0,3061 0,3845 0,4570 0,5220 0,5798 0,6311 0,8093 0,9018 0,9740 0,9931 0,9982 0,9995 0,9999 1,0000 10,3517

11 p11,20 (m) 0,0000 0,0833 0,2037 0,3048 0,3908 0,4666 0,5331 0,5912 0,6421 0,6867 0,8388 0,9171 0,9781 0,9942 0,9985 0,9996 0,9999 1,0000 9,3007

12 p12,20 (m) 0,0000 0,1111 0,2315 0,3272 0,4104 0,4838 0,5481 0,6044 0,6537 0,6968 0,8440 0,9198 0,9788 0,9944 0,9985 0,9996 0,9999 1,0000 9,0650

14 p14,20 (m) 0,0000 0,1389 0,2454 0,3387 0,4212 0,4933 0,5564 0,6116 0,6600 0,7023 0,8469 0,9213 0,9792 0,9945 0,9985 0,9996 0,9999 1,0000 8,9254

15 p15,20 (m) 0,1667 0,2778 0,3657 0,4444 0,5138 0,5743 0,6273 0,6737 0,7143 0,7499 0,8714 0,9338 0,9825 0,9954 0,9988 0,9997 0,9999 1,0000 7,6504

Tabulka 3.2: Vy´sledky cˇa´st 2

13 p13,20 (m) 0,0000 0,1389 0,2546 0,3457 0,4268 0,4983 0,5608 0,6155 0,6634 0,7053 0,8484 0,9220 0,9794 0,9945 0,9986 0,9996 0,9999 1,0000 8,8629

16 p16,20 (m) 0,1667 0,2778 0,3657 0,4444 0,5138 0,5743 0,6273 0,6737 0,7143 0,7499 0,8714 0,9338 0,9825 0,9954 0,9988 0,9997 0,9999 1,0000 7,6504

17 p17,20 (m) 0,1667 0,2778 0,3657 0,4444 0,5138 0,5743 0,6273 0,6737 0,7143 0,7499 0,8714 0,9338 0,9825 0,9954 0,9988 0,9997 0,9999 1,0000 7,6504

18 p18,20 (m) 0,1667 0,2778 0,3657 0,4444 0,5138 0,5743 0,6273 0,6737 0,7143 0,7499 0,8714 0,9338 0,9825 0,9954 0,9988 0,9997 0,9999 1,0000 7,6504

19 p19,20 (m) 0,1667 0,2778 0,3657 0,4444 0,5138 0,5743 0,6273 0,6737 0,7143 0,7499 0,8714 0,9338 0,9825 0,9954 0,9988 0,9997 0,9999 1,0000 7,6504

Kapitola 3. Hadi a zˇebrˇ´ıky jako homogennı´ markovsky´ rˇeteˇzec 28

Kapitola 4 Dva hraćˇi, strategie 4.1

Dva hraćˇi

Uvazˇujme hru hadi a zˇebrˇ´ıky, kterou hrajı´ dva hraćˇi, prˇicˇemzˇ kazˇdy´ z hraćˇu˚ ma´ jednu figurku. Nutno rˇ´ıci, zˇe z pohledu teorie her se sta´le jedna´ o hru jednoho hraćˇe, jı´mzˇ je prˇ´ıroda. Ta rozhoduje o pocˇtu ok na kostce (strategii) a hrajıćı´ osoby pak pouze posunujı´ sve´ figurky. Pozna´mka. V na´sledujıćı´m textu nebudou hraćˇi vnı´mańi z pohledu teorie her, nebude-li to zdu˚razneˇno. Budou to osoby posouvajıćı´ kazˇda´ svou figurku. Prˇipomenˇme pravidla klasicke´ hry, kdy hraćˇ, jehozˇ figurka se po tahu ocitne na poli obsazene´m jiny´m hraćˇem (protihraćˇem), takzvaneˇ vyhodı´ tuto protihraćˇovu figurku. Ta je prˇesunuta na startovnı´ pole. Pozna´mka. Startovnı´m polem u hernı´ho plańu na obra´zku 1.2 je mysˇleno pole, jenzˇ je oznacˇeno cˇ´ıslem 0. V kazˇde´m kole existuje pravdeˇpodobnost, zˇe jeden z hraćˇu˚ bude vyhozen. Pozna´mka. Kolem nazveˇme tah obou hraćˇu˚. Je-li hraćˇu˚ vıće, pak vsˇech hraćˇu˚. Tedy vsˇichni hraćˇi hodı´ kostkou a na´sledneˇ posunou svou figurku. Vy´sˇe popsanou situaci lze rˇesˇit neˇkolika zpu˚soby, ktere´ jsou vsˇak pomeˇrneˇ komplikovane´, a proto si pouze uka´zˇeme jak postupovat prˇi jejich rˇesˇenı´. Prˇedpokla´dejme, zˇe jsme hraćˇem, ktery´ je pra´veˇ na tahu, ha´zı´me tedy kostkou a na´sledneˇ prˇesouva´me nasˇi figurku. Po tomto tahu je nasˇe figurka na poli j s pravdeˇpodobnostı´ p j . Figurka protihraćˇe se nacha´zı´ na poli i s pravdeˇpodobnostı´ pi . V prˇ´ıpadeˇ 0 < j − i ≤ 6, mu˚zˇeme by´t protihraćˇem vyhozeni s pravdeˇpodobnostı´ p j,0 = 16 . Obecneˇ je tato pravdeˇpodobnost prˇechodu (vyhozenı´) p j,0 =

1 1 1 1 1 1 p i + p i +1 + p i +2 + p i +3 + p i +4 + p i +5 6 6 6 6 6 6

pro i, j ∈ J takova´, zˇe rozdı´l j − i ∈ [1; 6], kde p oznacˇuje pravdeˇpodobnosti vy´skytu figurky druhe´ho hraćˇe. Pokud nenı´ rozdı´l j − i z intervalu [1; 6], pravdeˇ– 29 –

Kapitola 4. Dva hraćˇi, strategie

30

podobnost, zˇe budeme vyhozeni, je nulova´. Vy´jimkou jsou situace, kdy stojı´me na konci hada cˇi zˇebrˇ´ıku a protihraćˇ ma´ mozˇnost vyhodit nasˇi figurku s jejich pomocı´. V tomto prˇ´ıpadeˇ existuje nenulova´ pravdeˇpodobnost, zˇe budeme vyhozeni, prˇestozˇe j − i ∈ / [1; 6]. Interval [1; 6] nenı´ vzˇdy spolehlivy´ ani v prˇ´ıpadeˇ, zˇe se mezi poli i a j nale´za´ zacˇa´tek zˇebrˇ´ıku cˇi hada, jelikozˇ tato pole nejsou cˇ´ıslovańa. Pokud po nasˇem tahu vyhodı´me protihraćˇe my, nic se pro na´s nemeˇnı´. Matici prˇechodu tedy nijak neovlivnı´me. Proble´mem vsˇak je, zˇe nezna´me rozlozˇenı´ pravdeˇpodobnosti, s jaky´m se druhy´ hraćˇ pohybuje na hernı´m plańu. ˇ esˇenı´m by bylo sestavit soustavu rovnic a nerovnic pro kazˇdy´ ze stavu˚ a kazˇdy´ R rozdı´l j − i a toto rozlozˇenı´ se pokusit odhadnout. Pote´ sestavit matici prˇechodu P s vypocˇ´ıtany´mi pravdeˇpodobnostmi prˇechodu p j,0 pro j ∈ J \ {20} a ostatnı´ pravdeˇpodobnosti prˇechodu upravit tak, aby byl soucˇet prvku˚ jednotlivyćh rˇa´dku˚ roven 1. Pravdeˇpodobnost prˇechodu p20,0 = 0, jelikozˇ pole 20 je absorpcˇnı´ stav. Zˇa´dne´ho hraćˇe tedy nelze z tohoto pole vyhodit. Nedostatkem modelu je vsˇak fakt, zˇe nezahrnuje mozˇnost vy´hry protihraćˇe. Druhy´ hraćˇ je tak spı´sˇe pouze dalsˇ´ım negativnı´m faktorem (spolu s hady), ktery´ se na´m pokousˇ´ı zabrańit v dohrańı´ hry. Prˇ´ıklad: Uvazˇujme, zˇe pohyb druhe´ho hraćˇe lze popsat rovnomeˇrny´m rozlozˇenı´m pravdeˇpodobnosti (a nemu˚zˇe vyhra´t hru). Sestavte matici prˇechodu P a vypocˇteˇte strˇednı´ hodnotu pocˇtu okamzˇiku˚, ktere´ rˇeteˇzec stra´vı´ v neabsorpcˇnıćh stavech. Rˇesˇenı´: Protihraćˇ se mu˚zˇe pohybovat na dvaceti polıćh, tedy pravdeˇpodobnost, 1 1 , p j,0 = 20 pro j ∈ J \ {20}. Ostatnı´ zˇe budeme vyhozeni po nasˇem tahu je 20 pravdeˇpodobnosti prˇechodu v jednotlivyćh rˇa´dcıćh snı´zˇ´ıme celkem o tuto hodnotu. Vy´pocˇet strˇednı´ hodnoty pocˇtu tahu˚ potrˇebnyćh k dohrańı´ hry vypocˇ´ıta´me stejneˇ jako v kapitole 3, sekce 3.4. Nejdrˇ´ıve zadefinujeme matici prˇechodu v syste´mu MATLAB, pote´ vypı´sˇeme submatici N s prˇechody mezi neabsorpcˇnı´mi stavy a s jejı´ pomocı´ vypocˇ´ıta´me fundamenta´lnı´ matici F. Za prˇedpokladu, zˇe vyćhozı´ stav je pole cˇ´ıslo 0, je strˇednı´ hodnota tahu˚ potrˇebnyćh k dohrańı´ hry te´meˇrˇ 16. Na poli 0 pak hraćˇ stra´vı´ necelyćh 1,8 okamzˇiku˚. Tyto u´daje zjistı´me z prvnı´ho rˇa´dku fundamenta´lnı´ matice. Samotna´ strˇednı´ hodnota pocˇtu okamzˇiku˚ stra´venyćh v neabsorpcˇnıćh stavem je soucˇtem prvku˚ prvnı´ho rˇa´dku fundamenta´lnı´ matice F. Doplnˇme, zˇe hru lze dohra´t za pouhe´ trˇi tahy s pravdeˇpodobnostı´ 0,0159. Matice prˇechodu P vypada´ na´sledovneˇ.

P=

0

20 1  20 1  20 1  20 1  20 1  20 1  20 1  20 1  20 1   20 1  20 1  20 1  20 1  20 1  20 1  20 1   20 1  20 1  20 1 20

1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 120

0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0 0 0 0

19 120 19 120

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0

0 0 0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0 0

19 120 19 120 19 120

0

19 120 19 120 19 120 19 120 19 120 19 120

0 0 0

19 120 19 120 19 120 19 120

0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

19 120 19 120 19 120 19 120

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

19 120 19 120 19 120 19 120

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0

19 120 19 120 19 120 19 120 19 120

0

19 120 19 120 19 120 19 120 19 120 19 120

0 0 0

0 0 0

19 120 19 120 19 120 19 120 19 120 19 120 38 120

19 120 19 120 19 120 19 120 19 120 19 120

0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0

19 120 19 120 19 120 19 120 19 120 19 120 57 120

0 0 0 0 0 0 0 0 0 0 0 0

0

19 120 19 120 19 120 19 120 19 120 19 120 76 120

0 0 0 0 0 0 0 0 0 0 0 0 0



1

120

                             19   120  19  120  19  120  19  120  19 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Kapitola 4. Dva hraćˇi, strategie 31

Kapitola 4. Dva hraćˇi, strategie

32

K tomu, abychom mohli do vy´pocˇtu zahrnout i mozˇnost vy´hry protihraćˇe na´m vsˇak klasicka ´ matice prˇechodu nestacˇ´ı. Museli bychom vytvorˇit matici se stavy J × J − id j ∪ {(0, 0) , (20, 20)}, kde J = {0, 1, . . . , 20}, id j = ( j, j) pro j ∈ J. Cˇlen id j tedy odstranı´ ty prˇ´ıpady, kdy by se figurky obou hraćˇu˚ nale´zaly na jednom poli. Vy´jimkou jsou pole 0 a 20, na kteryćh se mohou oba hraćˇi dle pravidel nale´zat soucˇasneˇ. Jednotlive´ stavy tedy budou dvojice polı´ (i, j). Tuto novou matici bychom pak rozcˇlenili na submatice podobne´ matici P z prˇedchozı´ho prˇ´ıkladu. Pravdeˇpodobnosti prˇechodu v teˇchto submaticıćh vsˇak budou za´visle´ na pozici obou figurek. Vektor pocˇa´tecˇnıćh pravdeˇpodobnostı´ pak bude obdobny´ jako v kapitole 3 a navıć pro oba hraćˇe spolecˇny´. Na zacˇa´tku hry se oba hraćˇi budou nale´zat na poli nula, tedy p(0,0) (0) = 1, ostatnı´ pravdeˇpodobnosti budou nulove´. p(0) = (1, 0, 0, 0, . . . , 0) Vektory absolutnıćh pravdeˇpodobnostı´, ktere´ bychom zı´skali obdobny´m vy´pocˇtem jako v kapitole 3, by uda´valy pravdeˇpodobnost pro oba hraćˇe. Tedy vzˇdy po odehrańı´ cele´ho kola, tj. po tahu obou hraćˇu˚.

4.2

Strategie

Na za´veˇr te´to praće jesˇteˇ uvazˇujme jednu hrajıćı´ osobu s dveˇmi figurkami. Z pohledu teorie her se jedna´ o dva hraćˇe. Jednı´m hraćˇem je opeˇt prˇ´ıroda, ta volı´ ze svyćh strategiı´, ktery´mi jsou pocˇty ok na hracı´ kostce. Druhy´ hraćˇ dle teorie her, osoba s figurkami, mu˚zˇe take´ vybı´rat z mnozˇiny svyćh strategiı´. Po kazˇde´m hodu kostkou se mu˚zˇe tento hraćˇ rozhodnout, kterou figurkou pota´hne. Zejmeńa se mu˚zˇe pokusit vyhnout hadu˚m a vyuzˇ´ıt co nejvıće zˇebrˇ´ıky. Prˇi volbeˇ strategie mu˚zˇe hraćˇ vyuzˇ´ıt vy´sledky shrnute´ v tabulkaćh 3.1 a 3.2, ktere´ mu pomohou k nejlepsˇ´ımu mozˇne´mu vy´sledku. Tı´m je dohrańı´ hry s obeˇma figurkami na nejnizˇsˇ´ı pocˇet tahu˚. Oznacˇme E1i strˇednı´ hodnotu pocˇtu okamzˇiku˚, ktere´ stra´vı´ prvnı´ figurka v nej

absorbcˇnıćh stavech, pokud se nacha´zı´ na poli i. E2 je tato hodnota pro druhou figurku nacha´zejıćı´ se ve stavu j. Soucˇet teˇchto strˇednıćh hodnot pak oznacˇme Ei,j . j

Ei,j = E1i + E2 Po hodu kostkou mu˚zˇe hraćˇ posunout svou 1. figurku na pole k a druhou na pole l. Po tahu tedy mohou nastat dveˇ mozˇnosti soucˇtu strˇednıćh hodnot pocˇtu okamzˇiku˚ potrˇebyćh k dohrańı´ hry. j

Ek,j = E1k + E2

a

Ei,l = E1i + E2l

Porovnańı´m teˇchto hodnot Ek,j a Ei,l mu˚zˇe hraćˇ urcˇit, zda je pro neˇj lepsˇ´ı ta´hnou prvnı´ cˇi druhou figurkou.

Seznam pouzˇite´ literatury [1] OSBORNE, Martin J. a Ariel RUBINSTEIN. A course in game theory. Cambridge, Mass.: MIT Press, c1994, xv, 352 p. ISBN 02-626-5040-1. [2] OSBORNE, Martin J. An introduction to game theory. New York: Oxford University Press, 2004, xvii, 533 s. ISBN 978-0-19-512895-6. ˇ ENA ˇ , Vaćlav. Stochasticke´ procesy. 2. prˇeprac. vyd. Praha: Vysoka´ sˇkola ´R [3] KOR ekonomicka´ v Praze, 2010, 227 s. ISBN 978-802-4516-462. ´ SˇKOVA ´ , Zuzana a Petr LACHOUT. Za´klady na´hodnyćh procesu˚. 2. dotisk [4] PRA 1. vyd. Praha: Karolinum, 2005, 146 s. ISBN 80-718-4688-0. [5] MANDL, Petr. Pravdeˇpodobnostnı´ dynamicke´ modely. Praha: Academia, 1985 ´ vod do finitnı´ [6] KEMENY, John G., J. Laurie SNELL a Gerald L. THOMPSON. U matematiky. vyd. 1. Praha: SNTL, 1971, 469 s. ´ SˇEK, Josef a Zdeneˇk TICHY´. Za´klady aplikovane´ matematiky III. Praha: [7] SˇKRA SNTL, 1990, 853 s. ISBN 80-030-0111-0. ´ , Petra. Sbı´rka prˇ´ıkladu˚ z markovskyćh rˇeteˇzcu˚ (s vyuzˇitı´m MAT[8] CABALKOVA LABu) [online]. 2011 [cit. 2012-05-19]. Bakala´rˇska´ praće. Masarykova univerzita, Prˇ´ırodoveˇdecka´ fakulta. Vedoucı´ praće Marie Budı´kova´. Dostupne´ z: http://is.muni.cz/th/324014/prif_b/. [9] SˇMERDA, Stanislav. Sbı´rka rˇesˇenyćh u´loh z aplikacı´ stochastickyćh modelu˚ [online]. 2008 [cit. 2012-05-19]. Diplomova´ praće. Masarykova univerzita, Fakulta informatiky. Vedoucı´ praće Marie Budı´kova´. Dostupne´ z: http://is.muni. cz/th/39247/fi_m/. ´ CˇEK. Jak pracovat s MATLABem [online]. [cit. 2012[10] ZELINKA, Jirˇ´ı a Jan KOLA 05-20]. Dostupne´ z: http://www.math.muni.cz/~kolacek/vyuka/vypsyst/ navod.pdf [11] Symbolic Math Toolbox. In: Documentation [online]. Natick, Massachusetts: c 1984-2012 [cit. 2012-05-27]. Dostupne´ z: http://www. The MathWorks, Inc., mathworks.com/help/toolbox/symbolic/ – 33 –

Seznam pouzˇite´ literatury

34

[12] Snakes and Ladders. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2012-05-27]. Dostupne´ z: http://en. wikipedia.org/wiki/Chutes_and_Ladders ´ , Katerˇina. Vyúka jazyka R [online]. 2010 [cit. 2012-05-20]. [13] KONECˇNA Bakala´rˇska´ praće. Masarykova univerzita, Prˇ´ırodoveˇdecka´ fakulta. Vedoucı´ praće Jan Kolaćˇek. Dostupne´ z: http://is.muni.cz/th/270073/prif_b/.

MASARYKOVA UNIVERZITA

Recommend Documents