4. 1.
Markov-l´ ancok Defin´ıci´ o´ es alapvet˝ o tulajdons´ agok
Legyen adott egy S diszkr´et halmaz. Leggyakrabban S az eg´esz sz´amoknak egy halmaza, p´eld´ aul S = {0, 1, 2, . . . , N }, {0, 1, 2, . . . }. 1. defin´ıci´ o. S ´ert´ek˝ u val´ osz´ın˝ us´egi v´altoz´ ok egy X0 , X1 , X2 , . . . v´egtelen sorozat´ at Markov-l´ancnak h´ıvjuk, ha a val´osz´ın˝ us´egi v´altoz´ ok k¨oz¨ott a k¨ovetkez˝o o¨sszef¨ ugg´es fenn´all. Minden n ≥ 0 eg´esz sz´am, ´es j, i, i0 , 11 , . . . , in−1 ∈ S ´allapotok eset´en teljes¨ ul a P(Xn+1 = j | Xn = i, Xn−1 = in−1 , . . . , X1 = i1 , X0 = i0 ) = P(Xn+1 = j | Xn = i)
(1)
egyenl˝ os´eg. A Markov-l´ anc id˝oben homog´en, ha P(Xn+1 = j | Xn = i) = P(X1 = j | X0 = i), minden n ≥ 0 eset´en. • Leggyakrabban az indexre u ´ gy gondolunk, mint az id˝o param´etere. ´Igy egy Markov-l´anc valamilyen id˝oben v´altoz´ o v´eletlen jelens´eget ´ır le. • Fontos k¨ovetkezm´enye a defin´ıci´onak, pontosabban a (1) egyenl˝ os´egnek, hogy P(Xn+m = jm , . . . , Xn+2 = j2 , Xn+1 = j1 | Xn = i, Xn−1 = in−1 , . . . , X1 = i1 , X0 = i0 ) = = P(Xn+m = jm , . . . , Xn+2 = j2 , Xn+1 = j1 = j | Xn = i). Ez az egyenl˝ os´eg azt jelenti, hogy ha a jelen az n id˝oindexn´el van, ´es a jelen ´ert´ek´et ismerj¨ uk, Xn = i, akkor a Markov-l´ anc j¨ ov˝ oje, (Xn+m = jm , . . . , Xn+2 = j2 , Xn+1 = j1 ), f¨ uggetlen a m´ ultt´ol, az (Xn−1 = in−1 , . . . , X1 = i1 , X0 = i0 ) esem´enyt˝ ol. • Ezent´ ul S-et a Markov-l´ anc ´ allapott´ernek h´ıvjuk. • Ezent´ ul csak id˝oben homog´en Markov-l´ancokkal foglalkozunk, ´es elhagyjuk az id˝oben homog´en jelz˝ ot. • Minden Markov-l´ anc fejl˝ od´es´et meghat´arozza a P(Xn+1 = j | Xn = i) egyl´ep´eses ´atmenetval´osz´ın˝ us´eg, ha ez adott minden j, i ∈ S eset´en. Ezeket az ´atmenet val´osz´ın˝ us´egeket egy |S|-szer |S|-es P m´atrixba gy˝ ujtj¨ uk, ahol a m´atrix ij index˝ u hely´en a Pij = P(Xn+1 = j | Xn = i) val´osz´ın˝ us´eg ´ all. Ha S v´egtelen, akkor P egy v´egtelen m´atrix. A P m´atrix neve ´ atmenetval´ osz´ın˝ us´eg m´atrix, vagy egyl´ep´eses ´atmenetval´osz´ın˝ us´eg m´atrix. • Legyen adott ´ allapotok egy v´eges hossz´ u sorozata: i1 , i2 , . . . , in−1 , in . Fontos tulajdons´ aga a Markovl´ancoknak, hogy egyszer˝ uen fel tudjuk ´ırni annak a val´osz´ın˝ us´eg´et, hogy mi annak a val´osz´ın˝ us´ege, hogy a Markov-l´ anc egym´ as ut´ani l´ep´eseiben pont ezeket az ´allapotokat veszi fel: P (Xn = in , Xn−1 = in−1 . . . , X2 = i2 , X1 = i1 | X1 = i0 ) = Pi0 i1 Pi1 i2 . . . Pin−1 in
(2)
Ennek az a k¨ovetkezm´enye, hogy minden Markov-l´ancot egy´ertelm˝ uen meg lehet feleltetni egy ir´ any´ıtott, s´ ulyozott gr´ afon val´ o v´eletlen bolyong´asnak. Legyenek a gr´af pontjai az S halmazzal indexelve. Az i → j ir´ any´ıtott ´el be van h´ uzva, ha a Pij egy l´ep´eses ´atmenet pozit´ıv, az ´el s´ uly a Pij ´ert´eke. Ekkor a gr´afon val´ o bolyong´ as u ´ gy n´ez ki, hogy ha n-dik l´ep´esben a bolyong´as az i ´allapotba ugrott, akkor a j-be ugr´ as val´ osz´ın˝ us´ege ´eppen Pij 1. p´ elda. Az 1. ´ abr´ an l´ev˝ o Markov-l´anc eset´en annak a val´osz´ın˝ us´ege, hogy az 5-b˝ ol indulva sorus´ege, hogy 5-b˝ ol indulva sorrendben rendben megl´ atogatja az 112 ´ allapotokat 31 21 14 . Annak a val´osz´ın˝ megl´ atogatja az 612 ´ allapotokat 0.
1
1 3
1 2
6 2 3 2 3
1/2 1/4 1/4 0 0 0 0 1/4 1/2 1/4 0 0 0 0 1/2 0 1/2 0 0 0 0 0 0 0 0 1/3 2/3 0 1/3 0 0 0 0 1/3 0 P = 0 0 0 2/3 0 1/3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
3 1 2
1 3
4 1 3
1 3
7
1
2 1 4
1 2
1
10 1
1 4
1 3
5
1 4
1 4
9
1 2
1 2
1 2 1 2
1 2
8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1/3 0 0 0 1/2 0 1/2 1/2 1/2 0 0 0 1 0 0 0
Figure 1.: Markov-l´ anc gr´ af reprezent´ aci´ oja ´es ´atmenetval´osz´ın˝ us´eg m´atrixa • T¨obbl´ep´eses ´ atmenetval´ osz´ın˝ us´egek. Legyen P (n) a P ´atmenetval´osz´ın˝ us´eg m´atrixszal meghat´arozott Markov-l´ anc egyl´ep´eses ´ atmenetval´ osz´ın˝ us´eg m´atrixa. Pontosabban, P (n) ij koordin´at´aj´ u hely´en a (n)
Pij = P(Xn = j | X0 = i),
i, j ∈ S
val´osz´ın˝ us´eg ´ all, azaz annak val´ osz´ın˝ us´ege, hogy a Markov-l´anc n l´ep´ese alatt az i ´allapotb´ol eljut a j ´allapotba. Fontos ¨ osszef¨ ugg´es, hogy az n l´ep´eses ´atmenetval´osz´ın˝ us´eg m´atrix fel´ırhat´ o az egyl´ep´eses ´atmenetval´ osz´ın˝ us´eg m´atrix n-dik hatv´anyak´ent: 1. ´ all´ıt´ as. P (n) = P n 2. p´ elda. A 1. ´ abr´ aban defini´alt Markov-l´anc eset´en annak a val´osz´ın˝ us´ege, hogy 5-b´ ol indulva 3 l´ep´es m´ ulva a 2-es ´ allapotban van megegyezik a [P 3 ]53 elemmel. Ez megegyezik az 5112 5122 utak val´osz´ın˝ us´eg´enek ¨ osszeg´evel. • Eddig mindig feltett¨ uk, hogy a Markov-l´anc valamilyen i0 ´allapotb´ol indul, ´es u ´ gy n´ezt¨ uk a k´es˝obbi l´ep´esek val´ osz´ın˝ us´eg´et. Most P(X0 = i0 , X1 = i1 ), vagy P(Xn = in ) kifejez´esekhez hasonl´ o val´osz´ın˝ us´egeket szeretn´enk meghat´arozni mindenf´ele felt´etel n´elk¨ ul. Ezt u ´ gy tudjuk megtenni, hogy feltessz¨ uk, hogy a 0 id˝oben adott valamilyen kiindul´ asi eloszl´as, azaz adott az X0 -nak az eloszl´asa. Ezt az eloszl´ast kezdeti eloszl´asnak nevezz¨ uk. A kezdeti eloszl´as megad´ as´at technikailag u ´ gy tessz¨ uk meg, hogy megadunk egy ´ gy, hogy az i-dik elem ´eppen annak a val´osz´ın˝ us´ege, hogy a 0 sorvektort, a-t, azaz a = [ai , i ∈ S], u id˝oben a Markov-l´ anc az i ´ allapotban van: P(X0 = i) = ai ,
i ∈ S.
3. p´ elda. P´eld´ aul, ha P(X0 = i0 ) = 1, akkor ez azt jelenti, hogy a Markov-l´anc az i0 ´allapotb´ol indul. Vagy tekints¨ uk a 1. ´ abr´ aban defini´alt Markov-l´ancot. Ha feltessz¨ uk, hogy kezdetben minden ´allapot 1 , i = 1, 2, . . . , 10, akkor annak a val´ ın˝ us´ege, hogy az els˝o l´ep´es ugyanolyan val´ osz´ın˝ u, azaz ai = 10 osz´ 1 1 1 1 1 + + . ut´an a 3-as ´ allapotban van az a3 P33 + a2 P23 + a1 P13 = 10 = 2 4 4 10
• Ekkor a (2) egyenl˝ os´eghez hasonl´ oan (imm´aron felt´etel n´elk¨ ul)
P (Xn = in , Xn−1 = in−1 . . . , X2 = i2 , X1 = i1 X1 = i0 ) = P(X0 = i0 )Pi0 i1 Pi1 i2 . . . Pin−1 in azaz P(X0 = i0 ) = ai0 miatt P (Xn = in , Xn−1 = in−1 . . . , X2 = i2 , X1 = i1 X1 = i0 ) = ai0 Pi0 i1 Pi1 i2 . . . Pin−1 in 4. p´ elda. Tekints¨ uk a 1. ´ abr´ aban defini´alt Markov-l´ancot. Ha feltessz¨ uk, hogy kezdetben ai = 5 111 i = 1, 2, . . . , 10, akkor annak a val´ osz´ın˝ us´ege, hogy sorrendben az 5112 utat teszi meg az 55 3 2 4.
i 55 ,
• Most m´ar, hogy adott egy a kezdeti eloszl´as, k´epesek vagyunk meghat´arozni Xn eloszl´as´at. Teh´at meg kell adnunk P(Xn = j)-t minden j ∈ S eset´en. A teljes val´osz´ın˝ us´eg t´etel´et haszn´alva: X X (n) P(Xn = j) = P(Xn = j | X0 = i)P(X0 = i) = ai Pij . i∈S
i∈S
2
Mivel ennek az ¨ osszegnek ugyanolyan a strukt´ ur´aja, mint a m´atrix szorz´ asnak ez´ert ez´ert X (n) P(Xn = j) = ai Pij = [aP n ]j , i∈S
azaz amit kapunk az a aP n sorvektor j-dik eleme. • Teh´at Xn eloszl´ as´ at egy sorvektork´ent k´epzelhetj¨ uk el, ahol a sorvektor j-dik koordin´at´aja a P(Xn = j) val´osz´ın˝ us´eg. Ez f¨ ugg a kezdeti eloszl´ ast´ ol. Ha jel¨olni szeretn´enk a kezdeti eloszl´ast´ ol val´o f¨ ugg´est, akkor a Pa (Xn = j) kifejez´est ´ırjuk.
2.
Markov-l´ anc ´ allapoteres felbont´ asa
A Markov-l´anc ´ allapotter´et szeretn´enk felbontani olyan oszt´alyokra, amelyek ha nagyon sok´ aig n´ezz¨ uk a l´ anc fejl˝ od´es´et, akkor l´enyegesen m´ashogy viselkednek. Ehhez el˝osz¨ or defini´aljunk k´et rel´aci´ ot. 2. defin´ıci´ o. j el´erhet˝ o az i ´ allapotb´ ol, jelben i → j, ha l´etezik pozit´ıva val´osz´ın˝ us´eg˝ uu ´ t ib-˝ol j-be, azaz l´etezik egy n, hogy P(Xn = j | X0 = i) > 0. 3. defin´ıci´ o. i ´erintkezik a j ´ allapottal, jelben i ↔ j, ha i el´erhet˝o jb˝ ol, ´es j is el´erhet˝o az i-b˝ol 2. ´ all´ıt´ as. Az ´erintkez´esi rel´aci´ o ekvivalencia rel´aci´ o, azaz, (1) reflex´ıv i ↔ i, (2) szimmetrikus i ↔ j ⇒ j ↔ i, ´es (3) tranzit´ıv i ↔ j ´es j ↔ k ⇒ i ↔ k. Ennek az a k¨ovetkezm´enye, hogy az egym´ assal ´erintkez˝o ´allapotok egy oszt´alyba tartoznak. A 1. ´abr´ an defini´alt Markov-l´ anc eset´en 3 oszt´aly van: C1 = {1, 2, 3}, C2 = {4, 5, 6}, C3 = {7, 8, 9, 10}. 4. defin´ıci´ o. Ha egy oszt´alyb´ ol nem megy ki pozit´ıv val´osz´ın˝ us´eg˝ uu ´ t, akkor z´ artnak nevezz¨ uk. A p´eld´ aban a C1 ´es a C3 oszt´aly z´ art. Minden oszt´alyra megmondhat´ o az, hogy mi a peri´odusa, ´es az, hogy visszat´er˝o-e. Ezeket defini´aljuk most. 5. defin´ıci´ o. Az i ´ allapot peri´ odusa d(i) a {n : P (Xn = i | X0 = i) > 0} halmaz legnagyobb k¨oz¨os oszt´oja. Ha a peri´odus 1, azaz d(i) = 1, akkor azt mondjuk, hogy az i ´allapot aperiodikus. Bebizony´ıthat´ o, hogy ha egy i ´ allapot peri´odusa d(i) = d, akkor elegend˝oen sok id˝o ut´an minden n sz´amra (nd) > 0, azaz, d l´ep´esenk´ent mindig visszat´er pozit´ıv val´osz´ın˝ us´eggel, ha az i ´allapotb´ol teljes¨ ul, hogy Pii indult a Markov-l´ anc. Term´eszetesen ha d(i) = 1, akkor ez azt jelenti, hogy egy id˝o ut´an mindig pozit´ıv val´osz´ın˝ us´eggel (lehet, hogy egyre cs¨ okken˝o) tart´ ozkodik az i ´allapotban, ha az i ´allapotb´ol indult a Markovl´anc. 6. defin´ıci´ o. Egy i ´ allapot visszat´er˝ o, ha i-b˝ol indulva 1 val´osz´ın˝ us´eggel visszat´er, azaz P(∃nXn = i | X0 = i) = 1. Egy ´allapot a ´tmeneti, ha nem visszat´er˝ o. 3. ´ all´ıt´ as. A peri´odus ´es a visszat´er˝ os´eg oszt´alytulajdons´ ag. Azaz, az egy oszt´alyban l´ev˝ o ´allapotoknak ugyanaz a peri´odusa. Tov´abb´a, az egy oszt´alyban l´ev˝ o ´allapotok vagy mind visszat´er˝ok, vagy mind ´atmenetiek. A 1. ´abr´ an defini´alt Markov-l´ anc eset´en a C1 ´es a C2 oszt´aly peri´odusa 1, m´ıg a C3 oszt´aly peri´odusa 2. Tov´abb´a, a C1 ´es a C3 oszt´aly visszat´er˝ o, m´ıg a C2 oszt´aly ´atmeneti. Ennek a k¨ovetkez˝o az oka. ol ´ all´o oszt´aly z´ art, akkor visszat´er˝o. Ha megy ki bel˝ole pozit´ıv val´osz´ın˝ us´eg˝ u 4. ´ all´ıt´ as. Ha egy v´eges sok elemb˝ u ´ t, akkor visszat´er˝ o.
3
Ez ut´obbi ´ all´ıt´ as az´ert igaz szeml´eletesen, mert egy ilyen pozit´ıv val´osz´ın˝ us´eg˝ uu ´ t “kipump´ alja az ott tart´ozkod´ as val´ osz´ın˝ us´eg´et az oszt´alyb´ ol”. Az is bebizony´ıthat´o, hogy egy v´eges elemb˝ ol ´all´o ´atmeneti oszt´alyban tart´ozkod´ as val´ osz´ın˝ us´ege exponenci´ alisan cs¨okken. Pontosabban, ha C egy v´eges ´atmeneti oszt´aly ´es i ∈ C akkor, P(Xn ∈ C | X0 = i) ≤ Kδ n , ahol K > 0 ´es 0 < δ < 1. ´ Altal´ aban az S ´ allapott´er felbonthat´ o S = T1 ∪ T2 ∪ · · · ∪ C1 ∪ C2 ∪ . . . oszt´alyok uni´oj´ ara, ahol Ti oszt´alyok jel¨ olik az ´atmeneti oszt´alyokat, ´es Ci jel¨olik a visszat´er˝o oszt´alyokat. 7. defin´ıci´ o. Ha a Markov-l´ anc egy oszt´alyb´ol ´alla, akkor azt mondjuk, hogy irreducibilis (felbonthatatlan). A visszat´er˝ o oszt´alyok z´ artak, nem megy ki bel˝ol¨ uk ´el. Ha a Markov-l´ anc egy z´ art oszt´alyb´ ol indul, akkor v´egig abban az oszt´alyban marad. Ha a Markov-l´ anc egy ´ atmeneti oszt´alyb´ol indul, akkor v´eges sok l´ep´es alatt 1 val´osz´ın˝ us´eggel elhagyja.
3.
Stacion´ arius eloszl´ as
8. defin´ıci´ o. Egy X0 , X1 , . . . Markov-l´ ancot (er˝ osen) stacion´arius folyamatnak nevez¨ unk, ha minden n ≥ 1, m ≥ 1, ´es i0 , i1 , . . . , in ∈ S ´ allapotsorozat eset´en P (X0 = i0 , X1 = i1 , . . . , Xn = in ) = P (Xm = i0 , Xm+1 = i1 , . . . , Xm+n = in ) . Ez azt jelenti, hogy egy v´eges trajekt´oria (i0 , i1 , . . . , in ) val´osz´ın˝ us´ege minden id˝oben ugyanaz allapott´eren adott egy eloszl´as (π = [πi , i ∈ S]), akkor stacion´arius 9. defin´ıci´ o. Ha π sorvektor az S ´ eloszl´asnak h´ıvjuk, ha πP = π. (3) Figyelj¨ uk meg, hogy ez azt jelenti, hogy X0 eloszl´asa (P(Xn = j) = πj , miden j ∈ S) megegyezik X1 eloszl´as´aval (P(Xn = j) = [πP ]j , miden j ∈ S) Ennek az a k¨ovetkezm´enye, hogy minden n-re Xn -nek ugyanaz az eloszl´asa: P(Xn = j) = πj ,
∀n ≥ 0, ∀j ∈ S,
ugyanis, ahogy m´ar kor´ abban fel´ırtuk Xn eloszl´asa fel´ırhat´ o πP n sorvektor alakban. Tov´abb´a, a (3)-b´ol az k¨ovetkezik, hogy nem csak egy hatv´anyra, hanem tetsz˝ oleges n-re igaz, hogy πP n = π. Bizony´ıthat´ oa arius eloszl´ as, ´es ez a Markov-l´anc kezdeti eloszl´asa (a = π), akkor az X0 , X1 , . . . 5. ´ all´ıt´ as. Ha π stacion´ Markov-l´anc stacion´ arius. ´ Erdekes, hogy ha anc irreducibilis ´es aperiodikus, akkor az 1. t´ etel. Ha egy Markov-l´ yP = y saj´at´ert´ek egyenletnek l´etezik egyetlen megold´asa. K´et egym´ ast kiz´ar´ o eset lehets´eges: P (1) Ha az y sorvektor elemeinek az ¨ osszege v´eges, azaz i∈S yi < ∞, akkor l´etezik egyetlen stacion´arius eloszl´as π, ahol yj πj = P i∈S yi pozit´ıv sz´am.
4
P
yi = ∞, akkor nem l´etezik stacion´arius eloszl´as. P 1. megjegyz´ es. Fontos megjegyz´es, hogy ha az ´allapott´er v´eges, akkor az i∈S yi ¨osszeg automatikusan v´eges, ´ıgy minden irreducibilis ´es aperiodikus Markov-l´ancnak l´etezik stacion´arius eloszl´asa.
(2) Ha az y sorvektor elemeinek az ¨ osszege v´eges, azaz
i∈S
5. p´ elda. Tekints¨ uk a 1. ´ abr´ an defini´alt Markov-l´ancot megszor´ıtva a C1 oszt´alyra. Ez egy irreducibilis, aperiodikus Markov-l´ anc. Hat´ arozzuk meg a stacion´arius eloszl´as´at. Ehhez meg kell oldani az 1/2 1/4 1/4 [π1 π2 π3 ] 1/4 1/2 1/4 = [π1 π2 π3 ] 1/2 0 1/2 π1 + π2 + π3 = 1 egyenletrendszert. Azt kapjuk, hogy π1 =
4 9,
π2 = 29 , π3 = 93 .
6. p´ elda. Legyen S = {0, 1, 2, . . . }. Legyen adott egy p1 , p2 , . . . sorozat, ahol 0 < pi < 1 teljes¨ ul minden i = 1, 2, . . . sz´ amra. Tekints¨ uk a k¨ovetkez˝o Markov-l´ ancot az S ´allapott´eren. Pi,i+1 = pi ,
Pi,i−1 = 1 − pi =: qi ,
ha i = 1, 2, . . . ´es
P01 = 1. Hat´ arozzuk meg, hogy mikor l´etezik a Markov-l´ancnak stacion´arius eloszl´asa. ´Irjuk fel a stacion´arius eloszl´ast. Megold´ as: Az 1. t´etel alapj´ an az yP = y egyenletet kell megoldani els˝o l´ep´esben. Azt kapjuk, hogy y0 yj
= =
y1 q1 yj+1 qj+1 + yj−1 pj−1 ,
j ≥ 1.
Ebb˝ol egy rekurzi´ot lehet kapni yj -kre. pj + qj = 1 miatt azt kapjuk, hogy
yj+1 qj+1 − yj pj = yj qj − yj−1 pj−1 ,
y0 p0 = y1 q1 j ≥ 1.
A szomsz´edos sorokat ¨ osszeadva, majd egyszer˝ us´ıtve azt kapjuk, hogy yj+1 qj+1 = yj pj , amib˝ol a rekurzi´o az yj+1 =
j ≥ 0,
p0 p1 . . . pj y0 , q1 q2 . . . qj+1
j≥0
alakot ¨olti. Ekkor a 1. t´etel szerint pontosan akkor van stacion´arius eloszl´as, ha yj -k ¨osszege v´eges, azaz ∞ X
yj /y0 =
j=0
∞ X p0 p1 . . . pj < ∞. q q . . . qj+1 j=0 1 2
Abban a speci´ alis esetben, mikor pi = p r¨ogz´ıtett sz´am (qi = q := 1 − p), akkor ez a felt´etel az p
∞ j X p j=0
q
=p
1 1−
p q
< ∞.
alakot ¨olti. Ez akkor teljes¨ ul, ha p < 12 . Ekkor a stacion´arius eloszl´as πj = ρj π0 , ahol ρ = pq .
5
2. t´ etel. Ha egy Markov-l´ anc irreducibilis ´es aperiodikus ´es l´etezik stacion´arius eloszl´asa, akkor Xn eloszl´asa n n¨ oveked´es´evel konverg´ al a stacion´ arius eloszl´ashoz f¨ uggetlen¨ ul att´ ol, hogy mi a kezdeti eloszl´as. Pontosabban, Pa (Xn = j) → πj ,
n → ∞,
vagy m´atrixosan megfogalmazva aP n → π,
n → ∞,
ahol a sorvektorok konvergenci´ aja azt jelenti, hogy minden koordin´at´aban konverg´ al. Nagyon fontos tulajdons´ aga v´eges ´ allapotter˝ u Markov-l´ancoknak, hogy a fenti konvergencia exponenci´ alisan gyors, azaz 3. t´ etel. Ha egy v´eges ´ allapotter˝ u Markov-l´ anc irreducibilis ´es aperiodikus (ekkor l´etezik stacion´arius eloszl´asa), akkor Pa (Xn = j) − πj ≤ Cδ n ,
ahol C > 0 ´es 0 < δ < 1. Vagy m´atrixosan megfogalmazva, minden j ∈ S ´allapotra |[aP n ]j − πj | ≤ Cδ n .
2. megjegyz´ es. A fenti exponenci´ alis konvergencia nem csak v´eges ´allapotter˝ u Markov-l´ancokra igaz. Bizonyos felt´etelek mellett v´egtelen ´ allapotter˝ u Markov-l´ancokra is teljes¨ ul.
4.
Ergod-t´ etel Markov-l´ ancokra
Legyen X0 , X1 , . . . egy Markov-l´ anc S ´ allapott´errel. Tov´abb´a, adott egy val´os ´ert´ek˝ u f k¨olts´egf¨ uggv´eny az ´allapotokon ´ertelmezve: f :S→R Ha a Markov-l´ ancnak adott egy i0 i1 . . . in trajekt´ori´aja, akkor ennek a trajekt´ori´anak a k¨olts´ege f (i0 ) + f (i1 ) + · · · + f (in ). Ha nem hat´arozzuk meg a trajekt´ori´at, akkor az els˝o n + 1 ´allapot k¨olts´ege egy val´osz´ın˝ us´egei v´altoz´ o f (X0 ) + f (X1 ) + · · · + f (Xn ). Ekkor egy l´ep´esre jut´o ´ atlagos k¨olts´eg f (X0 ) + f (X1 ) + · · · + f (Xn ) . n+1 Arra vagyunk k´ıv´ ancsiak, hogyha a Markov-l´ancot v´egtelen sok´aig futtatjuk, akkor mi lesz az egy l´ep´esre jut´o k¨olts´eg, vagy m´ask´ent a hossz´ ut´ av´ ua ´tlagos k¨olts´eg: f (X0 ) + f (X1 ) + · · · + f (Xn ) n+1 Erre a v´alaszt a k¨ovetkez˝o t´etel adja meg. lim
n→∞
4. t´ etel. Legyen X0 , X1 , . . . egy irreducibilis, aperiodikus Markov-l´anc, amelynek l´etezik stacion´arius eloszl´asa, π. Tov´abb´a legyen adott egy f : S → R k¨olts´egf¨ uggv´eny u ´ gy, hogy a stacion´arius eloszl´as szerinti ´atlaga v´eges, X f (i)πi < ∞. i∈S
Ekkor a hossz´ ut´av´ u´ atlagos k¨olts´eg egyszer˝ uen sz´amolhat´ o, f (X0 ) + f (X1 ) + · · · + f (Xn ) X = f (i)πi . n→∞ n+1 lim
i∈S
7. p´ elda. Tekints¨ uk a 1. ´ abr´ an defini´alt Markov-l´ancot megszor´ıtva a C1 oszt´alyra. Vezess¨ uk be a k¨ovetkez˝o k¨olts´egf¨ uggv´enyt: f (1) = 10, f (2) = 20, f (3) = 40. Hat´ arozzuk meg a Markov-l´ anc l´ep´eseinek hossz´ ut´av´ u ´atlagos k¨olts´eg´et. Az 4. t´etelb˝ol k¨ovetkezik, hogy ehhez ki kell sz´amolni a stacion´ arius eloszl´ ast. Az 5. p´eld´ aban ezt kisz´ amoltuk. Teh´at a 4. t´etel alapj´an a v´alasz 2 3 4 10 + 20 + 40 . 9 9 9 6
5.
Reverzibilis Markov-l´ ancok
A 3. t´etelbeli gyors konvergenci´ at felhaszn´alhatjuk arra, hogy egy tetsz˝ oleges, v´eges S halmazon adott π eloszl´asb´ ol gener´ aljunk mint´ at. A K´es˝ obb majd ejt¨ unk r´ola sz´ot, hogy mi´ert fontos, hogy meg tudjunk oldani ilyen t´ıpus´ u feladatokat. Azt fogjuk tenni, hogy megadunk egy Markov-l´ancot, amelynek a stacion´arius eloszl´asa ´eppen π. Ehhez el˝osz¨ or reverzibilis/megford´ıthat´ o Markov-l´ancokat tanulm´anyozzuk. 10. defin´ıci´ o. Egy X0 , X1 , . . . , XT Markov-l´anc megford´ıt´asa az X0∗ , X1∗ , . . . , XT∗ folyamat, ahol Xt∗ = XT −t 6. ´ all´ıt´ as. Az X0∗ , X1∗ , . . . , XT∗ folyamat Markov-l´anc. Bizony´ıt´ as. A megford´ıt´ as defin´ıci´oja szerint: ∗ ∗ P(Xt+1 = j | Xt∗ = i, Xt−1 = it−1 , . . . , X0∗ = i0 ) =
= P(XT −(t+1) = j | XT −t = i, XT −(t−1) = it−1 , . . . , XT = i0 ). Mivel adott jelen, XT −t = i, mellett a Markov l´anc j¨ov˝ oje (XT −(t−1) = it−1 , . . . , XT = i0 ) ´es a m´ ultja (XT −(t+1) = j) f¨ uggetlenek, ez´ert a jobboldal egyenl˝ o P(XT −(t+1) = j | XT −t = i) val´osz´ın˝ us´eggel, ami ∗ pedig ´eppen P(X(t+1) = j | Xt∗ = i). Azaz a megford´ıtott folyamat is Markov-l´anc. 7. ´ all´ıt´ as. Ha az X0 , X1 , . . . , XT Markov-l´ anc stacion´arius, akkor a megford´ıtott Markov-l´anc is stacion´arius, Pij∗ =
Pji πj πi
(4)
´atmenetval´osz´ın˝ us´eggel, ahol π az eredeti Markov-l´anc stacion´arius eloszl´asa. Proof. A Bayes-t´etelt haszn´alva, majd azt, hogy a Markov-l´anc a stacion´arius eloszl´asb´ ol indul, ´ıgy minden n-re P(Xn = j) = πj . ∗ Pij∗ = P(Xt+1 = j | Xt∗ = i) = P(XT −t−1 = j | XT −t = i) =
=
P(XT −t
P(XT −t−1 = jXT −t = i) = P(XT −t = i) = i | XT −t−1 = j)P(XT −t−1 = j) Pji πj . = P(XT −t = i) πi
Ezek ut´an defini´aljuk ezen alfejezet legfontosabb fogalm´at 11. defin´ıci´ o. Egy X0 , X1 , . . . , XT Markov-l´ancot megford´ıthat´onak nevez¨ unk, ha eloszl´ asa megegyezik a megford´ıt´as´anak eloszl´ as´ aval, azaz Pij∗ = Pij . A (4) egyenletb˝ ol k¨ovetkezik, hogy a megford´ıthat´o Markov-l´anc ´atmenetval´osz´ın˝ us´eg´ere fen´all Pij∗ =
Pji πj = Pij , πi
m´ask´eppen πj Pji = πi Pij ,
minden i, j ∈ S.
(5)
Ha ez az egyenl˝ os´eg fenn´all egy Markov-l´ ancra, akkor a Markov-l´anc megford´ıthat´o. • A megford´ıthat´ o Markov-l´ ancok reprezent´ alhat´ok egy ir´ any´ıtatlan s´ ulyozott gr´afon val´o bolyong´assal a k¨ovetkez˝ok´eppen. Legyen adott egy gr´ af, ahol a cs´ ucspontok az S halmazzal vannak indexelve. Ha az i − j ´el be van h´ uzva, akkor az ´el s´ ulya legyen wij = wji > 0. Ekkor a bolyong´as a k¨ovetkez˝ok´eppen fejl˝odik. Ha az n-dik l´ep´esben az i ´ allapotban van, akkor wij Pij = wi val´osz´ın˝ us´eggel l´ep a j ´ allapotba a k¨ovetkez˝o l´ep´esben, ahol X wi = wij i−j ´ el be van h´ uzva
7
´Igy egy Markov-l´ ancot defini´altunk, amelynek a stacion´arius eloszl´asa πj = ahol w=
wj , w
X
wi
i∈S
a s´ ulyok ¨osszege. Azt, hogy ez a stacion´ arius eloszl´as, l´atszik a k¨ovetkez˝o ´all´ıt´as bizony´ıt´as´ab´ol. anc reverzibilis. 8. ´ all´ıt´ as. A fent defini´alt Markov-l´ Proof. El´eg ellen˝ orizni a (5) egyenl˝ os´eg megl´et´et. Ez viszont teljes¨ ul: πj Pji =
wj wji wji wij wi wij = = πi Pij . = = w wj w w w wi
8. p´ elda. Mutassuk meg, hogy az 6. p´eld´ aban defini´alt Markov-l´anc reverzibilis.
• Markov chain Monte Carlo (MCMC). Ebben a pontba ´ırjuk le az alfejezet kiindul´ asi probl´em´ aj´ anak unk egy reverzibilis Markovmegold´as´at. Teh´at, ha adott egy S ´ allapott´er ´es egy π eloszl´as S-en, akkor k´esz´ıt¨ anak n¨ ovel´es´evel a l´ancot, amelynek a stacion´ arius eloszl´ asa ´eppen π. Mivel S v´eges, a l´ep´esek (n) sz´am´ Markov-l´anc n id˝oben vett eloszl´ asa exponenci´ alisan gyorsan konverg´ al a stacion´arius eloszl´as´ahoz, π-hez. Teh´at, hogyan konstru´ alunk ilyen reverzibilis Markov-l´ancot? Meg kell hat´arozni P -t, az ´atment val´osz´ın˝ us´eg m´atrixot. Induljunk ki (5) karakteriz´aci´ ob´ol, azaz az ismeretlen Pij -nek ki kell el´eg´ıteni a πj Pij = Pji πi egyenl˝ os´eget. Vegy¨ uk a logaritmus´at: log Pij − log Pji = log πj − log πi . ´ Atrendezve azt kapjuk, hogy log Pij = log Pji + log πj − log πi , tov´abb´a
1 1 log Pij − (log πj − log πi ) = log Pji + (log πj − log πi ) 2 2 1 1 log Pij − (log πj − log πi ) = log Pji − (log πi − log πj ). 2 2 Legyen S ′ egy |S| × |S| m´atrix, amelynek az ij-dik eleme legyen 1 ′ Sij := log Pij − (log πj − log πi ), 2
(6)
ha i 6= j.
Ekkor az (6) egyenl˝ os´eg alapj´ an S ′ szimmetrikus m´atrix (i ´es j felcser´el´es´evel ugyanazt a sz´amot kapjuk). Ekkor az ismeretlen Pij ´ atmenetval´ osz´ın˝ us´egekre teljes¨ ul a 1 1 ′ ′ log Pij = Sij + (log πj − log πi ) = Sij − (log πi − log πj ), 2 2
ha i 6= j. ′
os´eg defini´al minden egyenl˝ os´eg. Ekkor bevezetve az S szimmetrikus m´atrixot, amelyet az Sij = eSij egyenl˝ ij p´ arra, azt kapjuk, hogy 1 πi Pij = Sij e− 2 , ha i 6= j. πj
8
Most meg kell v´alasztanunk Pii ´ atmenet val´osz´ın˝ us´egeket, i ∈ S. Arra kell vigy´aznunk, hogy ne legyen P P > 1. Mivel S -k helyett tetsz˝ o leges δ > 0 sz´amszorosa is j´o szimmetrikus m´atrixnak, ez´ert ij j:j6=i ij legyenek Sij -k (i, j ∈ S) akkor´ ak, hogy X
Pij ≤ 1,
azaz
j:j6=i
1
X
Sij e− 2
X
Pij .
j:j6=i
πi ≤ 1. πj
Ekkor m´ar defini´alhatjuk Pii -t, legyen Pii := 1 −
j:j6=i
Szok´asos v´alaszt´as, ha az S m´atrixnak az incidencia m´atrix C, valamely δ-szoros´at vessz¨ uk (δ > 0). Eml´ekeztet˝ou ¨ l, a incidencia m´atrix egy n´egyzetes m´atrix, amely a cs´ ucsok k¨oz¨otti kapcsolatot ´ırja le u ´ gy, hogy 1 ha az i − j ´el be van h´ uzva, Cij = 0 k¨ ul¨onben. Ekkor Pij = δCij
9
πi . πj
