University of Jyväskylä | JYX Digital Repository

  • English  | Give feedback |
    • suomi
    • English
 
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
View Item 
  • JYX
  • Opinnäytteet
  • Pro gradu -tutkielmat
  • View Item
JYX > Opinnäytteet > Pro gradu -tutkielmat > View Item

Markovin ketju Monte Carlo -simulointi ja Peskunin järjestys

Thumbnail
View/Open
426.5Kb

Downloads:  
Show download detailsHide download details  
Authors
Parkkinen, Santeri
Date
2019
Discipline
MatematiikkaMathematics
Copyright
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

 
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. ...
Keywords
Markovin ketju Monte Carlo -simulointi siirtymätodennäköisyysmatriisi asymptoottinen varianssi Peskunin järjestys Metropolis–Hastings algoritmi Barkerin algoritmi Markovin ketjut Monte Carlo -menetelmät
URI

http://urn.fi/URN:NBN:fi:jyu-201906042916

Metadata
Show full item record
Collections
  • Pro gradu -tutkielmat [23424]

Related items

Showing items with similar title or keywords.

  • 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 ...
  • Conditional particle filters with diffuse initial distributions 

    Karppinen, Santeri; Vihola, Matti (Springer, 2021)
    Conditional particle filters (CPFs) are powerful smoothing algorithms for general nonlinear/non-Gaussian hidden Markov models. However, CPFs can be inefficient or difficult to apply with diffuse initial distributions, which ...
  • Importance sampling type estimators based on approximate marginal Markov chain Monte Carlo 

    Vihola, Matti; Helske, Jouni; Franks, Jordan (Wiley-Blackwell, 2020)
    We consider importance sampling (IS) type weighted estimators based on Markov chain Monte Carlo (MCMC) targeting an approximate marginal of the target distribution. In the context of Bayesian latent variable models, the ...
  • 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 ...
  • Browse materials
  • Browse materials
  • Articles
  • Conferences and seminars
  • Electronic books
  • Historical maps
  • Journals
  • Tunes and musical notes
  • Photographs
  • Presentations and posters
  • Publication series
  • Research reports
  • Research data
  • Study materials
  • Theses

Browse

All of JYXCollection listBy Issue DateAuthorsSubjectsPublished inDepartmentDiscipline

My Account

Login

Statistics

View Usage Statistics
  • How to publish in JYX?
  • Self-archiving
  • Publish Your Thesis Online
  • Publishing Your Dissertation
  • Publication services

Open Science at the JYU
 
Data Protection Description

Accessibility Statement

Unless otherwise specified, publicly available JYX metadata (excluding abstracts) may be freely reused under the CC0 waiver.
Open Science Centre