Markovin ketju Monte Carlo -simulointi ja Peskunin järjestys

Markovin ketju Monte Carlo -simulointi ja Peskunin j¨ arjestys

Santeri Parkkinen

Matematiikan pro gradu -tutkielma Jyv¨ askyl¨ an yliopisto

Matematiikan ja tilastotieteen laitos

Kev¨ at 2019

Tiivistelm¨ a

Jyv¨askyl¨an yliopisto

Matematiikan ja tilastotieteen laitos Matematiikan pro gradu -tutkielma

Markovin ketju Monte Carlo -simulointi ja Peskunin j¨arjestys, 42 s., liitteit¨a 19 s.

Santeri Parkkinen Toukokuu 2019

T¨am¨an tutkielman tavoitteena on esitell¨a Markovin ketju Monte Carlo -simulointi ¨a¨arellisess¨a tila-avaruudessa ja k¨asitell¨a simulointialgoritmien vertailuun liittyv¨a¨a ongelmaa. Markovin ket- ju Monte Carlo -simuloinnissa funktion odotusarvolle lasketaan approksimaatioita simuloitua Markovin ketjua apuna k¨aytt¨aen. Usein simulointi voidaan tehd¨a useammalla kuin yhdell¨a algo- ritmilla ja halutaan selvitt¨a¨a, mik¨a algoritmi soveltuu teht¨av¨a¨an parhaiten.

Kun simulaatioaskelten m¨a¨ar¨a l¨ahestyy ¨a¨aret¨ont¨a, Markovin ketju Monte Carlo -estimaatti sup- penee melkein varmasti kohti odotusarvon oikeaa arvoa k¨aytetyst¨a simulointialgoritmista riippu- matta. K¨ayt¨ann¨oss¨a Markovin ketju Monte Carlo -simulointi tuottaa kuitenkin vain odotusar- von approksimaation, koska mik¨a¨an todellinen simulointi ei voi jatkua ¨a¨arett¨om¨an pitk¨a¨an. Vain

¨a¨arellisen monen simulaatioaskeleen k¨aytt¨o aiheuttaa virheen, joka on luonteeltaan satunnainen:

virhe kuuluu tietylle v¨alille jollakin todenn¨ak¨oisyydell¨a. On luonnollista kysy¨a, miten approksi- maation tarkkuus riippuu simulointialgoritmista. Kaikki algoritmit antavat odotusarvolle arvion halutulla tarkkuudella, jos simulointia jatketaan riitt¨av¨an kauan. Jotkut algoritmit tuottavat kuitenkin tarkkoja approksimaatioita nopeammin kuin toiset, mik¨a on motivaatio algoritmien vertailulle. Ei kuitenkaan ole aivan selv¨a¨a, miten vertailu pit¨aisi k¨ayt¨ann¨oss¨a tehd¨a. Halutun tarkkuuden saavuttamiseksi vaadittavaa aikaa on vaikea arvioida, eiv¨atk¨a pelk¨at arviot edes ole riitt¨av¨a perusta algoritmien vertailulle. Voi esimerkiksi k¨ayd¨a niin, ett¨a arvioitu alaraja algo- ritminP vaatimalle ajalle on pienempi kuin alaraja algoritminQvaatimalle ajalle, mutta silti algoritmi Qp¨a¨asee haluttuun tarkkuuteen nopeammin kuin algoritmi P. Pelk¨at alarajat eiv¨at siis kerro tarpeeksi vaadittavien aikojen todellisista arvoista. Arvioiden sijaan tarvitaan jokin eksakti riippuvuus simulointivirheen ja algoritmin v¨alille.

Kriteeri, jonka suhteen algoritmien vertailu tehd¨a¨an, johdetaan Markovin ketjujen keskeist¨a raja- arvolausetta k¨aytt¨aen. Keskeinen raja-arvolause mahdollistaa simulointivirheiden todenn¨ak¨oi- syyksien raja-arvon eksaktin laskemisen tietyss¨a erikoistapauksessa. Tarkastelu osoittaa, ett¨a algoritmien vertailemiseksi kannattaa tutkia niiden asymptoottisia variansseja: kahdesta algo- ritmista se, jonka asymptoottinen varianssi annetulle funktiolle on pienempi, soveltuu parem- min kyseisen funktion odotusarvon simulointiin. Kriteerin ongelmana on, ett¨a sen soveltaminen ei ole ihan suoraviivaista. K¨ayt¨ann¨oss¨a algoritmeista tiedet¨a¨an vain niiden siirtym¨atodenn¨ak¨oi- syysmatriisit, joten algoritmien vertailemiseksi t¨aytyy selvitt¨a¨a, miten asymptoottinen varians- si riippuu siirtym¨atodenn¨ak¨oisyysmatriisista. T¨ass¨a tutkielmassa tarkastelu rajataan k¨a¨antyviin Markovin ketjuihin, jolloin kyseinen riippuvuus voidaan selvitt¨a¨a funktionaalianalyysin tuloksia hy¨odynt¨aen. T¨am¨an j¨alkeen vertailu onnistuu tietyss¨a erikoistapauksessa Peskunin j¨arjestyst¨a k¨aytt¨am¨all¨a. Peskunin j¨arjestyksen sovelluksena osoitetaan, ett¨a Metropolis–Hastings -algoritmi on parempi kuin Barkerin algoritmi.

Sis¨ alt¨ o

1 Markovin ketju ¨a¨arellisess¨a tila-avaruudessa 4

2 Invariantti jakauma ja tasainen ergodisuus 6

3 Markovin ketju Monte Carlo -simulointi 13

4 Siirtym¨atodenn¨ak¨oisyysmatriisin ominaisvektorit

ja -arvot 25

5 Peskunin j¨arjestys ja asymptoottisten varianssien vertailu 30

Liite A Markovin ketjujen perustuloksia 42

Liite B Funktionaalianalyysin tuloksia 50

Liite C Kroneckerin lemma 59

Viitteet 61

Johdanto

Stokastiikassa ja sen sovelluksissa usein vastaan tuleva ongelma on satunnaismuuttujan odo- tusarvon laskeminen. Aina odotusarvoa ei k¨ayt¨ann¨oss¨a ole mahdollista laskea suoraan satunnais- muuttujan jakaumaa k¨aytt¨aen edes tapauksessa, jossa satunnaismuuttujan tila-avaruus tiedet¨a¨an

¨a¨arelliseksi. Ongelmia ilmenee, jos tila-avaruus on hyvin suuri tai jos jakauman normitusvakio- ta ei tunneta. T¨allaisissa tilanteissa on kuitenkin usein mahdollista approksimoida odotusarvoa Markovin ketju Monte Carlo -simuloinniksi kutsuttua menetelm¨a¨a k¨aytt¨aen viel¨ap¨a niin, ett¨a simulointialgoritmi voidaan valita useasta eri vaihtoehdosta. T¨am¨an tutkielman tavoitteena on esitell¨a Markovin ketju Monte Carlo -simulointi ¨a¨arellisess¨a tila-avaruudessa sek¨a k¨asitell¨a algo- ritmien vertailuun liittyv¨a¨a ongelmaa.

