Markovovy ˇretˇezce

Markovovy ˇ retˇ ezce

Mirko Navara

Centrum strojov´ eho vn´ım´ an´ı katedra kybernetiky FEL ˇ CVUT Karlovo n´ amˇ est´ı, budova G, m´ıstnost 104a

http://cmp.felk.cvut.cz/˜navara/stat 15. ledna 2021

Obsah

1 O ˇcem to m˚uˇze b´yt? 1

2 Matematick´y model: (homogenn´ı) Markovovy ˇretˇezce (Markov chains) 3

3 Pravdˇepodobnosti stav˚u 4

3.1 Pˇr´ıklady na pravdˇepodobnosti stav˚u . . . 4

3.2 Permutace stav˚u . . . 8

4 Klasifikace stav˚u Markovov´ych ˇretˇezc˚u s koneˇcnˇe mnoha stavy 8 5 Asymptotick´e chov´an´ı Markovov´ych ˇretˇezc˚u s koneˇcnˇe mnoha stavy 12 5.1 Pˇrechodn´e stavy . . . 12

5.2 Nerozloˇziteln´e Markovovy ˇretˇezce . . . 14

5.3 Rozloˇziteln´e Markovovy ˇretˇezce . . . 16

5.4 Pˇr´ıklady . . . 16

6 Reverzibilita 17 6.1 Odhady parametr˚u Markovov´ych ˇretˇezc˚u . . . 17

6.2 Obr´acen´ı ˇcasov´e osy (zpˇetn´y chod) . . . 18

6.3 Jak lze luˇstit ˇsifry 1: model . . . 20

6.4 Jak lze luˇstit ˇsifry 2: rozluˇstˇen´ı . . . 21

6.5 Metropolis˚uv algoritmus . . . 22

7 Markovovy ˇretˇezce s nekoneˇcnˇe mnoha stavy 24 8 Pˇr´ıklady aplikac´ı 24 9 Co zde nebylo 25 9.1 Kdy se vr´at´ıme do stejn´eho stavu? . . . 25

9.2 Nehomogenn´ı Markovovy ˇretˇezce . . . 25

9.3 Markovovy procesy . . . 25

10 Dodatek: Mocniny stochastick´ych matic ˇr´adu 2 25

1 O ˇ cem to m˚ uˇ ze b´ yt?

Pˇr´ıklad(basketbal). [MN: PMS] Alice a Bob se stˇr´ıdavˇe strefuj´ı m´ıˇcem do koˇse, zaˇc´ın´a Alice. Kdo se prvn´ı stref´ı, vyhr´av´a. Alice se stref´ı s pravdˇepodobnost´ıa, Bob s pravdˇepodobnost´ıb. Jak´a je pravdˇepodobnost v´ysledk˚u hry?

Reˇˇ sen´ı. Po prvn´ım hodu s pravdˇepodobnost´ıaAlice vyhr´av´a, s pravdˇepodobnost´ı1−ase pokraˇcuje. Po 2. hodu hra skonˇc´ı v´yhrou Boba s pravdˇepodobnost´ı(1−a)b, nebo je situace stejn´a jako na zaˇc´atku a ˇsance se dˇel´ı ve stejn´em pomˇeru, tj.a: (1−a)b. Alice vyhraje s pravdˇepodobnost´ı

a

a+ (1−a)b = a a+b−a b, Bob s pravdˇepodobnost´ı

(1−a)b

a+ (1−a)b = (1−a)b a+b−a b.

(Pˇredpokl´ad´ame, ˇze aspoˇn jedna z pravdˇepodobnost´ıa, bje nenulov´a. V´ıce viz [MN: PMS].)

1 2 3 4

1 a

1−a

b

1−b

1

M˚uˇzeme sdruˇzit 2 kroky do jednoho.

1 2 4

1 a

(1−a)(1−b) (1−a)b

1

Pˇr´ıklad(foton). [MN: PMS] Foton vnikne do tenk´e vrstvy s rovnobˇeˇzn´ymi stˇenami. Na jej´ım rozhran´ı m˚uˇze proj´ıt, nebo se odraz´ı a dojde k druh´emu rozhran´ı, kter´ym projde, nebo se odraz´ı atd. Vypoˇctˇete pravdˇepodobnosti pr˚uchodu fotonu do jednotliv´ych poloprostor˚u vymezen´ych touto vrstvou.

Reˇˇ sen´ı. Jde o pˇr´ıklad

”basketbal“ v jin´e interpretaci. Obdobn´a ´uloha se ˇreˇs´ı pˇri programov´an´ı barevn´ych tisk´aren.

Pˇr´ıklad(shoda v tenisu). Alice s Bobem hraj´ı tenis, doˇslo ke shodˇe, takˇze hru vyhraje hr´aˇc, kter´y jako prvn´ı vyhraje o 2 m´ıˇce v´ıc neˇz soupeˇr. Alice vyhraje m´ıˇc s pravdˇepodobnost´ıc. Jak´e jsou pravdˇepododobnosti v´ysledk˚u hry? Jak´e rozdˇelen´ı a stˇredn´ı hodnotu m´a poˇcet m´ıˇc˚u hry?

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1

Reˇˇ sen´ı. Sdruˇz´ıme 2 kroky do jednoho: Po 2 m´ıˇc´ıch bud’ vyhraje Alice (s pravdˇepodobnost´ıa=c²), nebo Bob (s pravdˇepodobnost´ı(1−c)²), nebo bude opˇet shoda. Jde o pˇr´ıklad

”basketbal“, kde a=c², (1−a)b= (1−c)².

1 3 5

1

c²

2c(1−c) (1−c)²

1

Alice vyhraje s pravdˇepodobnost´ı c²

c²+ (1−c)², napˇr. pro c= 2/3 s pravdˇepodobnost´ı4/5. Takto bychom vˇsak nevyˇreˇsili v´ysledek hry od jej´ıho poˇc´atku (m´ısto od shody), setu, z´apasu, turnaje... [Papoulis, Pillai 2002]

Pˇr´ıklad(informaˇcn´ı kan´al se zpˇetnou vazbou). Odes´ılatel poˇsle zpr´avu v k´odu, dovoluj´ıc´ım odhalit chyby v pˇrenosu. (Pro jednoduchost zanedb´av´ame riziko nerozpoznan´e chyby.) Zpr´ava je doruˇcena spr´avnˇe s pravdˇepo- dobnost´ıc. Pˇr´ıjemce za stejn´ych podm´ınek poˇsle zpˇet (jednobitovou) zpr´avu o ´uspˇeˇsnosti pˇrijet´ı. Chybn´a zpr´ava

o spr´avn´em pˇrenosu vypad´a stejnˇe jako spr´avn´a zpr´ava o chybn´em pˇrenosu. V tˇechto pˇr´ıpadech se pˇrenos opa- kuje za stejn´ych podm´ınek. Chybn´a zpr´ava o chybn´em pˇrenosu vypad´a stejnˇe jako spr´avn´a zpr´ava o spr´avn´em pˇrenosu. V tˇechto pˇr´ıpadech pˇrenos konˇc´ı; pˇrijat´a zpr´ava m˚uˇze b´yt spr´avn´a nebo chybn´a.

Jak´e jsou pravdˇepodobnosti ukonˇcen´ı spr´avn´ym/chybn´ym pˇrijet´ım zpr´avy?

Reˇˇ sen´ı. Jde opˇet o pˇr´ıklad

”shoda v tenisu“, resp.

”basketbal“.

Dalˇs´ı ot´azky:Jak´e je rozdˇelen´ı d´elky komunikace; jej´ı stˇredn´ı hodnota a d˚uleˇzit´e kvantily?

Ot´azky:Jak´e je asymptotick´e chov´an´ı syst´emu? Jak z´avis´ı na poˇc´ateˇcn´ım stavu?

2 Matematick´ y model: (homogenn´ı) Markovovy ˇ retˇ ezce (Markov chains)

Doporuˇcen´a literatura: [Hsu 1996, Papoulis, Pillai 2002, Wasserman 2004].

Posloupnost diskr´etn´ıch n´ahodn´ych veliˇcin X₀, X₁, X₂, . . . s hodnotami ze spoˇcetn´e mnoˇziny stav˚u, obvykle {1,2, . . .}.

Indexov´ana je diskr´etn´ım ˇcasems hodnotami z mnoˇzinyN0={0,1,2, . . .}.

Z hlediskaokamˇzikut rozliˇsujememinulost(< t) abudoucnost(> t).

D´ano:

Pravdˇepodobnosti poˇc´ateˇcn´ıch stav˚u (=rozdˇelen´ı n´ahodn´e veliˇcinyX0), pi(0) =pX₀(i),

popˇr. dan´y poˇc´ateˇcn´ı stavk, tj.

pi(0) =δik=

1 proi=k, 0 proi6=k, pravdˇepodobnosti pˇrechodu ze stavuido stavuj v jednom kroku,

pij =P(Xt+1=j|Xt=i),

(nez´avisl´e na ˇcaset); pro koneˇcnˇe mnoho stav˚u je lze popsatmatic´ı pˇrechodu

P =







p₁₁ · · · p_1n ... . .. ... p_n1 · · · p_nn





,

kter´a jestochastick´a(=m´a jednotkov´e ˇr´adkov´e souˇcty),

∀i= 1, . . . , n:

