Fast simulation for slow paths in Markov models

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

48 Downloads (Pure)


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
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

PublisherNTNU University Press


Workshop9th International Workshop on Rare Event Simulation, RESIM 2012
Abbreviated titleRESIM


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

Cite this