Kun simulaatioaskelten m¨a¨ar¨a l¨ahestyy ¨a¨aret¨ont¨a, Markovin ketju Monte Carlo -estimaatti sup- penee melkein varmasti kohti odotusarvon oikeaa arvoa k¨aytetyst¨a simulointialgoritmista riippu- matta. K¨ayt¨ann¨oss¨a Markovin ketju Monte Carlo -simulointi tuottaa kuitenkin vain odotusar- von approksimaation, koska mik¨a¨an todellinen simulointi ei voi jatkua ¨a¨arett¨om¨an pitk¨a¨an. Vain

¨a¨arellisen monen simulaatioaskeleen k¨aytt¨o aiheuttaa virheen, joka on luonteeltaan satunnainen:

virhe kuuluu tietylle v¨alille jollakin todenn¨ak¨oisyydell¨a. On luonnollista kysy¨a, miten approksi- maation tarkkuus riippuu simulointialgoritmista. Kaikki algoritmit antavat odotusarvolle arvion halutulla tarkkuudella, jos simulointia jatketaan riitt¨av¨an kauan. Jotkut algoritmit tuottavat kuitenkin tarkkoja approksimaatioita nopeammin kuin toiset, mik¨a on motivaatio algoritmien vertailulle. Ei kuitenkaan ole aivan selv¨a¨a, miten vertailu pit¨aisi k¨ayt¨ann¨oss¨a tehd¨a. Halutun tarkkuuden saavuttamiseksi vaadittavaa aikaa on vaikea arvioida, eiv¨atk¨a pelk¨at arviot edes ole riitt¨av¨a perusta algoritmien vertailulle. Voi esimerkiksi k¨ayd¨a niin, ett¨a arvioitu alaraja algo- ritminP vaatimalle ajalle on pienempi kuin alaraja algoritminQvaatimalle ajalle, mutta silti algoritmi Qp¨a¨asee haluttuun tarkkuuteen nopeammin kuin algoritmi P. Pelk¨at alarajat eiv¨at siis kerro tarpeeksi vaadittavien aikojen todellisista arvoista. Arvioiden sijaan tarvitaan jokin eksakti riippuvuus simulointivirheen ja algoritmin v¨alille.

Osoittautuu, ett¨a tietyss¨a erikoistapauksessa Markovin ketjujen keskeinen raja-arvolause mah- dollistaa simulointivirheiden todenn¨ak¨oisyyksien raja-arvon eksaktin m¨a¨aritt¨amisen. Tarkaste- lun seurauksena n¨ahd¨a¨an, ett¨a algoritmien vertailemiseksi kannattaa tutkia niiden asymptoot- tisia variansseja: jos algoritmin P asymptoottinen varianssi funktiolle f on pienempi tai yht¨a suuri kuin algoritmin Q asymptoottinen varianssi funktiolle f, niin algoritmi P on parempi funktionf odotusarvon simulointiin kuin algoritmiQ. T¨allaisen vertailun tekeminen ei kuiten- kaan ole aivan ongelmatonta. L¨aht¨okohtaisesti simulointialgoritmeista tiedet¨a¨an nimitt¨ain vain niiden siirtym¨atodenn¨ak¨oisyysmatriisit, joten t¨aytyy selvitt¨a¨a, miten algoritmin asymptoottinen varianssi funktiolle f riippuu siirtym¨atodenn¨ak¨oisyysmatriisista. T¨ass¨a tutkielmassa tarkastelu rajataan k¨a¨antyviin Markovin ketjuihin, jolloin kyseinen riippuvuus voidaan selvitt¨a¨a funktio- naalianalyysin ty¨okaluja apuna k¨aytt¨aen. P¨a¨adyt¨a¨an lauseeseen, joka on sik¨ali ongelmallinen, ett¨a tyypillisess¨a Markovin ketju Monte Carlo -simuloinnin sovelluksessa k¨ayt¨oss¨a olevat tie- dot eiv¨at riit¨a algoritmien vertailuun. Ongelman ratkaisi Peter Peskun, joka keksi, miten kahden algoritmin asymptoottisten varianssien suuruusj¨arjestys voidaan erikoistapauksessa p¨a¨atell¨a suo- raan siirtym¨atodenn¨ak¨oisyysmatriisien alkioita tutkimalla. Oletetaan, ett¨a algoritmeja P ja Q vastaavat siirtym¨atodenn¨ak¨oisyysmatriisit ovat k¨a¨antyvi¨a saman invariantin jakauman suhteen.

Peskun osoitti, ett¨a jos algoritmia P vastaavan matriisin kaikki alkiot – diagonaalialkioita lu- kuun ottamatta – ovat suurempia tai yht¨a suuria kuin algoritmia Qvastaavan matriisin alkiot, niin algoritmin P asymptoottinen varianssi funktiolle f on pienempi tai yht¨a suuri kuin algo- ritminQ asymptoottinen varianssi funktiolle f. Johtop¨a¨at¨os on sama kaikille funktioille, joten t¨ast¨a seuraa, ett¨a algoritmiP on parempi kuin algoritmiQmink¨a tahansa funktion odotusarvon

approksimointiin. Nykyisin matriisin alkioita koskevaa ehtoa kutsutaan Peskunin j¨arjestykseksi.

Lauseensa sovelluksena Peskun osoitti, ett¨a Metropolis–Hastings -algoritmi on parempi kuin Bar- kerin algoritmi.

Tutkielman esitietoina lukijalta edellytet¨a¨an todenn¨ak¨oisyysteorian, lineaarialgebran ja funktio- naalianalyysin perusteiden tunteminen. Markovin ketjujen tunteminen sen sijaan ei ole aivan v¨altt¨am¨at¨ont¨a, sill¨a tarvittava m¨a¨ar¨a teoriaa sis¨altyy tutkielmaan. Kannattaa kuitenkin huoma- ta, ett¨a Markovin ketjujen perusominaisuuksia k¨asitell¨a¨an vain liitteess¨a A, ja varsinainen teksti keskittyy niihin tuloksiin, jotka tarvitaan Markovin ketju Monte Carlo -simuloinnin esitt¨amiseen.

My¨os funktionaalianalyysist¨a on melko kattava liite.

