Markovin ketju Monte Carlo -simulointi ja Peskunin järjestys

Abstract

Tämän tutkielman tavoitteena on esitellä Markovin ketju Monte Carlo -simulointi äärellisessä tila-avaruudessa ja käsitellä simulointialgoritmien vertailuun liittyvää ongelmaa. Markovin ketju Monte Carlo -simuloinnissa funktion odotusarvolle lasketaan approksimaatioita simuloitua Markovin ketjua apuna käyttäen. Usein simulointi voidaan tehdä useammalla kuin yhdellä algoritmilla ja halutaan selvittää, mikä algoritmi soveltuu tehtävään parhaiten.

Kun simulaatioaskelten määrä lähestyy ääretöntä, Markovin ketju Monte Carlo -estimaatti suppenee melkein varmasti kohti odotusarvon oikeaa arvoa käytetystä simulointialgoritmista riippumatta. Käytännössä Markovin ketju Monte Carlo -simulointi tuottaa kuitenkin vain odotusarvon approksimaation, koska mikään todellinen simulointi ei voi jatkua äärettömän pitkään. Vain äärellisen monen simulaatioaskeleen käyttö aiheuttaa virheen, joka on luonteeltaan satunnainen: virhe kuuluu tietylle välille jollakin todennäköisyydellä. On luonnollista kysyä, miten approksimaation tarkkuus riippuu simulointialgoritmista. Kaikki algoritmit antavat odotusarvolle arvion halutulla tarkkuudella, jos simulointia jatketaan riittävän kauan. Jotkut algoritmit tuottavat kuitenkin tarkkoja approksimaatioita nopeammin kuin toiset, mikä on motivaatio algoritmien vertailulle. Ei kuitenkaan ole aivan selvää, miten vertailu pitäisi käytännössä tehdä. Halutun tarkkuuden saavuttamiseksi vaadittavaa aikaa on vaikea arvioida, eivätkä pelkät arviot edes ole riittävä perusta algoritmien vertailulle. Voi esimerkiksi käydä niin, että arvioitu alaraja algoritmin P vaatimalle ajalle on pienempi kuin alaraja algoritmin Q vaatimalle ajalle, mutta silti algoritmi Q pääsee haluttuun tarkkuuteen nopeammin kuin algoritmi P. Pelkät alarajat eivät siis kerro tarpeeksi vaadittavien aikojen todellisista arvoista. Arvioiden sijaan tarvitaan jokin eksakti riippuvuus simulointivirheen ja algoritmin välille.

Kriteeri, jonka suhteen algoritmien vertailu tehdään, johdetaan Markovin ketjujen keskeistä raja-arvolausetta käyttäen. Keskeinen raja-arvolause mahdollistaa simulointivirheiden todennäköisyyksien raja-arvon eksaktin laskemisen tietyssä erikoistapauksessa. Tarkastelu osoittaa, että algoritmien vertailemiseksi kannattaa tutkia niiden asymptoottisia variansseja: kahdesta algoritmista se, jonka asymptoottinen varianssi annetulle funktiolle on pienempi, soveltuu paremmin kyseisen funktion odotusarvon simulointiin. Kriteerin ongelmana on, että sen soveltaminen ei ole ihan suoraviivaista. Käytännössä algoritmeista tiedetään vain niiden siirtymätodennäköisyysmatriisit, joten algoritmien vertailemiseksi täytyy selvittää, miten asymptoottinen varianssi riippuu siirtymätodennäköisyysmatriisista. Tässä tutkielmassa tarkastelu rajataan kääntyviin Markovin ketjuihin, jolloin kyseinen riippuvuus voidaan selvittää funktionaalianalyysin tuloksia hyödyntäen. Tämän jälkeen vertailu onnistuu tietyssä erikoistapauksessa Peskunin järjestystä käyttämällä. Peskunin järjestyksen sovelluksena osoitetaan, että Metropolis–Hastings -algoritmi on parempi kuin Barkerin algoritmi.