Fast simulation for slow paths in Markov models

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

26 Downloads (Pure)

Abstract

Inspired by applications in the context of stochastic model checking, we are interested in using simulation for estimating the probability of reaching a specific state in a Markov chain after a large amount of time tau has passed. Since this is a rare event, we apply importance sampling. We derive approximate expressions for the sojourn times on a given path in a Markov chain conditional on the sum exceeding tau, and use those expressions to construct a change of measure. Numerical examples show that this change of measure performs very well, leading to high precision estimates in short simulation times.
Original languageUndefined
Title of host publicationProceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012
Place of PublicationTrondheim, Norway
PublisherNTNU University Press
Pages36-38
Number of pages3
ISBN (Print)not assigned
Publication statusPublished - Jun 2012
Event9th International Workshop on Rare Event Simulation, RESIM 2012 - Trondheim, Norway
Duration: 25 Jun 201227 Jun 2012
Conference number: 9

Publication series

Name
PublisherNTNU University Press

Workshop

Workshop9th International Workshop on Rare Event Simulation, RESIM 2012
Abbreviated titleRESIM
CountryNorway
CityTrondheim
Period25/06/1227/06/12

Keywords

  • METIS-287910
  • IR-80763
  • Large times
  • EWI-22016
  • Rewards
  • Importance sampling
  • Rare event simulation

Cite this