n

X

j=1

pij = 1. Homogenn´ı: Matice pˇrechodu nez´avis´ı na ˇcase.

Retˇˇ ezce: S diskr´etn´ım ˇcasem a diskr´etn´ımi stavy; pro spojit´y ˇcas dost´av´ame Markov˚uv proces (Markov process).

Markovovy: Pravdˇepodobnost budouc´ıch stav˚u je plnˇe urˇcena souˇcasn´ym stavem, bez ohledu na minul´e stavy, P(Xt+1=j|Xt=it, Xt−1=it−1, . . . , X0=i0) =P(Xt+1=j|Xt=it) =pi_tj.

(Stav nese

”dostateˇcnou informaci“ o pˇredchoz´ım pr˚ubˇehu.)

To jepodm´ınˇen´a nez´avislostbudouc´ıho a minul´eho stavu pˇri dan´em souˇcasn´em stavu: prou < t < va libovoln´e stavyi, j, k

P(X_u=i, X_v=k|X_t=j) =P(X_u=i|X_t=j)·P(X_v=k|X_t=j).

3 Pravdˇ epodobnosti stav˚ u

Pravdˇepodobnosti stav˚u vyjadˇruje na poˇc´atku ˇr´adkov´y vektor

p(0) = (p1(0), . . . , pn(0)) = (pX₀(1), . . . , pX₀(n)), d´ale se vyv´ıjej´ı podle rekurentn´ıho vzorce

p(t+ 1) =p(t)P, pj(t+ 1) =X

i

pi(t)pij, p(t+u) =p(t)P^u, p_j(t+u) =X

i

p_i(t)p_ij(u), p(u) =p(0)P^u, p_j(u) =X

i

p_i(0)p_ij(u),

kde prvky maticeP^tznaˇc´ımepij(t) (6=p^t_ij), coˇz je pravdˇepodobnost pˇrechodu ze stavuido stavujvtkroc´ıch.

Chapmanova-Kolmogorovova rovnice:

P^t+u=P^tP^u, pkj(t+u) =X

i

pki(t)pij(u), kde sˇc´ıt´ame pˇres vˇsechny moˇzn´e stavyiv ˇcaset.

Princip superpozice (=linearita):Pokud jsou poˇc´ateˇcn´ı pravdˇepodobnostip(0) konvexn´ı kombinac´ı (=smˇes´ı) rozdˇelen´ı,

p(0) =cq(0) + (1−c)r(0), c∈ h0,1i,

jsou pozdˇejˇs´ı pravdˇepodobnosti d´any stejnou konvexn´ı kombinac´ı pravdˇepodobnost´ı jednotliv´ych sloˇzek, p(u) =p(0)P^u=cq(0)P^u+ (1−c)r(0)P^u=cq(u) + (1−c)r(u).

D˚usledek. Staˇc´ı n´am vyˇsetˇrit pˇr´ıpady, kdy poˇc´ateˇcn´ı stav je dan´y (=Diracovo rozdˇelen´ı).

3.1 Pˇ r´ıklady na pravdˇ epodobnosti stav˚ u

Pˇr´ıklad(otevˇren´e restaurace). Pij´ak se pohybuje Sklonˇenou ulic´ı mezi dvˇema restauracemi. Pˇred kaˇzd´ymi dveˇrmi, kter´e nevedou do restaurace, se rozhodne, kter´ym smˇerem se vyd´a; s pravdˇepodobnost´ıc p˚ujde z kopce, s pravdˇepodobnost´ı1−c do kopce.Aˇz najde restauraci, z˚ustane v n´ı. Jak´e jsou pravdˇepodobnosti dosaˇzen´ı obou restaurac´ı? (Jednodimenzion´aln´ı n´ahodn´a proch´azka s absorpˇcn´ımi bari´erami.) ˇReˇste speci´alnˇe pro restau- race ve vzd´alenosti 2 od v´ychoz´ı polohy.

Reˇˇ sen´ı. Jde opˇet o pˇr´ıklad

”shoda v tenisu“, resp.

”basketbal“.

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1

P =













1 0 0 0 0

c 0 1−c 0 0

0 c 0 1−c 0

0 0 c 0 1−c

0 0 0 0 1













, P²=













1 0 0 0 0

c c(1−c) 0 (1−c)² 0

c² 0 2c(1−c) 0 (1−c)²

0 c² 0 c (1−c) 1−c

0 0 0 0 1











 .

Napˇr. pro c= 0.7dost´av´ame

P =













1 0 0 0 0

0.7 0 0.3 0 0

0 0.7 0 0.3 0

0 0 0.7 0 0.3

0 0 0 0 1











 ,

P²=













1 0 0 0 0

0.7 0.21 0 0.09 0

0.49 0 0.42 0 0.09

0 0.49 0 0.21 0.3

0 0 0 0 1











 ,

P¹⁰=













1 0 0 0 0

0.945 56 6.534 6·10⁻³ 0 2.800 5·10⁻³ 4.510 3·10⁻²

0.833 79 0 1.306 9·10⁻² 0 0.153 14

0.572 98 1.524 7·10⁻² 0 6.534 6·10⁻³ 0.405 24

0 0 0 0 1











 ,

0 0 1 0 0

P = 0 0.7 0 0.3 0 , 0 0 1 0 0

P²= 0.49 0 0.42 0 0.09 , 0 0 1 0 0

P¹⁰= 0.833 79 0 1.306 9·10⁻² 0 0.153 14 , 0 0 1 0 0

P³⁰= 0.844 83 0 2.232 2·10⁻⁶ 0 0.155 17 ,

t→∞lim 0 0 1 0 0

P^t=

c²

c²+(1−c)² 0 0 0 _c2^(1−c)2

+(1−c)²

= 0.844 83 0 0 0 0.155 17 . Bez 2. a 4. stavu dostaneme zjednoduˇsen´y popis, v nˇemˇz 2 kroky povaˇzujeme za jeden (z lich´eho stavu se po sud´em poˇctu krok˚u dostaneme do lich´eho stavu, sud´e stavy ignorujeme):

1 3 5

1

c²

2c(1−c) (1−c)²

1

PZ=





1 0 0

c² 2c (1−c) (1−c)²

0 0 1



. Napˇr. pro c= 2/3 dost´av´ame

PZ =





1 0 0

4 9

4 9

1 9

0 0 1



 ,

P²_Z =





1 0 0

52 81

16 81

13 81

0 0 1



,

P¹⁰_Z .

=





1.0 0.0 0.0

0.799 76 3.007 3·10⁻⁴ 0.199 94

0.0 0.0 1.0



.