Rakenteeltaan tutkielma on seuraavanlainen: Luvussa 1 m¨a¨aritell¨a¨an siirtym¨atodenn¨ak¨oisyys- matriisi ja Markovin ketju ¨a¨arellisess¨a tila-avaruudessa. Luvussa 2 k¨ayd¨a¨an l¨api Markovin ketju Monte Carlo -simuloinnin esitt¨amiseen tarvittavia pohjatietoja. Keskeisi¨a k¨asitteit¨a ovat inva- riantti jakauma ja tasainen ergodisuus. Luvussa 3 perustellaan, miksi Markovin ketju Monte Carlo -simulointi toimii. Lis¨aksi m¨a¨aritell¨a¨an Metropolis–Hastings -algoritmi ja Barkerin algorit- mi ja osoitetaan, ett¨a ne ovat k¨a¨antyvi¨a invariantin jakaumansa suhteen. Lopuksi pohjustetaan algoritmien vertailuun liittyv¨a¨a ongelmaa. Luku 4 k¨asittelee siirtym¨atodenn¨ak¨oisyysmatriisien ominaisvektoreita ja -arvoja. T¨am¨a tarkastelu on tarpeen, jotta luvussa 5 voidaan hy¨odynt¨a¨a funktionaalianalyysin tuloksia asymptoottisen varianssin tutkimiseen. Luvussa 5 teht¨avien tar- kastelujen tuloksena saadaan lause, joka kertoo, miten asymptoottinen varianssi riippuu simu- lointialgoritmista. Luvussa 5 esitell¨a¨an my¨os Peskunin j¨arjestys ja selvitet¨a¨an, miten se liittyy asymptoottisten varianssien ja algoritmien vertailuun. Lopuksi Peskunin j¨arjestyksen sovellukse- na osoitetaan, ett¨a Metropolis–Hastings -algoritmi on parempi kuin Barkerin algoritmi.

Merkint¨ oj¨ a

• N₀={0,1,2, . . .}

• N={1,2,3, . . .}

• Z={. . . ,−2,−1,0,1,2, . . .}

• Olkoon P = [pi,j]i,j=1,2,...,n neli¨omatriisi sek¨a k∈N. Potenssimatriisin P^k alkio paikassa (i, j) onp^(k)_i,j.

• OlkoonP = [pi,j] matriisi.

– Josp_i,j≥0 kaikillaijaj, merkit¨a¨anP ≥0.

– Josp_i,j>0 kaikillaijaj, merkit¨a¨anP >0.

• Olkoonx= (x1, x2, . . . , x_n)∈Rⁿ vektori.

– Josxi≥0 kaikillai= 1,2, . . . , n, merkit¨a¨an x≥0.

– Josxi>0 kaikillai= 1,2, . . . , n, merkit¨a¨an x >0.

• Avaruuden Rⁿ luonnollisia kantavektoreita merkit¨a¨an tunnuksilla ei,i= 1,2, . . . , n. Vek- torinei j.komponentti on siis

e_i,j=

