Markovin ketju Monte Carlo -simulointi ja Peskunin järjestys
Tekijät
Päivämäärä
2019Tekijänoikeudet
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
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.
...
Asiasanat
Metadata
Näytä kaikki kuvailutiedotKokoelmat
- Pro gradu -tutkielmat [28130]
Samankaltainen aineisto
Näytetään aineistoja, joilla on samankaltainen nimeke tai asiasanat.
-
Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance
Franks, Jordan; Vihola, Matti (Elsevier, 2020)We establish an ordering criterion for the asymptotic variances of two consistent Markov chain Monte Carlo (MCMC) estimators: an importance sampling (IS) estimator, based on an approximate reversible chain and subsequent ... -
Unbiased Inference for Discretely Observed Hidden Markov Model Diffusions
Chada, Neil K.; Franks, Jordan; Jasra, Ajay; Law, Kody J.; Vihola, Matti (Society for Industrial & Applied Mathematics (SIAM), 2021)We develop a Bayesian inference method for diffusions observed discretely and with noise, which is free of discretization bias. Unlike existing unbiased inference methods, our method does not rely on exact simulation ... -
On the convergence of unconstrained adaptive Markov chain Monte Carlo algorithms
Vihola, Matti (University of Jyväskylä, 2010) -
Coupled conditional backward sampling particle filter
Lee, Anthony; Singh, Sumeetpal S.; Vihola, Matti (Institute of Mathematical Statistics, 2020)The conditional particle filter (CPF) is a promising algorithm for general hidden Markov model smoothing. Empirical evidence suggests that the variant of CPF with backward sampling (CBPF) performs well even with long time ... -
Bayesian semiparametric long memory models for discretized event data
Chakraborty, Antik; Ovaskainen, Otso; Dunson, David B. (Institute of Mathematical Statistics, 2022)We introduce a new class of semiparametric latent variable models for long memory discretized event data. The proposed methodology is motivated by a study of bird vocalizations in the Amazon rain forest; the timings of ...
Ellei toisin mainittu, julkisesti saatavilla olevia JYX-metatietoja (poislukien tiivistelmät) saa vapaasti uudelleenkäyttää CC0-lisenssillä.