Pˇr´ıklad(zavˇren´e restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

Reˇˇ sen´ı.

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1

P =













0 1 0 0 0

c 0 1−c 0 0

0 c 0 1−c 0

0 0 c 0 1−c

0 0 0 1 0













,P²=













c 0 1−c 0 0

0 2c−c² 0 (1−c)² 0

c² 0 2c(1−c) 0 (1−c)²

0 c² 0 1−c² 0

0 0 c 0 1−c













. Napˇr. pro c= 0.7

dost´av´ame

P =













0 1 0 0 0

0.7 0 0.3 0 0

0 0.7 0 0.3 0

0 0 0.7 0 0.3

0 0 0 1 0











 ,

P²=













0.7 0 0.3 0 0

0 0.91 0 0.09 0

0.49 0 0.42 0 0.09

0 0.49 0 0.51 0

0 0 0.7 0 0.3











 ,

P¹⁰=













0.594 76 0 0.360 14 0 4.510 3·10⁻²

0 0.846 86 0 0.153 14 0

0.588 22 0 0.363 87 0 4.790 4·10⁻²

0 0.833 79 0 0.166 21 0

0.572 98 0 0.372 58 0 5.443 8·10⁻²











 ,

0 0 1 0 0

P = 0 0.7 0 0.3 0 , 0 0 1 0 0

P²= 0.49 0 0.42 0 0.09 , 0 0 1 0 0

P¹⁰= 0.588 22 0 0.363 87 0 4.790 4·10⁻² , 0 0 1 0 0

P³⁰= 0.591 38 0 0.362 07 0 4.655 2·10⁻² , 0 0 0 0 1

P³⁰= 0.591 38 0 0.362 07 0 4.655 3·10⁻² , 0 0 1 0 0

P³¹= 0 0.844 83 0 0.155 17 0 ,

t→∞lim 0 0 1 0 0 P^t

neexistuje.

Bez 2. a 4. stavu dostaneme zjednoduˇsen´y popis, v nˇemˇz 2 kroky povaˇzujeme za 1:

1 3 5

c

1−c

c²

2c(1−c)

(1−c)²

1−c c

PZ=





c 1−c 0

c² 2c (1−c) (1−c)²

0 c 1−c



. Napˇr. pro c= 2/3 dost´av´ame

P_Z =







2 3

1

3 0

4 9

4 9

1 9

0 ²₃ ¹₃





 ,

P²_Z =







16 27

10 27

1 27 40

81 34 81

7 81 8

27 14 27

5 27





,

P¹⁰_Z .

=





0.533 42 0.399 95 6.662 2·10⁻² 0.533 27 0.400 03 6.669 7·10⁻² 0.532 97 0.400 18 6.684 7·10⁻²



,

P²⁰_Z .

=





0.533 0.400 6.67·10⁻² 0.533 0.400 6.67·10⁻² 0.533 0.400 6.67·10⁻²



. Pˇr´ıklad(otevˇren´a a zavˇren´a restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

Reˇˇ sen´ı.

1 2 3 4 5

1 c

1−c 1−c

c c

1−c

1

P =













1 0 0 0 0

c 0 1−c 0 0

0 c 0 1−c 0

0 0 c 0 1−c

0 0 0 1 0













, P²=













1 0 0 0 0

c c(1−c) 0 (1−c)² 0

c² 0 2c(1−c) 0 (1−c)²

0 c² 0 1−c² 0

0 0 c 0 1−c











 .

Bez 2. a 4. stavu dostaneme zjednoduˇsen´y popis, v nˇemˇz 2 kroky povaˇzujeme za jeden:

1 3 5

1

c²

2c(1−c)

(1−c)²

1−c c

P_Z=





1 0 0

c² 2c (1−c) (1−c)²

0 c 1−c



. Napˇr. pro c= 2/3 dost´av´ame

P_Z =





1 0 0

4 9

4 9

1 9

0 ²₃ ¹₃



,

P²_Z =





1 0 0

52 81

22 81

7 81 8

27 14 27

5 27



,

P¹⁰_Z .

=





1 0 0

0.986 13 1.040 5·10⁻² 3.468 3·10⁻³ 0.972 25 2.081 0·10⁻² 6.936 6·10⁻³



,

P²⁰_Z .

=





1 0 0

0.9998 1.8·10⁻⁴ 6.01·10⁻⁵ 0.9995 3.61·10⁻⁴ 1.2·10⁻⁴



.

Cviˇcen´ı. Upravte pˇredchoz´ı ´ulohy na jednodimenzion´aln´ı n´ahodn´e proch´azky tak, ˇze se n´ahodnˇe nevol´ı smˇer, alezmˇena smˇeru.

(N´avod: Potˇrebujeme zdvojit stavy, do nichˇz se lze dostat z obou stran, a t´ım pˇridat informaci o tom, z kter´eho smˇeru jsme pˇriˇsli. Tu je potˇreba dodat i v popisu poˇc´ateˇcn´ıho stavu.)

Cviˇcen´ı. [Wasserman 2004] Markov˚uv ˇretˇezecX_t,t∈N, m´a matic´ı pˇrechodu

P =





0.1 0.2 0.7 0.9 0.1 0 0.1 0.8 0.1





a poˇc´ateˇcn´ı pravdˇepodobnosti (0.3, 0.4, 0.3). Najdˇete pravdˇepodobnosti P(X0= 1, X1= 2, X2= 3), P(X0= 1, X1= 2, X2= 2).

Cviˇcen´ı. (upraveno dle [Wasserman 2004]) H´az´ıme kostkou. N´ahodn´a veliˇcina Xt je maximum z prvn´ıch t hod˚u. Ukaˇzte, ˇze se jedn´a o Markov˚uv ˇretˇezec, najdˇete jeho pˇrechodov´y diagram a matici pˇrechodu.

3.2 Permutace stav˚ u

Pokud v popisu zmˇen´ıme poˇrad´ı stav˚u, zmˇen´ı se stejnˇe poˇrad´ı sloˇzek vektor˚u i ˇr´adk˚u a sloupc˚u matice pˇrechodu.

Pˇr´ıklad(basketbal– pokraˇcov´an´ı). Matice pˇrechodu P =









1 0 0 0

a 0 1−a 0

0 1−b 0 b

0 0 0 1









1 2 3 4

1 a

1−a

b

1−b

1

se v´ymˇenou 2. a 4. stavu (=permutac´ı stav˚u(1,4,3,2)) zmˇen´ı na matici









1 0 0 0

0 1 0 0

0 b 0 1−b

a 0 1−a 0







 .

Pˇr´ıklad(zavˇren´e restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1 Slouˇcen´ım dvou krok˚u do jednoho jsme dospˇeli k matici:

P²=













c 0 1−c 0 0

0 2c−c² 0 (1−c)² 0

c² 0 2c(1−c) 0 (1−c)²

0 c² 0 1−c² 0

0 0 c 0 1−c











 .

Permutac´ı stav˚u (1,3,5,2,4) dostaneme blokovˇe diagon´aln´ı matici:













c 1−c 0 0 0

c² 2c (1−c) (1−c)² 0 0

0 c 1−c 0 0

0 0 0 2c−c² (1−c)²

0 0 0 c² 1−c²











 .

4 Klasifikace stav˚ u Markovov´ ych ˇ retˇ ezc˚ u s koneˇ cnˇ e mnoha stavy

Stavj je dosaˇziteln´y (angl.accessible) ze stavu i, jestliˇze se zidoj d´a pˇrej´ıt s nenulovou pravdˇepodobnost´ı (pro nˇejak´y poˇcet krok˚u),

∃t≥0 :pij(t)>0. Znaˇcen´ı:i→j. Negace:i6→j.

Stavyi, jkomunikuj´ı(angl.communicate), jestliˇze i→j∧j→i. Znaˇcen´ı:i↔j.

Relace↔je ekvivalence.

Stav jetrval´y(angl.persistent, recurrent), jestliˇze (podm´ınˇen´a) pravdˇepodobnost, ˇze kdyˇz z nˇej vyjdeme, nˇekdy v budoucnu se do nˇej vr´at´ıme, je 1.

Speci´aln´ı pˇr´ıpad trval´eho stavu: Stavijeabsorpˇcn´ı(angl.absorbing), jestliˇze jej nelze opustit.

Jak se pozn´a, ˇzei je absorpˇcn´ı stav?

pii = 1, tj.

pij=δij=

1 proi=j, 0 proi6=j.

Stav jepˇrechodn´y(angl.transient), jestliˇze nen´ı trval´y, tj. pravdˇepodobnost, ˇze se do nˇej (nˇekdy) vr´at´ıme, je

<1.

Jak se pozn´a, ˇzeije pˇrechodn´y stav?

Lze se z nˇej dostat do stavu, z nˇehoˇz se nelze dostat zpˇet, tj. existuje stavj takov´y, ˇze i→j∧j6→i.

Jak se pozn´a, ˇzeije trval´y stav?

Nen´ı pˇrechodn´y, neboli lze se z nˇej dostat jen do stav˚u, z nichˇz se lze dostat zpˇet, tj.i→j =⇒ j →i.

D˚usledek:

Kdyˇzije pˇrechodn´y,i↔j, pakj je pˇrechodn´y.

Kdyˇzije trval´y,i↔j, pakj je trval´y.

Pˇr´ıklad(basketbal– pokraˇcov´an´ı). Matice pˇrechodu je P =









1 0 0 0

a 0 1−a 0

0 1−b 0 b

0 0 0 1







 ,

1 2 3 4

1 a

1−a

b

1−b

1

prvn´ı a posledn´ı stav je trval´y (dokonce absorpˇcn´ı), zb´yvaj´ıc´ı 2 pˇrechodn´e, protoˇze se z nich lze dostat do ab- sorpˇcn´ıch (a zpˇet ne).

Vˇeta. Stavi je trval´y ⇐⇒

∞

P

t=1

pii(t) =∞. Stavije pˇrechodn´y ⇐⇒

∞

P

t=1

pii(t)<∞.

D˚ukaz.

”=⇒“: ˇC´ıslo

∞

P

t=1

pii(t) je stˇredn´ı hodnota poˇctu n´avrat˚u. S pravdˇepodobnost´ı 0 se nevr´at´ıme. S pravdˇe- podobnost´ı 1 se aspoˇn jednou vr´at´ıme. Pravdˇepodobnost, ˇze 1. n´avrat bude i posledn´ı, je 0. Pravdˇepodobnost, ˇze n-t´y n´avrat bude posledn´ı, je 0 pro vˇsechna n∈N. To je spoˇcetnˇe mnoho jev˚u, tedy pravdˇepodobnost, ˇze poˇcet n´avrat˚u bude koneˇcn´y, je 0. S pravdˇepodobnost´ı 1 se vr´at´ıme nekoneˇcnˇekr´at.

”⇐“: Pˇredpokl´adejme, ˇze stavije pˇrechodn´y. Oznaˇcmeq <1 pravdˇepodobnost, ˇze se nˇekdy vr´at´ıme. Po prvn´ım n´avratu n´asleduje druh´y s podm´ınˇenou pravdˇepodobnost´ıq, celkovˇe s pravdˇepodobnost´ıq²,n-t´y s pravdˇepo- dobnost´ıqⁿ. Celkov´y souˇcet pravdˇepodobnost´ı n´avrat˚u

P∞

t=1p_ii(t) je roven souˇctu pravdˇepodobnost´ın-t´eho n´avratu pˇres vˇsechnan,

∞

X

t=1

pii(t) =

∞

X

n=1

qⁿ= q

1−q <∞.

Perioda stavu i je nejvˇetˇs´ı spoleˇcn´y dˇelitel vˇsech ˇc´ısel t, pro kter´a p_ii(t) > 0, tj. nejvˇetˇs´ı ˇc´ıslo t takov´e, ˇze p_ii(u) = 0 pro vˇsechnau, kter´a nejsou n´asobkyt.

Trval´y stav je periodick´y (angl. periodic), jestliˇze m´a periodu t > 1, v opaˇcn´em pˇr´ıpadˇe jeneperiodick´y (angl.aperiodic).

Nutn´a podm´ınka:Je-li staviperiodick´y, mus´ı b´yt odpov´ıdaj´ıc´ı prvek na diagon´ale pii= 0.

Kdyˇzi↔j a stavije periodick´y s periodout, pakj je periodick´y s periodout.

Stav jeergodick´y(angl. ergodic), jestliˇze je trval´y a neperiodick´y.

Pˇr´ıklad (n´ahodn´a proch´azka v cyklu). Pro (obousmˇernou) n´ahodnou proch´azku v cyklu sud´e d´elky maj´ı vˇsechny stavy periodu2 (pˇrech´az´ıme mezi sud´ymi a lich´ymi), jsou trval´e a periodick´e.

Pro (obousmˇernou) n´ahodnou proch´azku v cyklu lich´e d´elky maj´ı vˇsechny stavy periodu 1 (pˇrestoˇze se do nich nelze vr´atit v 1 kroku!) a jsou ergodick´e.

Mnoˇzinatrval´ychstav˚u je uzavˇren´a, jestliˇze ji nelze opustit.

Komponenta je (kaˇzd´a) nepr´azdn´a uzavˇren´a mnoˇzina (trval´ych) stav˚u, kter´a neobsahuje vlastn´ı (=menˇs´ı nepr´azdnou) uzavˇrenou podmnoˇzinu stav˚u.

Vˇeta. Vˇsechny uzavˇren´e mnoˇziny stav˚u jsou sjednocen´ı (disjunktn´ıch) komponent (vˇcetnˇe pr´azdn´e mnoˇziny komponent) a tvoˇr´ıσ-algebru podmnoˇzin mnoˇziny vˇsech trval´ych stav˚u.

Kaˇzd´y absorpˇcn´ı stav tvoˇr´ı jednoprvkovou komponentu.

Kaˇzd´a mnoˇzina absorpˇcn´ıch stav˚u je uzavˇren´a.

Markov˚uv ˇretˇezec jenerozloˇziteln´y, jestliˇze mnoˇzina vˇsech jeho stav˚u je komponenta.

⇒Nem´a pˇrechodn´e stavy.

Dosaˇzitelnost (B ´UNO: v obou smˇerech) rozdˇeluje vˇsechnytrval´estavy na disjunktn´ı komponenty. (Dosaˇziteln´e jsou pr´avˇe ty dvojice stav˚u, kter´e patˇr´ı do stejn´e komponenty.) Vˇsechny stavy v komponentˇe maj´ı stejnou pe- riodu.

⇒Pokud jsou vˇsechny stavy trval´e a ˇretˇezec je rozloˇziteln´y, lze matici pˇrechodu (po vhodn´e permutac´ı stav˚u) vyj´adˇrit jakoblokovˇe diagon´aln´ı,

P =











D1 0 · · · 0 0 D2 · · · 0 ... ... . .. ... 0 0 · · · Dk









 ,

kde kaˇzd´y blok odpov´ıd´a jedn´e komponentˇe a0je nulov´a matice odpov´ıdaj´ıc´ıho ˇr´adu.

Pokud existuj´ı pˇrechodn´e stavy a zaˇrad´ıme je aˇz za trval´e (pomoc´ı permutace stav˚u), matice pˇrechodu m´a tvar P =

D 0 R Q

,

kdeD vyjadˇruje pravdˇepodobnosti pˇrechod˚u mezi trval´ymi stavy,Qmezi pˇrechodn´ymi aRvyjadˇruje pravdˇe- podobnosti pˇrechod˚u z pˇrechodn´ych stav˚u do trval´ych.

Po rozkladu mnoˇziny trval´ych stav˚u na komponenty dostaneme tvar

P =















D1 0 · · · 0 0 0 D2 · · · 0 0 ... ... . .. ... ... 0 0 · · · Dk 0 R₁ R₂ · · · R_k Q













 .

Pˇr´ıklad(basketbal– pokraˇcov´an´ı).

1 2 3 4

1 a

1−a

b

1−b

1

Matice pˇrechodu po permutaci stav˚u byla









1 0 0 0

0 1 0 0

0 b 0 1−b

a 0 1−a 0









=

D 0 R Q

=





D₁ 0 0 0 D₂ 0 R1 R2 Q



,

kde prvn´ı 2 stavy jsou trval´e (dokonce absorpˇcn´ı), zb´yvaj´ıc´ı 2 pˇrechodn´e, D=

1 0 0 1

, R=

0 b

a 0

, Q=

0 1−b 1−a 0

,

D₁= 1

, D₂= 1

, R₁=

0 a

, R₂=

b 0

.

Pˇr´ıklad(otevˇren´e restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1

P =













1 0 0 0 0

c 0 1−c 0 0

0 c 0 1−c 0

0 0 c 0 1−c

0 0 0 0 1











 .

Permutac´ı stav˚u (1,5,2,3,4) dostaneme matici pˇrechodu













1 0 0 0 0

0 1 0 0 0

c 0 0 1−c 0

0 0 c 0 1−c

0 1−c 0 c 0













=

D 0 R Q

=





D1 0 0 0 D2 0 R1 R2 Q



,

kde prvn´ı 2 stavy jsou absorpˇcn´ı, zb´yvaj´ıc´ı 3 pˇrechodn´e,

D= 1 0

0 1

, R=





c 0

0 0

0 1−c



, Q=





0 1−c 0

c 0 1−c

0 c 0



,

D1= 1

, D2= 1

, R1=



 c 0 0



, R2=



 0 0 1−c



 . Pˇr´ıklad(zavˇren´e restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1 Slouˇcen´ım dvou krok˚u do jednoho a pˇreskupen´ım stav˚u (

”napˇred lich´e, pak sud´e“) jsme dospˇeli k blokovˇe dia- gon´aln´ı matici:













c 1−c 0 0 0

c² 2c (1−c) (1−c)² 0 0

0 c 1−c 0 0

0 0 0 2c−c² (1−c)²

0 0 0 c² 1−c²











 .

Tento ˇretˇezec lze rozloˇzit na2 komponenty: jednu se3stavy (odpov´ıdaj´ıc´ımi lich´ym,1,3,5, v p˚uvodn´ı reprezen- taci), druhou se2 stavy (odpov´ıdaj´ıc´ımi p˚uvodn´ım sud´ym,2,4). Vˇsechny stavy jsou ergodick´e.

Cviˇcen´ı. [Wasserman 2004] Markov˚uv ˇretˇezec m´a matic´ı pˇrechodu

P =

















0.4 0 0.1 0 0 0.5 0.05 0.7 0.25 0 0 0

0 0 0 0 1 0

0.05 0.5 0.4 0 0 0.05

0 0 1 0 0 0

0 0 0 0 0 1















 .

Urˇcete pˇrechodn´e a trval´e stavy a jejich periodu.

Cviˇcen´ı. [Hsu 1996] Markov˚uv ˇretˇezec m´a matic´ı pˇrechodu

P =





0 0.5 0.5 0.7 0 0.3

1 0 0



.

Je stav1 periodick´y?

5 Asymptotick´ e chov´ an´ı Markovov´ ych ˇ retˇ ezc˚ u s koneˇ cnˇ e mnoha stavy

Metody ˇreˇsen´ı:

• Speci´aln´ı pˇr´ıpady lze ˇreˇsit exaktnˇe.

• Obecnˇe potˇrebujeme urˇcit lim

t→∞P^t. Pro matici ˇr´adu 2 viz Dodatek 10.

• Obt´ıˇzn´e ´ulohy lze simulovat na poˇc´ıtaˇci (metoda MCMC=Markov Chain Monte Carlo) a z´ıskat tak aspoˇn pˇredstavu o jejich vlastnostech.

5.1 Pˇ rechodn´ e stavy

Vˇeta. Pravdˇepodobnosti pˇrechodn´ych stav˚u konverguj´ı k 0.

D˚ukaz. V koneˇcn´em ˇcase T se z pˇrechodn´eho stavu pˇrejde do nˇekter´eho trval´eho s pravdˇepodobnost´ı aspoˇn ε >0, v nˇekter´em z pˇrechodn´ych stav˚u z˚ust´avame s pravdˇepodobnost´ı nejv´yˇse 1−ε. V ˇcase 2T z˚ust´avame v nˇekter´em z pˇrechodn´ych stav˚u s pravdˇepodobnost´ı nejv´yˇse (1−ε)², v ˇcaset T s pravdˇepodobnost´ı nejv´yˇse (1−ε)^t→0 prot→ ∞.

D˚usledek. S pravdˇepodobnost´ı1 se dostaneme do nˇekter´e komponenty a v t´e jiˇz z˚ustaneme.

D˚usledek. Existuje trval´y stav.

Ot´azky:

Do jak´ych trval´ych stav˚u pˇrejdeme z pˇrechodn´ych?

Za jak dlouho?

Vˇeta. Necht’ stavy1, . . . , ijsou absorpˇcn´ı, i+ 1, . . . , npˇrechodn´e. Pak matice pˇrechodu m´a tvar P =

Ii 0 R Q

,

kdeIije jednotkov´a matice ˇr´adui. Pravdˇepodobnost, ˇze z pˇrechodn´eho stavuj > iskonˇc´ıme v absorpˇcn´ım stavu k≤i, je prvek na pozici(j−i, k)v matici

(I_n−i+Q+Q²+Q³+. . .

| {z }

F

)R=F R,

kdeIn−i je jednotkov´a matice ˇr´adu n−ia

F =I_n−i+Q+Q²+Q³+. . . je fundament´aln´ı maticetohoto ˇretˇezce.

D˚ukaz. (ˇc´asteˇcn´y) Tvar matice pˇrechodu jsme jiˇz odvodili. MaticeQpopisuje

”recyklaci“ pˇrechodn´ych stav˚u a maticeRjejich nevratnou pˇremˇenu na trval´e.

Pokud jsou pouze pˇrechodn´e a absorpˇcn´ı stavy, pak je lze seˇradit tak, jak poˇzaduje pˇredchoz´ı vˇeta.

Vˇeta.

F =I_n−i+Q+Q²+Q³+. . .= (I_n−i−Q)⁻¹.

D˚ukaz. (ˇc´asteˇcn´y) Oznaˇcme

Ft=I_n−i+Q+Q²+Q³+. . .+Q^t. Pak

(I_n−i−Q)·Ft=I_n−i−Q+Q−Q²+Q²−Q³+. . .−Q^t+1=I_n−i−Q^t+1. MaticeQm´a vˇsechny souˇcty ˇr´adk˚u nejv´yˇse 1 a nˇekter´e menˇs´ı neˇz 1. O takov´ych matic´ıch je zn´amo, ˇze lim

t→∞Q^t=0 a ˇzeI_n−i−Qje regul´arn´ı. Tud´ıˇz

t→∞lim(I_n−i−Q)·F_t=I_n−i, F = lim

t→∞Ft= (In−i−Q)⁻¹.

Pˇr´ıklad(basketbal– pokraˇcov´an´ı).

1 2 3 4

1 a

1−a

b

1−b

1

Matice pˇrechodu po permutaci stav˚u byla









1 0 0 0

0 1 0 0

0 b 0 1−b

a 0 1−a 0









=

I2 0 R Q

,

kde prvn´ı 2 stavy jsou absorpˇcn´ı, zb´yvaj´ıc´ı 2 pˇrechodn´e, I2=

1 0 0 1

, R=

0 b

a 0

, Q=

0 1−b 1−a 0

,

F = (I2−Q)⁻¹=

1 b−1

a−1 1

−1

= 1

a+b−a b

1 1−b 1−a 1

,

F R= 1 a+b−a b

a(1−b) b

a b(1−a)

=

a(1−b) a+b−a b

b a+b−a b a

a+b−a b

b(1−a) a+b−a b

! .

Zaˇc´ın´a Alice (stav 4, tj. posledn´ı; pˇred permutac´ı byl2.), pravdˇepodobnosti pˇrechod˚u do absorpˇcn´ıch stav˚u jsou tedy v posledn´ım ˇr´adku matice F R.

Alice vyhraje s pravdˇepodobnost´ı a

a+b−a b, Bob s pravdˇepodobnost´ı b(1−a) a+b−a b.

Napˇr. pro a= 1/2,b = 1/3 Alice vyhraje s pravdˇepodobnost´ı3/4, Bob s pravdˇepodobnost´ı1/4, coˇz odpov´ıd´a numerick´emu experimentu:

P¹⁰_Z .

=





1.0 0.0 0.0

0.749 99 1.693 5·10⁻⁵ 0.250 00

0.0 0.0 1.0



. Pˇr´ıklad(otevˇren´e restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1

Permutac´ı p˚uvodn´ıch stav˚u (1,5,2,3,4)jsme dostali matici pˇrechodu













1 0 0 0 0

0 1 0 0 0

c 0 0 1−c 0

0 0 c 0 1−c

0 1−c 0 c 0













=

I2 0 R Q

,

kde prvn´ı 2 stavy jsou absorpˇcn´ı, zb´yvaj´ıc´ı 3 pˇrechodn´e,

I2= 1 0

0 1

, R=





c 0

0 0

0 1−c



, Q=





0 1−c 0

c 0 1−c

0 c 0



,

F = (I₃−Q)⁻¹=





1 c−1 0

−c 1 c−1

0 −c 1





−1

=

= 1

2c²−2c+ 1





1−c+c² 1−c (1−c)²

c 1 1−c

c² c c²−c+ 1



,

F R= 1 2c²−2c+ 1





c 1−c+c²

(1−c)³

c² (1−c)²

c³ (1−c) 1−c+c²



.

Napˇr. pro c= 2/3 dost´av´ame

F R=







14 15

1 15 4 5

1 5 8 15

7 15





.

Souhlas s numerick´ym experimentem, je-li poˇc´ateˇcn´ı stav prostˇredn´ı z pˇrechodn´ych:

P¹⁰_Z .

=





1.0 0.0 0.0

0.799 76 3.007 3·10⁻⁴ 0.199 94

0.0 0.0 1.0



.

MaticeF Rje stochastick´a, ud´av´a pravdˇepodobnosti v´ysledk˚u pro libovoln´y pˇrechodn´y poˇc´ateˇcn´ı stav (i pro jejich smˇes, tj. poˇc´ateˇcn´ı rozdˇelen´ı, kter´ym ji staˇc´ı vyn´asobit zleva). Napˇr. pro rovnomˇern´e rozdˇelen´ı poˇc´ateˇcn´ıch stav˚u dostaneme

1 3

1 3

1 3

·







14 15

1 15 4 5

1 5 8 15

7 15





= ³⁴₄₅ ¹¹₄₅ .

Co kdyˇz trval´e stavy nejsou vˇsechny absorpˇcn´ı?

M˚uˇzeme ignorovat rozd´ıly mezi trval´ymi stavy, kter´e komunikuj´ı (jsou navz´ajem dosaˇziteln´e): Kaˇzdou kompo- nentu nahrad´ıme jedn´ım

”nov´ym“ stavem, kter´y jiˇz d´ale nerozliˇsujeme. Ten je absorpˇcn´ı.

T´ım jsme pˇrevedli ´ulohu na pˇredch´azej´ıc´ı (m´ame pouze pˇrechodn´e a absorpˇcn´ı stavy).

Dozv´ıme se, s jakou pravdˇepodobnost´ı skonˇc´ıme v kter´e komponentˇe.

Kdybychom chtˇeli vˇedˇet pravdˇepodobnosti stav˚u uvnitˇr t´eto komponenty, anal´yza by byla sloˇzitˇejˇs´ı (z´aleˇz´ı nejen na tom, pˇres kter´y stav do n´ı vstoup´ıme, ale tak´e, kdy).

Uˇz v´ıme, ˇze s pravdˇepodobnost´ı 1 pˇrejdeme do nˇejak´e komponenty, kterou uˇz neopust´ıme.

Ot´azka je, co se dˇeje d´al.

5.2 Nerozloˇ ziteln´ e Markovovy ˇ retˇ ezce

Stacion´arn´ı rozdˇelen´ıpravdˇepodobnost´ıpje takov´e, kter´e se zachov´av´a, tj.

p P =p, neboli lev´y vlastn´ı vektor odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu 1.

Lze je naj´ıt vyˇreˇsen´ım t´eto (homogenn´ı) soustavy line´arn´ıch rovnic prop s dodateˇcnou podm´ınkou, ˇze souˇcet nezn´am´ych je 1.

Markov˚uv ˇretˇezec jeergodick´y, je-li nerozloˇziteln´y a m´a vˇsechny stavy ergodick´e.

Vˇeta. Ergodick´y Markov˚uv ˇretˇezec m´a jedin´e stacion´arn´ı rozdˇelen´ı pravdˇepodobnost´ı; k tomu konverguje pˇri libovoln´em poˇc´ateˇcn´ım rozdˇelen´ı.

D˚usledek. V tom pˇr´ıpadˇe lim

t→∞P^t existuje a je rovna matici, jej´ıˇz vˇsechny ˇr´adky jsou rovn´e stacion´arn´ımu rozdˇelen´ı.

Pˇr´ıklad(zavˇren´e restaurace ve vzd´alenosti 2– pokraˇcov´an´ı).

1 2 3 4 5

1

c

1−c 1−c

c c

1−c

1

Tento ˇretˇezec nen´ı ergodick´y, ale pro lich´e stavy jsme dostali zjednoduˇsen´y popis, v nˇemˇz 2 kroky povaˇzujeme za 1, a ten ergodick´y je:

P_Z =





c 1−c 0

c² 2c(1−c) (1−c)²

0 c 1−c





1 3 5

c

1−c

c²

2c(1−c)

(1−c)²

1−c c

Napˇr. pro c= 2/3

P_Z =







2 3

1

3 0

4 9

4 9

1 9

0 ²₃ ¹₃





.

Tento Markov˚uv ˇretˇezec je nerozloˇziteln´y a m´a vˇsechny stavy ergodick´e, takˇze m´a jedin´e stacion´arn´ı rozdˇelen´ı pravdˇepodobnost´ı, kter´e dostaneme ˇreˇsen´ım soustavy line´arn´ıch rovnic

(a, b,1−a−b)PZ = (a, b,1−a−b), (a, b,1−a−b) =

8 15,2

5, 1 15

.

Souhlas s numerick´ym experimentem:

P¹⁰_Z .

=





0.533 42 0.399 95 6.662 2·10⁻² 0.533 27 0.400 03 6.669 7·10⁻² 0.532 97 0.400 18 6.684 7·10⁻²



,

P²⁰_Z .

=





0.533 0.400 6.67·10⁻² 0.533 0.400 6.67·10⁻² 0.533 0.400 6.67·10⁻²



.

Uvaˇzujmenerozloˇziteln´y Markov˚uv ˇretˇezec, kter´ynen´ı ergodick´y.

Nutn´a podm´ınka:Matice pˇrechodu mus´ı m´ıt nulovou diagon´alu.

Pozn´amka. Stacion´arn´ı rozdˇelen´ı m˚uˇze existovat, ale nemus´ıme se k nˇemu pˇribl´ıˇzit.

Napˇr. pro

P =





0 1 0 0 0 1 1 0 0





je rozdˇelen´ı(1/3,1/3,1/3) stacion´arn´ı, ale z poˇc´ateˇcn´ıho rozdˇelen´ı(1,0,0) se k nˇemu nepˇribl´ıˇz´ıme.

Vˇsechny stavy maj´ı stejnou perioduT >1.

Lze je rozdˇelit na T disjunktn´ıch tˇr´ıd M1, . . . , MT tak, ˇze z kaˇzd´e tˇr´ıdy lze v jednom kroku pˇrej´ıt pouze do n´asleduj´ıc´ı (a zMT doM1).

Do kaˇzd´e tˇr´ıdy se vr´at´ıme poT kroc´ıch.

Slouˇcen´ımT krok˚u do jednoho dostaneme Markov˚uv ˇretˇezec s matic´ı pˇrechoduP^T.

Ten je rozloˇziteln´y, tˇr´ıdyM1, . . . , MT odpov´ıdaj´ı komponent´am, kter´e maj´ı vˇsechny stavy ergodick´e, takˇze maj´ı jedin´e stacion´arn´ı rozdˇelen´ı pravdˇepodobnost´ı.

⇒ Aˇz na to, ˇze se periodicky proch´az´ı mezi tˇr´ıdami M1, . . . , MT, m˚uˇzeme asymptotick´e chov´an´ı uvnitˇr nich urˇcit stejnˇe jako v pˇredchoz´ım pˇr´ıpadˇe.

Cviˇcen´ı. [Wasserman 2004] Najdˇete stacion´arn´ı rozdˇelen´ı Markovova ˇretˇezce s matic´ı pˇrechodu

P =





0.4 0.5 0.1 0.05 0.7 0.25 0.05 0.5 0.45



.

Cviˇcen´ı (rosniˇcka). (upraveno dle [Wasserman 2004]) Rosniˇcka sk´aˇce po k sch˚udc´ıch. Kaˇzd´ym skokem se s pravdˇepodobnost´ıc ∈ (0,1) dostane o sch˚udek v´yˇs, s pravdˇepodobnost´ı1−c spadne zpˇet do vody a zaˇc´ın´a od zaˇc´atku. Z nejvyˇsˇs´ıho sch˚udku vˇzdy spadne do vody (=

”nejniˇzˇs´ı sch˚udek“). Kde ji m´ame hledat, tj. jak´a je pravdˇepodobnost jej´ıho v´yskytu na jednotliv´ych sch˚udc´ıch po dlouh´em pr˚ubˇehu? ˇReˇste pokud moˇzno obecnˇe, pak pro hodnotyk= 4,c= 1/2.

5.3 Rozloˇ ziteln´ e Markovovy ˇ retˇ ezce

bez pˇrechodn´ych stav˚u se ˇreˇs´ı rozkladem na nerozloˇziteln´e (na komponenty). Mohou existovat stacion´arn´ı rozdˇelen´ı, ale nemus´ı b´yt limitou.

Pˇr´ıklad. Pro

P = 1 0

0 1

=I₂ jsou vˇsechna rozdˇelen´ı stacion´arn´ı. Pro

P =









1/2 1/2 0 0 1/2 1/2 0 0

0 0 0 1

0 0 1 0









jsou stacion´arn´ı vˇsechna rozdˇelen´ı ₂^c,^c₂,^1−c₂ ,^1−c₂

,c∈ h0,1i;

z poˇc´ateˇcn´ıho rozdˇelen´ı(1,0,0,0)se dostaneme ihned do stacion´arn´ıho(¹₂,¹₂,0,0);

z poˇc´ateˇcn´ıho rozdˇelen´ı(0,0,0,1)se k ˇz´adn´emu stacion´arn´ımu nebl´ıˇz´ıme.

5.4 Pˇ r´ıklady

Pˇr´ıklad (chcete b´yt milion´aˇrem? – zjednoduˇsen´e zad´an´ı bez z´achytn´ych bod˚u). Hr´aˇc zaplat´ı za vstup do hry. Odpov´ıd´a na ot´azky, pravdˇepodobnost, ˇze zn´a spr´avnou odpovˇed’, je c∈ (0,1). Po spr´avn´e odpovˇedi m˚uˇze skonˇcit s v´yhrou 1,2,4,8, . . ., obecnˇe 2^k−1, kde k je poˇcet spr´avnˇe zodpovˇezen´ych ot´azek. Po chybn´e odpovˇedi konˇc´ı a nedost´av´a nic.

• Jak dlouho m´a hr´at, aby maximalizoval zisk? (D´elka hry a v´yˇse v´yhry nen´ı omezena.)

• Jak´e je pˇri optim´aln´ı strategii rozdˇelen´ı, stˇredn´ı hodnota a rozptyl v´yhry po k kolech (resp. vyˇrazen´ı v nejv´yˇse k-t´em kole)?

• Jak´a je adekv´atn´ı cena za vstup do hry?

Hr´aˇc zaplatil za vstup do hry, urˇcitˇe m´a hr´at prvn´ı kolo. Pˇredk-t´ym kolem (pokud do nˇej postoup´ı) se rozhoduje mezi jistou v´yhrou2^k−1a dalˇs´ı ot´azkou, kter´a m˚uˇze v´est k v´yhˇre bud’0, nebo2^k (s pravdˇepodobnost´ıc). Optim´aln´ı

rozhodnut´ı tedy bude vˇzdy stejn´e (z´avisl´e nac, nikoli nak). Proc <1/2konˇc´ı po1. kole. Proc >1/2je optim´aln´ı hr´at co nejd´ele. Pak matice pˇrechodu je

P =

1 0 1−c c

,

prvn´ı stav (vyˇrazen´ı) je absorpˇcn´ı, druh´y (pokraˇcov´an´ı ve hˇre) je pˇrechodn´y, takˇzepravdˇepodobnost v´yhry je nulov´a!

V´yhraX_k pok kolech m´a alternativn´ı rozdˇelen´ı, EXk =c^k2^k−1,

DX_k = EX_k²−(EX_k)²=c^k2^2(k−1)−c^2k2^2(k−1)= (1−c^k)c^k2^2(k−1). Proc >1/2 je

k→∞lim c^k2^k−1= 1 2 lim

k→∞(2c)^k=∞, tedyadekv´atn´ı cena za vstup do hry je nekoneˇcn´a!

Cviˇcen´ı. Popiˇste Markov˚uv ˇretˇezec, popisuj´ıc´ı hru

”chcete b´yt milion´aˇrem?“ se z´achytn´ymi body a omezen´ym poˇctem kol.

Pˇr´ıklad (ruinov´an´ı v ruletˇe). V ruletˇe s´azka na barvu pˇrin´aˇs´ı v´yhru ve v´yˇsi dvojn´asobku vkladu s pravdˇe- podobnost´ıd o m´alo menˇs´ı neˇz 1/2 (dle typu rulety ²⁴₄₉, ¹⁸₃₇ nebo ¹⁸₃₈ = ₁₉⁹). Hr´aˇc vsad´ı nejprve 1000EUR. Po prvn´ı v´yhˇre konˇc´ı. Po kaˇzd´e prohˇre vsad´ı dvojn´asobnou ˇc´astku neˇz v pˇredchoz´ım kole. Jak´e je rozdˇelen´ı a stˇredn´ı hodnota jeho v´yhry?

Jde o obdobu hry

”chcete b´yt milion´aˇrem?“ s vymˇenˇen´ymi rolemi hr´aˇce a bank´eˇre a c= 1−d. Bank´eˇri se hra

”vypl´ac´ı“, pˇrestoˇze m´a nulovou pravdˇepodobnost v´yhry. Nere´aln´y je pˇredpoklad, ˇze hru lze hr´at libovolnˇe dlouho.

Cviˇcen´ı. Jak bude vypadat

”ruinov´an´ı v ruletˇe“, jestliˇze hr´aˇc (pˇr´ıpadnˇe i bank´eˇr) m´a omezen´e finance?

Pˇr´ıklad(petrohradsk´y paradox). Hr´aˇc zaplat´ı za ´uˇcast ve hˇre, v n´ıˇz h´az´ı minc´ı. Padne-li l´ıc, vyhraje1EUR.

Padne-li rub, hra pokraˇcuje a v´yhra se zdvojn´asobuje, tj. padne-li l´ıc poprv´e vk-t´em hodu, v´yhra je2^k−1 EUR.

Jak´a je adekv´atn´ı cena za ´uˇcast ve hˇre?

Hra konˇc´ı vk-t´em kroku s pravdˇepodobnost´ı 2^−ka v´yhrou 2^k−1EUR, stˇredn´ı hodnotu v´yhry dostaneme souˇctem pˇres vˇsechny moˇzn´e d´elky hry,

∞

X

k=1

2^−k2^k−1=

∞

X

k=1

1 2 =∞.

Cviˇcen´ı(prodluˇzovaˇcky). Prodluˇzovaˇcky s pravdˇepodobnost´ıc∈(0,1)mˇen´ı poˇrad´ı vodiˇc˚u (f´aze↔nul´ak). Jak´a je pravdˇepodobnost, ˇze s´eriov´e spojen´ıkprodluˇzovaˇcek mˇen´ı poˇrad´ı vodiˇc˚u?

Cviˇcen´ı (informaˇcn´ı kan´al). * Bin´arn´ı informaˇcn´ı kan´al pˇrenese 0 s pravdˇepodobnost´ı0.1 jako1,1 s pravdˇe- podobnost´ı0.2jako0. Spoj´ıme jichkdo s´erie. Jak´e jsou pravdˇepodobnosti chyb? Jak´y bude v´ystup prok→ ∞?

6 Reverzibilita

6.1 Odhady parametr˚ u Markovov´ ych ˇ retˇ ezc˚ u

Co lze zjistit dlouhodob´ym pozorov´an´ım?

A. Pokud m˚uˇzeme pokus libovolnˇe opakovat (vˇcetnˇe poˇc´ateˇcn´ıho rozdˇelen´ı pravdˇepodobnost´ı stav˚u), lze kon- zistentnˇe odhadnout vˇsechny parametry.

(”Dostateˇcnˇe dlouh´a doba sledov´an´ı“ je ˇCebyˇsevovou nerovnost´ı v´az´ana na nejmenˇs´ı nenulovou z odhadovan´ych pravdˇepodobnost´ı.)

B. Nad´ale uvaˇzujeme obvykl´y pˇr´ıpad, kdy Markov˚uv ˇretˇezec nastartoval jen jednou a my m˚uˇzeme sledovat jen jednu posloupnost, kterou vygeneruje.

Nem˚uˇzeme odhadnout poˇc´ateˇcn´ı rozdˇelen´ı pravdˇepodobnost´ı stav˚u a nedov´ıme se nic o komponent´ach, do kter´ych jsme se nedostali.

M˚uˇzeme studovat jen tu komponentu, v n´ıˇz jsme skonˇcili, a to jen jej´ı asymptotick´e vlastnosti.

To postaˇcuje ke konzistentn´ımu odhadu matice pˇrechodut´eto komponenty.

6.2 Obr´ acen´ı ˇ casov´ e osy (zpˇ etn´ y chod)

Co bychom pozorovali, kdybychom sledovali Markov˚uv ˇretˇezec pozp´atku a chtˇeli pozorov´an´ı popsat rovnˇeˇz Mar- kovov´ym ˇretˇezcem?

1. Pˇrechodn´e stavy by n´am to mohly znemoˇznit, nad´ale je vylouˇc´ıme.

2. M´a smysl studovat jen jednu komponentu, tedy nerozloˇziteln´y Markov˚uv ˇretˇezec.

3. M´a-li periodu T > 1, pak pˇri zpˇetn´em chodu vid´ıme pr˚uchod tˇr´ıdami stav˚u M1, . . . , MT dle kapitoly 5.2 v opaˇcn´em poˇrad´ı.

Chov´an´ı uvnitˇr nich popisuj´ı ergodick´e ˇretˇezce, vznikl´e pˇrechodem ke krok˚um d´elkyT a n´aslednou dekompozic´ı na komponentyM1, . . . , MT.

4. Pokud rozdˇelen´ı pravdˇepodobnost´ı stav˚u nen´ı stacion´arn´ı, pak pˇri pohybu vpˇred ke stacion´arn´ımu konver- guje, pˇri zpˇetn´em chodu

”diverguje“. Z toho pozn´ame, ˇze orientace ˇcasu je chybn´a a popis zpˇetn´eho chodu Markovov´ym ˇretˇezcem neexistuje. (Souvislost s principem r˚ustu entropie.)

Zb´yv´a popsatergodick´eMarkovovy ˇretˇezce sestacion´arn´ım rozdˇelen´ım pravdˇepodobnost´ı stav˚u.

Podkladem pro odhad jejich parametr˚u jsou n´am pouze (relativn´ı) ˇcetnosti pˇrechod˚u v posloupnosti stav˚u (li- bovolnˇe dlouh´e); ty konverguj´ı k pravdˇepodobnostem pˇrechod˚u.

(”Konverguj´ı“ ve stejn´em smyslu, o jak´em hovoˇr´ı ˇCebyˇsevova nerovnost. D´ıky nez´avislosti lze uplatnit i centr´aln´ı limitn´ı vˇetu.)

P⁻¹ nen´ımatice pˇrechodu zpˇetn´eho chodu:

absolutn´ı hodnota vlastn´ıch ˇc´ısel maticeP je≤1;

absolutn´ı hodnota vlastn´ıch ˇc´ısel maticeP⁻¹ je≥1.

Pˇr´ıklad.

P =





0 2/3 1/3

1/3 0 2/3

2/3 1/3 0



,

1

2 3

2 3 1

3

2 3

1 3 2

3

1 3

stacion´arn´ı rozdˇelen´ıp= (1/3,1/3,1/3).

”Pˇrevl´ad´a pohyb po smˇeru hodinov´ych ruˇciˇcek.“

Pˇri zpˇetn´em chodu

”pˇrevl´ad´a pohyb proti smˇeru hodinov´ych ruˇciˇcek.“

Odpov´ıd´a mu

”obr´acen´ı ˇsipek“ a transponovan´a matice P^>=





0 1/3 2/3

2/3 0 1/3

1/3 2/3 0



,

1

2 3

1 3 2

3

1 3

2 3

1 3

2 3

Pˇr´ıklad.

P =

1−a a

b 1−b

,

1 2

1−a

a

1−b b

kdea, b∈(0,1), stacion´arn´ı rozdˇelen´ıp= b

a+b, a a+b

. Zpˇetn´y chodnepopisuje maticeP^> (nen´ı stochastick´a!), ani

1−b b

a 1−a

,

(m´a jin´e stacion´arn´ı rozdˇelen´ı pravdˇepodobnost´ı stav˚u), n´ybrˇz opˇet P (zmˇenu orientace ˇcasu nepozn´ame).

Takov´ym ˇretˇezc˚um budeme ˇr´ıkatreverzibiln´ı.

Definice. Ergodick´yMarkov˚uv ˇretˇezec s matic´ı pˇrechoduP a stacion´arn´ım rozdˇelen´ım stav˚up= (p1, . . . , pn) je reverzibiln´ı, jestliˇze

p_ip_ij =p_jp_ji pro vˇsechnai, j.

Ekvivalentn´ı formulace:

P(X_t=i)·P(X_t+1=j|X_t=i) =P(X_t=j)·P(X_t+1=i|X_t=j) sij:=P(Xt+1=j,Xt=i) =P(Xt+1=i,Xt=j) =:sji

sij=sji

Pˇrevod na p˚uvodn´ı popis:

pi=P(Xt=i) =X

k

sik=X

m

smi,

pij=P(Xt+1=j|Xt=i) = sij

pi

= sij

P

k

sik

= sij

P

m

smi

.

Pro libovoln´y ergodick´y Markov˚uv ˇretˇezec m´ame matici s prvky sij = P(Xt+1 = j, Xt = i). M˚uˇzeme jimi ohodnotit hrany pˇrechodov´eho grafu; pak reverzibilitu snadno pozn´ame z grafu i ze symetrie maticeS.

1

2 3

2 9 1

9

2 9

1 9 2

9

1 9

1 2

(1−a)b a+b

ab a+b

a(1−b) a+b ab

a+b

Proˇc jsmeS nepouˇz´ıvali od zaˇc´atku?

Protoˇze popisuje ˇretˇezec sestacion´arn´ımrozdˇelen´ım pravdˇepodobnost´ı stav˚u.

P je maticepodm´ınˇen´ychpravdˇepodobnost´ı, nez´avisl´ych na pravdˇepodobnostech stav˚u.

Obr´acenˇe:

Vˇeta. Vnerozloˇziteln´emMarkovovˇe ˇretˇezci reverzibilita pipij =pjpji

neboli

s_ij=s_ji

implikuje, ˇze je ergodick´y a p= (p₁, . . . , p_n)je stacion´arn´ı rozdˇelen´ı pravdˇepodobnost´ı stav˚u.

D˚ukaz. Pravdˇepodobnost, ˇze pˇri rozdˇelen´ı pravdˇepodobnost´ıpbude v dalˇs´ım kroku stavj, je X

i

p_ip_ij =X

i

p_jp_ji=p_j X

i

p_ji

| {z }

1

=p_j.

Reverzibilita je silnˇejˇs´ı podm´ınka.

6.3 Jak lze luˇ stit ˇ sifry 1: model

Pˇr´ıklad. Fragment mot´aku z americk´e vˇeznice [Diaconis 2009]:

Pˇredpokl´ad´ame, ˇze kaˇzd´y znznak˚u odpov´ıd´a pr´avˇe jednomu znaku abecedy. Hled´ame spr´avnou permutaci abecedy, tˇech jen! (moc).

Hled´ame vhodnˇe zjednoduˇsen´y model.

A. Kaˇzd´y znak je nez´avisle vylosov´an s nˇejakou pravdˇepodobnost´ı.

npravdˇepodobnost´ı odhadneme relativn´ımi ˇcetnostmi v jazyce.

Maximalizujeme vˇerohodnost: Znaky obou abeced seˇrad´ıme podle relativn´ı ˇcetnosti a ztotoˇzn´ıme ty, kter´e maj´ı stejn´e poˇrad´ı.

Snadn´e, ale ne´uspˇeˇsn´e; m´alo informace.

B. Kaˇzd´y znak je vylosov´an s nˇejakou pravdˇepodobnost´ı z´avislou na pˇredchoz´ım znaku.

=⇒ Markov˚uv ˇretˇezec snstavy (posledn´ı znak).

n²prvk˚u matice pˇrechodu odhadneme podm´ınˇen´ymi relativn´ımi ˇcetnostmi dvojic znak˚u v jazyce.

Maximalizujeme vˇerohodnost.

Jak?

Uk´aˇzeme, ale napˇred uv´aˇz´ıme sloˇzitˇejˇs´ı modely.

C. Kaˇzd´y znak je vylosov´an s nˇejakou pravdˇepodobnost´ı z´avislou na`pˇredchoz´ıch znac´ıch.

=⇒ Markov˚uv ˇretˇezec sn<sup>`</sup> stavy (posledn´ıch` znak˚u).

matice pˇrechodu m´a n^{2`</sup>prvk˚u, z nichˇz nenulov´ych m˚uˇze b´yt nejv´yˇsen<sup>`+1}, odhad je pˇr´ıliˇs obt´ıˇzn´y.

Nem´ame dost dlouh´y text.

D. Kaˇzd´eslovoje vylosov´ano s nˇejakou pravdˇepodobnost´ı z´avislou na slovˇe.

=⇒ Markov˚uv ˇretˇezec s tolika stavy, kolik slov v jazyce uvaˇzujeme (napˇr. 10 000).

n²prvk˚u matice pˇrechodu odhadneme jen s obt´ıˇzemi, i kdyˇz se to dˇel´a.

Nem´ame dost dlouh´y text, aby rozdˇelen´ı na nˇem bylo podobn´e...

6.4 Jak lze luˇ stit ˇ sifry 2: rozluˇ stˇ en´ı

Model B: Pravdˇepodobnost znaku z´avis´ı na pˇredchoz´ım znaku.

Hled´ame spr´avnou permutaci znak˚u abecedy.

Spol´eh´ame na to, ˇze v´ıme, co jsou mezery mezi slovy.

Pro kaˇzdou permutaci znak˚u πdovedeme urˇcit vˇerohodnostL(π) dan´e zpr´avy.

Jak najdeme maximum vˇerohodnosti?

Sestroj´ıme nov´ynerozloˇziteln´y reverzibiln´ıMarkov˚uv ˇretˇezec sn! stavy – permutacemi abecedy.

Zvol´ıme matici pˇrechodu P ∈ R^n!×n! tak, aby stacion´arn´ı rozdˇelen´ı pravdˇepodobnost´ı stav˚u bylo ´umˇern´e vˇerohodnostiL,

p_π= L(π) P

%

L(%) =: L(π)

S .

K ˇcemu to bude?

Po delˇs´ım bˇehu budeme dost´avat pˇrev´aˇznˇe permutace s velkou vˇerohodnost´ı; spr´avn´a permutace bude nejˇcastˇejˇs´ı.

Probl´em:S:=P

%

L(%) pˇres vˇsechn! permutac´ı nespoˇc´ıt´ame.

Reˇˇ sen´ı: Budeme pouˇz´ıvat jen pomˇery vˇerohodnost´ı, na t´eto sumˇe nez´avisl´e.

6.5 Metropolis˚ uv algoritmus

0. Zvol´ıme libovolnou poˇc´ateˇcn´ı permutaci znak˚uπ.

1. V π vymˇen´ıme n´ahodnˇe vybranou dvojici znak˚u (z ⁿ₂

moˇznost´ı s rovnomˇern´ym rozdˇelen´ım); dostaneme novou permutaci%.

2. Porovn´ame vˇerohodnosti:

aπ%= L(%) L(π) = p%

pπ

.

(Vˇerohodnosti lze snadno spoˇc´ıtat, na rozd´ıl od pravdˇepodobnost´ıp_π, p_%.) A. a_π%≥1 (%je vˇerohodnˇejˇs´ı) =⇒ zmˇenu (π:=%) provedeme.

B. aπ%<1 (π je vˇerohodnˇejˇs´ı) =⇒ zmˇenu (π:=%) provedemes pravdˇepodobnost´ıaπ%. 3. Dokud nejsme spokojeni s v´ysledkem, pokraˇcujeme od kroku 1.

Retˇˇ ezec je nerozloˇziteln´y – ke kaˇzd´e permutaci se m˚uˇzeme dostat.

Kdybychom zmˇenu vˇzdy provedli, ˇretˇezec by nebyl ergodick´y, mˇel by periodu 2.

Nav´ıc jsme splnili podm´ınku reverzibility (zobrazen detail pˇrechodov´eho grafu):

A.L(%)≥L(π): pπpπ%= ^pπ

(ⁿ₂)=p%p%π

π %

1

(ⁿ₂)

a_%π

(ⁿ₂) = ^L(π)

(ⁿ₂)^L(%)= ^pπ (ⁿ₂)^p%

π %

p_π

(ⁿ₂)= ^L(π)

S(ⁿ₂)

p_%a_%π

(ⁿ₂) = ^pπ

(ⁿ₂) = ^L(π)

S(ⁿ₂)

B.L(%)< L(π): pπpπ%= ^p%

(ⁿ₂) =p%p%π

π %

aπ%

(ⁿ2) = ^L(%)

(ⁿ2)^L(π)= ^p% (ⁿ2)^pπ

1

(ⁿ₂)

π %

p_πa_π%

(ⁿ₂) = ^p%

(ⁿ₂)= ^L(%)

S(ⁿ₂)

p_%

(ⁿ₂)= ^L(%)

S(ⁿ₂)

Pravdˇepodobnosti stav˚u podle vˇety 6.2 konverguj´ı k p_π= L(π)

S = L(π)

P

%

L(%),

takˇze jsou ´umˇern´e vˇerohodnosti.

Pˇr´ıklad rozˇsifrov´an´ı Shakespearova textu (vlevo poˇcet krok˚u algoritmu):

Fragment rozˇsifrovan´eho mot´aku:

Uspˇ´ ech, pˇrestoˇze to ani nebyla tak docela angliˇctina.

7 Markovovy ˇ retˇ ezce s nekoneˇ cnˇ e mnoha stavy

M´ısto n´asoben´ı matic bychom potˇrebovali nekoneˇcn´e sumy.

Klasifikace stav˚u je sloˇzitˇejˇs´ı o dalˇs´ı moˇznosti (nulov´ystav), nemus´ı existovat trval´y stav...

Lze setrvat v pˇrechodn´ych stavech (nekoneˇcnˇe mnoha).

Pˇr´ıklad(nekoneˇcn´a n´ahodn´a proch´azka). [Wasserman 2004, Zv´ara, ˇStˇep´an 2002]

• Pokud oba smˇery vol´ıme se stejnou pravdˇepodobnost´ı, do v´ychoz´ıho bodu se vr´at´ıme s pravdˇepodobnost´ı1.

S pravdˇepodobnost´ı1navˇst´ıv´ıme v´ychoz´ı bod (stejnˇe jako vˇsechny ostatn´ı!)nekoneˇcnˇekr´at, pˇrestostˇredn´ı doba mezi n´avraty je nekoneˇcn´a.

• Pokud oba smˇery vol´ıme se r˚uznou pravdˇepodobnost´ı, do v´ychoz´ıho bodu se vr´at´ıme s pravdˇepodobnost´ı<1.

Pak jsou vˇsechny stavy pˇrechodn´e.

Pˇr´ıklad(nekoneˇcn´a n´ahodn´a proch´azka ve v´ıce dimenz´ıch). [Enc. Math.] Pˇri nekoneˇcn´e n´ahodn´e proch´azce se vˇzdy vyd´ame do nˇekter´eho ze sousedn´ıch bod˚u, a to se stejnou pravdˇepodobnost´ı.

• V 1dimenzi se do v´ychoz´ıho bodu vr´at´ıme s pravdˇepodobnost´ı1.

• Ve2 dimenz´ıch (vol´ıme ze4-okol´ı) se do v´ychoz´ıho bodu vr´at´ıme s pravdˇepodobnost´ı1.

• Ve3 dimenz´ıch (vol´ıme ze6-okol´ı) se do v´ychoz´ıho bodu vr´at´ıme s pravdˇepodobnost´ı pˇribliˇznˇe0.35<1.

8 Pˇ r´ıklady aplikac´ı

• Hromadn´a obsluha a fronty

• Klasifikace, rozpozn´av´an´ı(od tˇr´ıdˇen´ı chmelu po rozpozn´av´an´ı obliˇcej˚u)

• Pohyb nosiˇc˚u n´aboje v polovodiˇc´ıch, rekombinace