(1, josj=i 0, josj6=i .

• Avaruuden Rⁿ nollavektorille k¨aytet¨a¨an merkint¨a¨a ¯0.

• OlkoonS joukko. JoukonS osajoukkojen kokoelmaa merkit¨a¨an P(S) ={A|A⊂S}.

• Josx∈R, niin

⌊x⌋= max{n∈Z:n≤x}.

1 Markovin ketju ¨ a¨ arellisess¨ a tila-avaruudessa

T¨ass¨a luvussa m¨a¨aritell¨a¨an siirtym¨atodenn¨ak¨oisyysmatriisi ja Markovin ketju ¨a¨arellisess¨a tila- avaruudessa. Karkeasti ottaen Markovin ketju on jono satunnaismuuttujiaXk : Ω→S, jolla on se ominaisuus, ett¨a jokaisella ajanhetkell¨ak ∈N₀ todenn¨ak¨oisyys siirty¨a tilasta Xk =x tilaan X_k+1=yriippuu vain ketjun nykytilastaX_k =x, mutta ei siit¨a, miten nykytilaan on p¨a¨adytty.

SatunnaismuuttujatX0, X1, . . . , X_k−1eiv¨at siis vaikuta siirtym¨an X_k=x→Xk+1=y

todenn¨ak¨oisyyteen. Siirtym¨atodenn¨ak¨oisyysmatriisi puolestaan kirjaa kyseisten siirtymien to- denn¨ak¨oisyydet matriisin muotoon. T¨am¨a on mahdollista, kun ketjun tila-avaruus S on ¨a¨arel- linen, ja eritt¨ain hy¨odyllist¨a, koska siirtym¨atodenn¨ak¨oisyysmatriisin avulla Markovin ketjujen tutkiminen palautuu pitk¨alti matriisien tutkimiseen. Seuraavat m¨a¨aritelm¨at ovat l¨ahteest¨a [1].

M¨a¨aritelm¨a 1.1. Neli¨omatriisiP = [pi,j]i,j=1,2,...,n on siirtym¨atodenn¨ak¨oisyysmatriisi, jos (i) P ≥0

(ii) Pn

j=1p_i,j= 1kaikillai= 1,2, . . . , n.

Jos P = [pi,j]i,j=1,2,...,n on siirtym¨atodenn¨ak¨oisyysmatriisi, niin induktiolla on helppo todeta, ett¨a kaikilla k∈Nmy¨os potenssimatriisi P^k =h

p^(k)_i,ji

i,j=1,2,...,n on siirtym¨atodenn¨ak¨oisyysmat- riisi.

M¨a¨aritelm¨a 1.2. Olkoon(Ω,F,P) todenn¨ak¨oisyysavaruus,S={s1, s2, . . . , sn} ⊂Rja P = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi. Jono(Xk)^∞_k=0 satunnaismuuttujia

Xk: Ω→S

on Markovin ketju, jonka siirtym¨atodenn¨ak¨oisyysmatriisi onP, jos

(i) P(Xk+1=xk+1|Xk =xk, Xk−1=xk−1, . . . , X0=x0) = P(Xk+1=xk+1|Xk=xk) kaikil- la k∈N₀ ja kaikilla x₀, x₁, . . . , x_k+1∈S, joille

P(X0=x0, X1=x1, . . . , X_k =x_k)>0

(ii) P(Xk+1=s_j|X_k =s_i) =p_i,j kaikillai, j= 1,2, . . . , nja k∈N₀, joilleP(Xk=s_i)>0.

SatunnaismuuttujanX0jakaumaa kutsutaan Markovin ketjun(Xk)^∞_k=0alkujakaumaksi ja joukkoa S kutsutaan ketjun tila-avaruudeksi.

Jatkossa oletetaan, ett¨a Markovin ketjun tila-avaruus on reaalilukujen osajoukko, jossa on aina v¨ahint¨a¨an kaksi alkiota. Erityisesti siirtym¨atodenn¨ak¨oisyysmatriisi on aina v¨ahint¨a¨an kokoa 2×2.

Olkoon (Xk)^∞_k=0 Markovin ketju tila-avaruudella S = {s1, s2, . . . , sn} ja olkoon ketjun siir- tym¨atodenn¨ak¨oisyysmatriisiP = [pi,j]i,j=1,2,...,n. Samaistetaan satunnaismuuttujanXkjakauma

µ_k :S→[0,1], µk(x) =P(Xk =x), vektorin

µ^(k)=

µ^(k)₁ , µ^(k)₂ , . . . , µ^(k)_n

∈Rⁿ

kanssa, miss¨a

µ^(k)_i =µk(si) =P(Xk=si) kaikillai= 1,2, . . . , n.

OlkoonJ niiden indeksienj= 1,2, . . . , njoukko, joille p¨atee, ett¨a P(Xk =sj)>0.

T¨all¨oin kaikillal= 1,2, . . . , n

µ^(k+1)_l =P(Xk+1=sl) =P



{Xk+1=sl} ∩



 [n j=1

{Xk=sj}









=P



 [n j=1

({Xk+1=s_l} ∩ {X_k=s_j})



= Xn j=1

P(Xk+1=s_l, X_k=s_j)

=X

j∈J

P(Xk+1=s_l, X_k =s_j) =X

j∈J

P(Xk=s_j)P(Xk+1=s_l|X_k=s_j)

=X

j∈J

P(Xk =s_j)p_j,l= Xn j=1

P(Xk=s_j)p_j,l= Xn j=1

µ^(k)_j p_j,l=h µ^(k)Pi

l. (1)

N¨ain ollen vektorimuodossa p¨atee, ett¨a

µ^(k+1)=µ^kP. (2)

Yht¨al¨ost¨a (2) seuraa helposti induktiolla, ett¨a

µ^(k)=µ⁽⁰⁾P^k (3)

kaikillak∈N.

2 Invariantti jakauma ja tasainen ergodisuus

T¨ass¨a luvussa k¨ayd¨a¨an l¨api Markovin ketju Monte Carlo -simuloinnin esitt¨amiseen tarvittavia lauseita. Luvun p¨a¨atuloksia ovat Lause 2.1 ja Lause 2.2. Tulosten motivoimiseksi tarkastellaan lyhyesti seuraavaa ongelmaa l¨ahteen [1] esityst¨a mukaillen: Olkoon (Xk)^∞_k=0 Markovin ketju ja µ^(k)satunnaismuuttujanX_k jakauma. Halutaan selvitt¨a¨a, mill¨a ehdoilla on olemassa jakaumaπ siten, ett¨a

µ^(k)→π, kunk→ ∞.

Ongelman ratkaiseminen l¨ahtee liikkeelle rajajakaumakandidaatin etsimisest¨a. T¨am¨a onnistuu helposti: yht¨al¨on (2) mukaan

µ^(k+1)=µ^(k)P

kaikillak∈N₀, miss¨aP on ketjun siirtym¨atodenn¨ak¨oisyysmatriisi. N¨ain ollen n¨ahd¨a¨an, ett¨a jos rajajakaumaπ= lim_k→∞µ^(k) on olemassa, se toteuttaa yht¨al¨on

π= lim

k→∞µ^(k+1)= lim

k→∞

µ^(k)P

=

k→∞lim µ^(k)

P =πP.

T¨am¨a johtaa invariantin jakauman k¨asitteeseen:

M¨a¨aritelm¨a 2.1. Jakauma π ∈ Rⁿ on siirtym¨atodenn¨ak¨oisyysmatriisin P = [pi,j]i,j=1,2,...,n

invariantti jakauma, jos

π=πP.

Seuraavaksi osoitetaan, ett¨a jos Markovin ketjun siirtym¨atodenn¨ak¨oisyysmatriisilleP p¨atee, ett¨a P^m >0 jollakin m∈ N, niin yksik¨asitteinen invariantti jakauma π on olemassa ja sille p¨atee, ett¨aπ >0. Erotetaan osa todistuksesta lemmaksi my¨ohemp¨a¨a k¨aytt¨o¨a varten. Lemman 2.1 tulos on l¨ahteest¨a [2] ja todistus mukailee l¨ahteen todistusta.

Lemma 2.1. Olkoon P = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi siten, ett¨aP >0. Jos x∈Rⁿ siten, ett¨a xP =x, niin x≥0 taix≤0.

Todistus. Jos v¨aite on v¨a¨ar¨a, on olemassa indeksiti, j∈ {1,2, . . . , n}siten, ett¨axi<0 jaxj >0.

Kaikillak= 1,2. . . , n xk ≤ |xk|jaxi<0<|xi|, joten kaikilla l= 1,2, . . . , np¨atee, ett¨a Xn

k=1

x_kp_k,l=X

k6=i

x_kp_k,l+x_ip_i,l<X

k6=i

|x_k|p_k,l+|x_i|p_i,l= Xn k=1

|x_k|p_k,l. Vastaavastixk≥ − |xk|kaikilla k= 1,2, . . . , nja xj>0>− |xj|, joten

Xn k=1

xkpk,l>− Xn k=1

|xk|pk,l kaikillal= 1,2, . . . , n.

N¨ain ollen saadaan, ett¨a

Xn k=1

xkpk,l

<

Xn k=1

|xk|pk,l kaikillal= 1,2, . . . , n.

Toisaalta oletuksenxP =xnojalla x_l= [xP]_l=Pn

k=1x_kp_k,lkaikilla l= 1,2, . . . , n, joten Xn

l=1

|x_l|= Xn l=1

Xn k=1

x_kp_k,l

<

Xn l=1

Xn k=1

|x_k|p_k,l= Xn k=1

Xn l=1

|x_k|p_k,l= Xn k=1

|x_k| Xn

l=1

p_k,l= Xn k=1

|x_k|,

Lause 2.1. OlkoonP = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi siten, ett¨a P^m >0 jol- lakinm∈N. T¨all¨oin matriisillaP on yksik¨asitteinen invariantti jakaumaπ∈Rⁿ. Lis¨aksi p¨atee, ett¨a π >0.

Todistus. Olkoony= (y1, y2, . . . , yn)∈Rⁿ siten, ett¨ayk= 1 kaikillak= 1,2, . . . , n. T¨all¨oin [P y]_i=

Xn k=1

pi,kyk = Xn k=1

pi,k = 1 =yi kaikilla i= 1,2, . . . , n,

joten P y =y. Erityisesti luku 1 on matriisin P oikeanpuoleinen ominaisarvo. Koska matriisin vasemmanpuoleiset ja oikeanpuoleiset ominaisarvot ovat samat, on 1 my¨os matriisin P vasem- manpuoleinen ominaisarvo. On siis olemassa vektorix∈Rⁿ\{¯0}siten, ett¨axP =x. T¨ast¨a seuraa induktiolla, ett¨axP^k =xkaikilla k ∈N. ErityisestixP^m =x, joten soveltamalla Lemmaa 2.1 siirtym¨atodenn¨ak¨oisyysmatriisiinP^m>0 saadaan, ett¨ax≤0 taix≥0. Korvaamalla vektorix tarvittaessa vektorilla−xvoidaan olettaa, ett¨a x≥0. Koskaxei ole nollavektori, on olemassa indeksii∈ {1,2, . . . , n}siten, ett¨ax_i>0. T¨ast¨a seuraa, ett¨ax_j>0 kaikillaj = 1,2, . . . , n, sill¨a

xj= [xP^m]_j= Xn k=1

xkp^(m)_k,j ≥xip^(m)_i,j >0.

Olkoon

π= x

Pn j=1x_j, jolloin siisπ= (π1, π2, . . . , πn)∈Rⁿ siten, ett¨a

π_i = x_i Pn

j=1xj

kaikilla i= 1,2, . . . , n.

T¨all¨oin (i) πP =

Pnx

j=1xj

P = ^Pn¹

j=1xj (xP) = ^Pn^x

j=1xj =π, (ii) Pn

i=1πi=Pn i=1Pnxi

j=1xj =^Pn¹ j=1xj

Pn

i=1xi= 1 ja (iii) πi= ^Pn^xi

j=1xj >0 kaikillai= 1,2, . . . , n, koskaxi>0 kaikillai= 1,2, . . . , n, jotenπ∈Rⁿ on etsitty jakauma.

Osoitetaan viel¨a invariantin jakauman yksik¨asitteisyys. Oletetaan vastoin v¨aitett¨a, ett¨a on ole- massa invariantti jakaumaµ∈Rⁿ siten, ett¨aµ6=π. T¨all¨oin

(π−µ)P^m=πP^m−µP^m=π−µ,

joten Lemman 2.1 nojallaπ−µ≥ 0 taiπ−µ≤ 0. Oletetaan, ett¨a π−µ ≥0. Koska µ 6=π, on olemassa indeksi j ∈ {1,2, . . . , n} siten, ett¨a µj 6= πj. T¨all¨oin ehdon π−µ ≥0 nojalla on µj< πj, joten saadaan, ett¨a

1 = Xn i=1

µ_i<

Xn i=1

π_i= 1, mik¨a on ristiriita. Tapausπ−µ≤0 k¨asitell¨a¨an vastaavasti.

Lause 2.1 ratkaisee invariantin jakauman olemassaoloa koskevan kysymyksen. Voidaan my¨os osoittaa, ett¨a

k→∞lim µ^(k)=π,

jos P^m > 0 jollakinm ∈ N. Tulos ei kuitenkaan ole t¨am¨an tutkielman kannalta kovin oleelli- nen; ongelmaa tarkasteltiin l¨ahinn¨a invariantin jakauman k¨asitteen motivoimiseksi. Lis¨aksi nyt yht¨al¨on (3) perusteella on luonnollista kysy¨a, mit¨a tapahtuu matriiseille P^k, miss¨ak∈N, kun k→ ∞. Osoittautuu, ett¨a kaikilla i, j= 1,2, . . . , n

p^(k)_i,j →πj, kunk→ ∞,

viel¨ap¨a niin, ett¨a

p^(k)_i,j −π_j ≤Cβ^k

kaikilla k∈N, miss¨a C≥0 ja 0≤β <1. Huomaa, ett¨a yl¨araja ei riipu indekseist¨ai jaj, mik¨a on oleellista seuraavassa luvussa. Tulosta kutsutaan tasaiseksi ergodisuudeksi ja se todistetaan Lauseessa 2.2. Tarvitaan kuitenkin useita lemmoja, jotta luvun

p^(k)_i,j −π_j

yl¨araja voidaan kirjoittaa haluttuun muotoon. Lemma 2.2 todistuksineen on l¨ahteest¨a [3]. My¨os joissain luvun loppuosan tuloksissa on ep¨asuorasti hy¨odynnetty l¨ahdett¨a [3]

Lemma 2.2. OlkoonP = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi. T¨all¨oin kaikilla x∈Rⁿ

maxi [P x]_i−min

i [P x]_i≤

1−2 min

i,j pi,j max

i xi−min

i xi

.

Todistus. Olkoon x ∈ Rⁿ ja j0 ∈ {1,2, . . . , n} siten, ett¨a xj0 = minjxj. T¨all¨oin kaikilla i = 1,2, . . . , n

[P x]_i= Xn j=1

pi,jxj =pi,j0xj0+X

j6=j0

pi,jxj≤pi,j0xj0+ max

j xj

X

j6=j0

pi,j

=pi,j0min

j xj+ max

j xj(1−pi,j0) = max

j xj−pi,j0

maxj xj−min

j xj

≤max

j xj−min

i,j pi,j

maxj xj−min

j xj

.

Erityisesti

maxi [P x]_i≤max

j xj−min

i,j pi,j

maxj xj−min

j xj

. (4)

Vastaavasti arvioimalla n¨ahd¨a¨an, ett¨a kaikillai= 1,2, . . . , n mini [P x]_i≥min

j xj+ min

i,j pi,j

maxj xj−min

j xj

. (5)

V¨aite n¨ahd¨a¨an todeksi yhdist¨am¨all¨a arviot (4) ja (5):

maxi [P x]_i−min

i [P x]_i≤

maxj xj−min

i,j pi,j

maxj xj−min

j xj

−

minj x_j+ min

i,j p_i,j

maxj x_j−min

j x_j

=

maxj x_j−min

j x_j

−2 min

i,j

maxj x_j−min

j x_j

=

1−2 min

i,j p_i,j max

j x_j−min

j x_j

.

Seuraus 2.1. OlkoonP = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi. T¨all¨oin kaikilla x∈Rⁿ ja k∈N

maxi

P^kx

i−min

i

P^kx

i ≤

1−2 min

i,j p_i,j k

maxi x_i−min

i x_i .

Todistus. Lemman 2.2 nojalla v¨aite p¨atee, kunk= 1. Oletetaan induktio-oletuksena, ett¨a maxi

P^kx

i−min

i

P^kx

i≤

1−2 min

i,j pi,j

k

maxi xi−min

i xi

jollakink∈N. Lemman 2.2 ja induktio-oletuksen nojalla saadaan, ett¨a maxi

P^k+1x

i−min

i

P^k+1x

i= max

i

P(P^kx)

i−min

i

P(P^kx)

i

≤

1−2 min

i,j pi,j max

i

P^kx

i−min

i

P^kx

i

≤

1−2 min

i,j p_i,j 1−2 min

i,j p_i,j k

maxi x_i−min

i x_i

≤

1−2 min

i,j pi,j

k+1

maxi xi−min

i xi

.

Lemma 2.3. Olkoon P = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi siten, ett¨a P^m > 0 jollakinm∈N. Merkit¨a¨an

α= 1−2 min

i,j p^(m)_i,j . T¨all¨oin

(i) α∈[0,1[ja

(ii) on olemassa luvut C≥0 ja0≤β <1 siten, ett¨a α⌊m^k⌋ ≤Cβ^k kaikillak∈N.

Todistus. KoskaP^m>0, niin selv¨asti α <1. V¨aiteα≥0 seuraa osoittamalla, ett¨a mini,j p^(m)_i,j ≤1

2.

Tehd¨a¨an antiteesi: mini,jp^(m)_i,j > ¹₂. Olkooti0, j0∈ {1,2, . . . , n} siten, ett¨a p^(m)_i0,j0 = min

i,j p^(m)_i,j . T¨all¨oin

1 = Xn k=1

p^(m)_i

0,k≥min

k p^(m)_i

0,k+ max

k p^(m)_i

0,k≥2 min

k p^(m)_i

0,k≥2 min

i,j p^(m)_i,j >1, mik¨a on ristiriita. Siisp¨aα∈[0,1[.

Kaikillak∈N

k= k

m

m+

k− k

m

m

| {z }

≤m−1

≤ k

m

m+ (m−1),

joten

k m ≤

k m

+m−1 m kaikillak∈N. Edelleen, koskaα∈[0,1[, niin kaikilla k∈N

α^m1k

=α^mk ≥α⌊m^k⌋^+mm⁻¹ =α⌊m^k⌋α^mm−1, mist¨a

α⌊m^k⌋ ≤ 1 α^mm−1

α^m1k

kaikillak∈N. Voidaan siis valitaC= ¹

α^mm−1 jaβ=α^m1.

Lemma 2.4. Olkoon P = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi siten, ett¨a P^m > 0 jollakinm∈N. T¨all¨oin on olemassa luvutC≥0 ja0≤β <1siten, ett¨a

maxi p^(k)_i,j −min

i p^(k)_i,j ≤Cβ^k kaikillaj= 1,2, . . . , n ja kaikillak∈N.

Todistus. Merkit¨a¨an

α= 1−2 min

i,j p^(m)_i,j .

Lemman 2.3 nojalla on olemassa luvutC≥0 ja 0≤β <1 siten, ett¨a α⌊^mk⌋ ≤Cβ^k

kaikillak∈N. Kiinnitet¨a¨anj∈ {1,2, . . . , n}jak∈N. Koska kaikillai= 1,2, . . . , n P^kej

i= Xn l=1

p^(k)_i,lej,l=p^(k)_i,j, niin

minp^(k)= min P^ke

ja maxp^(k)= max P^ke

.

Siisp¨a Lausetta A.3 k¨aytt¨am¨all¨a saadaan, ett¨a maxi p^(k)_i,j −min

i p^(k)_i,j = max

i

P^kej

i−min

i

P^kej

i

= max

i

h

P⌊m^k⌋^m+(k−⌊m^k⌋^m)ej

i

i−min

i

h

P⌊m^k⌋^m+(k−⌊m^k⌋^m)ej

i

i

= max

i

h

P⌊m^k⌋^mP^k−⌊m^k⌋^me_ji

i−min

i

h

P⌊m^k⌋^mP^k−⌊m^k⌋^me_ji

i

= max

i

h(P^m)⌊^mk⌋

P^k−⌊^mk⌋^mej

i

i−min

i

h(P^m)⌊^mk⌋

P^k−⌊^mk⌋^mej

i

i

≤

1−2 min

i,j p^(m)_i,j ⌊m^k⌋

maxi

hP^k−⌊^mk⌋^me_ji

i−min

i

hP^k−⌊^mk⌋^me_ji

i

=

1−2 min

i,j p^(m)_i,j

⌊m^k⌋

maxi p(^k−⌊m^k⌋^m)

i,j −min

i p(^k−⌊m^k⌋^m)

i,j

| {z }

≤1

≤

1−2 min

i,j p^(m)_i,j ⌊m^k⌋

=α⌊m^k⌋

≤Cβ^k.

Lause 2.2. OlkoonP = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi siten, ett¨aP^m>0jolla- kinm∈N, ja olkoon π∈Rⁿ matriisin P invariantti jakauma. T¨all¨oin on olemassa luvutC≥0 ja 0≤β <1 siten, ett¨a

p^(k)_i,j −π_j ≤Cβ^k kaikillai, j= 1,2, . . . , n jak∈N.

Todistus. Koskaπon siirtym¨atodenn¨ak¨oisyysmatriisinP invariantti jakauma, niin π=πP.

T¨ast¨a seuraa induktiolla, ett¨a

π=πP^k

kaikillak∈N. N¨ain ollen kaikillaj= 1,2, . . . , njak∈Np¨atee, ett¨a π_j=

πP^k

j= Xn i=1

π_ip^(k)_i,j ≤max

i p^(k)_i,j Xn i=1

π_i= max

i p^(k)_i,j ja

πj= πP^k

j = Xn i=1

πip^(k)_i,j ≥min

i p^(k)_i,j Xn

i=1

πi= min

i p^(k)_i,j. Lemman 2.4 nojalla on olemassa luvutC≥0 ja 0≤β <1 siten, ett¨a

maxi p^(k)_i,j −min

i p^(k)_i,j ≤Cβ^k

kaikillaj = 1,2, . . . , njak∈N. Olkooti, j= 1,2, . . . , njak∈Nmit¨a tahansa. Koska mini p^(k)_i,j ≤πj≤max

i p^(k)_i,j ≤min

i p^(k)_i,j +Cβ^k ja

mini p^(k)_i,j ≤p^(k)_i,j ≤max

i p^(k)_i,j ≤min

i p^(k)_i,j +Cβ^k, niinπj, p^(k)_i,j ∈h

minip^(k)_i,j,minip^(k)_i,j +Cβ^ki . Siisp¨a

p^(k)_i,j −π_j

≤Cβ^k.

3 Markovin ketju Monte Carlo -simulointi

Olkoon π ∈ Rⁿ jakauma joukolla S = {s1, s2, . . . , sn}, f : S → R funktio ja X : Ω → S satunnaismuuttuja, joka noudattaa jakaumaaπ. Halutaan selvitt¨a¨a odotusarvo

E_πf :=E_πf(X) = Xn i=1

f(si)πi, miss¨af(X) on kuvaustenf :S→RjaX: Ω→S yhdistetty kuvaus

f(X) : Ω→R, f(X)(ω) =f(X(ω)).

Jos tieto jakaumasta π on puutteellista tain on hyvin suuri, niin odotusarvoa ei voi selvitt¨a¨a suoraan laskemalla. T¨all¨oin on kuitenkin usein mahdollista konstruoida Markovin ketju (X_k)^∞_k=0, jonka siirtym¨atodenn¨ak¨oisyysmatriisinP invariantti jakauma onπ. JosP^m>0 jollakinm∈N, voi odotusarvoaE_πf approksimoida satunnaisluvulla

1 k

Xk i=1

f(Xi),

kunk∈Non riitt¨av¨an suuri. T¨at¨a kutsutaan Markovin ketju Monte Carlo -simuloinniksi ja sen k¨aytt¨o perustellaan Lauseessa 3.1.

Otetaan k¨aytt¨o¨on seuraavat merkinn¨at: Olkoon (X_k)^∞_k=0Markovin ketju ¨a¨arellisell¨a tila-avaruu- dellaS ={s1, s2, . . . , s_n} ja olkoon ketjun taustalla oleva todenn¨ak¨oisyysavaruus (Ω,F,P). Jos i∈ {1,2, . . . , n}siten, ett¨aP(X0=s_i)>0 jaA∈ F, merkit¨a¨an

P_i(A) =P(A|X0=s_i). Lis¨aksi, josg: Ω→Ron funktio, merkit¨a¨an

E_ig=E[g|X0=si].

Lemma 3.1. Olkoon(Xk)^∞_k=0 Markovin ketju tila-avaruudellaS={s1, s2, . . . , sn} jaf :S→R funktio. Oletetaan, ett¨a ketjun siirtym¨atodenn¨ak¨oisyysmatriisilleP = [pi,j]i,j=1,2,...,n p¨ateeP^m>

0jollakinm∈Nja ett¨aπ∈Rⁿon matriisinP invariantti jakauma. T¨all¨oin, josP(X0=si)>0, niin

klim→∞

1 k²

Xk j=1

E_i(f(Xj)−E_πf)²= 0.

Todistus. Kaikillaj∈N E_i(f(Xj)−E_πf)²=

Xn l=1

(f(sl)−E_πf)²P_i(Xj =s_l)

≤ max

m=1,2,...,n(f(sm)−E_πf)² Xn l=1

Pi(Xj =sl) = max

m=1,2,...,n(f(sm)−E_πf)²,

joten

0≤ 1 k²

Xk j=1

E_i(f(Xj)−E_πf)²≤ 1 k²

Xk j=1

m=1,2,...,nmax (f(sm)−E_πf)²

= 1

k²k· max

m=1,2,...,n(f(sm)−E_πf)²= 1

k· max

m=1,2,...,n(f(sm)−E_πf)²→0, kunk→ ∞.

Lemma 3.2. Olkoon(Xk)^∞_k=0 Markovin ketju tila-avaruudellaS={s1, s2, . . . , s_n} jaf :S→R funktio. Oletetaan, ett¨a ketjun siirtym¨atodenn¨ak¨oisyysmatriisilleP = [pi,j]i,j=1,2,...,n p¨ateeP^m>

0jollakinm∈Nja ett¨aπ∈Rⁿon matriisinP invariantti jakauma. T¨all¨oin, josP(X0=si)>0, niin

klim→∞

2 k²

Xk j=1

j−1

X

l=1

E_i(f(Xj)−E_πf) (f(Xl)−E_πf) = 0.

Todistus. Merkit¨a¨an

f¯=f−E_πf, jolloin v¨aitteen¨a on

klim→∞

2 k²

Xk j=1

j−1

X

l=1

E_if¯(Xj) ¯f(Xl) = 0.

Huomataan, ett¨a kaikillal∈Njai= 1,2, . . . , n Xn

v=1

Xn u=1

f¯(sv) ¯f(su)πvp^(l)_i,u= Xn v=1

f¯(sv)πv

Xn u=1

f¯(su)p^(l)_i,u

= Xn v=1

(f(sv)−E_πf)πv

Xn u=1

f(s¯ u)p^(l)_i,u

= Xn v=1

f(sv)πv−E_πf Xn v=1

πv

! _n X

u=1

f¯(su)p^(l)_i,u

= (E_πf−E_πf) Xn u=1

f¯(su)p^(l)_i,u

= 0.

Olkooni∈ {1,2, . . . , n} mik¨a tahansa siten, ett¨aP(X0=si)>0. Olkoot edelleenj, l ∈Nmit¨a tahansa siten, ett¨al < j. Lemman A.1 nojalla

P(Xj =s_v, X_l=s_u|X₀=s_i) =P(Xj=s_v|X_l=s_u, X₀=s_i)P(Xl=s_u|X₀=s_i), kunP(Xl=s_u, X0=s_i)>0. Lauseen A.2 nojalla puolestaan

P(Xj =s_v|X_l=s_u, X0=s_i) =P(Xj=s_v|X_l=s_u),

kun P(Xl=su, X0=si) > 0. Kun viel¨a huomataan, ett¨a ehdosta P(Xl=su|X0=si) > 0 seuraa, ett¨aP(Xl=su, X0=si) =P(Xl=su|X0=si)P(X0=si)>0, saadaan, ett¨a

E_i f¯(Xj) ¯f(Xl)

= Xn v=1

Xn u=1

f¯(sv) ¯f(su)P_i(Xj =s_v, X_l=s_u)

= Xn v=1

Xn u=1

f¯(sv) ¯f(su)P(Xj=sv, Xl=su|X0=si)

= Xn v=1

X

u:P(Xl=su|X0=si)>0

f¯(sv) ¯f(su)P(Xj=sv, Xl=su|X0=si)

= Xn v=1

X

u:P(X_l=su|X0=si)>0

f¯(sv) ¯f(su)P(Xj=sv|Xl=su, X0=si)P(Xl=su|X0=si)

= Xn v=1

X

u:P(Xl=su|X0=si)>0

f¯(sv) ¯f(su)P(Xj=s_v|X_l=s_u)P(Xl=s_u|X0=s_i)

(∗)

= Xn v=1

X

u:P(Xl=su|X0=si)>0

f¯(sv) ¯f(su)p^(j−l)_u,v P(Xl=su|X0=si)

= Xn v=1

Xn u=1

f¯(sv) ¯f(su)p^(j_u,v^−l)P(Xl=su|X0=si)

(∗∗)

= Xn v=1

Xn u=1

f¯(sv) ¯f(su)p^(j−l)_u,v p^(l)_i,u

= Xn v=1

Xn u=1

f¯(sv) ¯f(su)p^(j_u,v^−l)p^(l)_i,u− Xn v=1

Xn u=1

f¯(sv) ¯f(su)πvp^(l)_i,u

| {z }

=0

= Xn v=1

Xn u=1

f¯(sv) ¯f(su)

p^(j_u,v^−l)−πv

p^(l)_i,u. (6)

Kohdissa (∗) ja (∗∗) k¨aytettiin Lausetta A.1. Huomaa kohdassa (∗), ett¨a P(Xl=su)≥P(Xl=su, X0=si)>0,

joten Lauseen A.1 k¨aytt¨o on mahdollista. Lauseen 2.2 nojalla on olemassa luvut C ≥ 0 ja 0≤β <1 siten, ett¨a

p^(k)_i,j −πj

≤Cβ^k

kaikillai, j= 1,2, . . . , njak∈N, joten yht¨al¨ost¨a (6) seuraa, ett¨a E_if¯(Xj) ¯f(Xl)

≤ Xn v=1

Xn u=1

f¯(sv)

f¯(su)

p^(j−l)_u,v −πv

p^(l)_i,u

≤ Xn v=1

f¯(sv)

! _n X

u=1

f¯(su)

! C

| {z }

=:M

β^j−l

=M β^j−l.

N¨ain ollen

−2 k²

Xk j=1

j−1

X

l=1

M β^j−l≤ 2 k²

Xk j=1

j−1

X

l=1

E_i f¯(Xj) ¯f(Xl)

≤ 2 k²

Xk j=1

j−1

X

l=1

M β^j−l,

joten riitt¨a¨a osoittaa, ett¨a

k→∞lim 2 k²

Xk j=1

j−1

X

l=1

M β^j−l= 0.

Koska 0≤β <1, niin

X∞ l=1

β^l<∞. Kaikillak∈N

0≤ 2 k²

Xk j=1

j−1

X

l=1

M β^j−l= 2M k²

Xk j=1

j−1

X

l=1

β^l

= 2M k²

k−1

X

l=1

(k−l)β^l≤ 2M k²

k−1

X

l=1

kβ^l≤ 2M k

X∞ l=1

β^l→0, kunk→ ∞.

Seuraava lause kertoo, ett¨a Markovin ketju Monte Carlo -simulointi toimii. Lauseen muotoiluun on otettu mallia l¨ahteest¨a [1], mutta todistus ei seuraa lainkaan l¨ahteen todistusta. Itse asiassa l¨ahteess¨a [1] todistetaan vahvempi tulos: Lauseen 3.1 tilanteessa

P_i



lim

k→∞

1 k

Xk j=1

f(Xj) =E_πf



= 1.

Lause 3.1. Olkoon (Xk)^∞_k=0 Markovin ketju tila-avaruudella S ={s1, s2, . . . , sn} ja olkoon f : S → R funktio. Jos ketjun siirtym¨atodenn¨ak¨oisyysmatriisille P = [pi,j]i,j=1,2,...,n p¨atee, ett¨a P^m > 0 jollakin m ∈ N, niin kaikilla ε > 0 ja kaikilla i = 1,2, . . . , n, joille P(X0=si) > 0, p¨atee, ett¨a

klim→∞

P_i



 1 k

Xk j=1

f(Xj)−E_πf

> ε



= 0, miss¨aπon matriisinP invariantti jakauma.

Todistus. Olkoonε >0 mik¨a tahansa. Merkit¨a¨an ¯f =f−E_πf ja huomataan, ett¨a kaikillak∈N

1 k

Xk j=1

f(Xj)−E_πf

2

=



1 k

Xk j=1

(f(Xj)−E_πf)





2

= 1 k²



 Xk j=1

f¯(Xj)





2

= 1 k²

Xk j=1

f(X¯ j) Xk

l=1

f¯(Xl) = 1 k²

Xk j=1

Xk l=1

f¯(Xj) ¯f(Xl)

= 1 k²

Xk j=1





j−1

X

l=1

f¯(Xj) ¯f(Xl) + ¯f(Xj)²+ Xk l=j+1

f¯(Xj) ¯f(Xl)





= 1 k²

Xk j=1

f(X¯ j)²+ 1 k²

Xk j=1

j−1

X

l=1

f¯(Xj) ¯f(Xl) + 1 k²

Xk j=1

Xk l=j+1

f¯(Xj) ¯f(Xl)

= 1 k²

Xk j=1

f(X¯ j)²+ 2 k²

Xk j=1

j−1

X

l=1

f¯(Xj) ¯f(Xl).

N¨ain ollen lemmojen 3.1 ja 3.2 ja Markovin ep¨ayht¨al¨on¹nojalla

P_i



 1 k

Xk j=1

f(Xj)−E_πf

> ε



=P_i



 1 k

Xk j=1

f(Xj)−E_πf

2

> ε²





≤ E_i

¹k

Pk

j=1f(Xj)−E_πf

2

ε²

= E_i

1 k²

Pk

j=1f¯(Xj)²+_k²2

Pk j=1

Pj−1

l=1f¯(Xj) ¯f(Xl) ε²

= 1

k²ε² Xk j=1

E_if¯(Xj)²+ 2 k²ε²

Xk j=1

j−1

X

l=1

E_i f¯(Xj) ¯f(Xl)

→0, kunk→ ∞.

Jotta Lause 3.1 olisi hy¨odyllinen, t¨aytyy annetulle jakaumalle π ∈ Rⁿ osata konstruoida siir- tym¨atodenn¨ak¨oisyysmatriisiP = [pi,j]i,j=1,2,...,n, jolle p¨atee, ett¨a

(i) πP =πja

(ii) P^m>0 jollakinm∈N.

1Markovin ep¨ayht¨al¨o: JosX on ei-negatiivinen satunnaismuuttuja jaλ >0, niinP(X≥λ)≤ ^E(_λ^X).

Ehto (i) saadaan voimaan, kun vaaditaan, ett¨a matriisiP on k¨a¨antyv¨a jakaumanπsuhteen.

M¨a¨aritelm¨a 3.1. Siirtym¨atodenn¨ak¨oisyysmatriisi P = [pi,j]i,j=1,2,...,n on k¨a¨antyv¨a jakauman π∈Rⁿ suhteen, jos

πipi,j=πjpj,i kaikillai, j= 1,2, . . . , n. (7) Markovin ketju(Xk)^∞_k=0on k¨a¨antyv¨a jakaumanπsuhteen, jos sen siirtym¨atodenn¨ak¨oisyysmatriisi on k¨a¨antyv¨a jakaumanπ suhteen.

Lause 3.2. OlkoonP = [pi,j]i,j=1,2,...,n siirtym¨atodenn¨ak¨oisyysmatriisi, joka on k¨a¨antyv¨a jakau- man π∈Rⁿ suhteen. T¨all¨oin πon matriisinP invariantti jakauma.

Todistus. Kaikillaj= 1,2, . . . , n [πP]j=

Xn i=1

π_ip_i,j= Xn i=1

π_jp_j,i=π_j Xn i=1

p_j,i=π_j, jotenπP =π.

Yht¨al¨o (7) ei kiinnit¨a matriisin P alkioita, vaan ne t¨aytyy m¨a¨ar¨at¨a muilla keinoilla. Ajatel- laan Markovin ketjun siirtym¨a tilasta toiseen kaksivaiheisena tapahtumana: Jos ollaan tilassa si, ehdotetaan uutta tilaa sj 6= si todenn¨ak¨oisyydell¨a gi,j. Ehdotettu tila sj hyv¨aksyt¨a¨an to- denn¨ak¨oisyydell¨aai,j. Jos uuden tilan ehdottaminen ja hyv¨aksyminen ovat toisistaan riippumat- tomia, niin todenn¨ak¨oisyys siirty¨a tilastasi tilaansj on

p_i,j=a_i,jg_i,j. Todenn¨ak¨oisyys pysy¨a tilassas_i on

1−X

j6=i

p_i,j= 1−X

j6=i

a_i,jg_i,j.

Oletetaan, ett¨a ehdokastilojen jakaumat g_i = (gi,1, g_i,2, . . . , g_i,n) ∈ Rⁿ, i = 1,2, . . . , n, on jo valittu siten, ett¨ag_i>0 kaikillai= 1,2, . . . , n. Teht¨av¨aksi j¨a¨a valita tilojen hyv¨aksymistodenn¨a- k¨oisyydeta_i,j,i, j= 1,2, . . . , n, niin, ett¨a k¨a¨antyvyysehto (7) toteutuu. Jakaumastaπoletetaan, ett¨aπ >0.

M¨a¨aritelm¨a 3.2. Valitsemalla

a_i,j=a^MH_i,j = min

1,πjgj,i

π_ig_i,j

kaikillai, j= 1,2, . . . , n, joillei6=j, saadaan Metropolis–Hastings -algoritmi, jonka siirtym¨ato- denn¨ak¨oisyysmatriisi onP_MH=

p^MH_i,j

i,j=1,2,...,n, miss¨a p^MH_i,j =a^MH_i,j gi,j, kun i6=j, ja

p^MH_i,i = 1−X

j6=i

p^MH_i,j .