Fast simulation for slow paths in Markov models

D.P. Reijsbergen, Pieter-Tjerk de Boer, Willem R.W. Scheinhardt, Boudewijn R.H.M. Haverkort

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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 languageEnglish
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
Externally publishedYes
Event9th International Workshop on Rare Event Simulation 2012 - Trondheim, Norway
Duration: 25 Jun 201227 Jun 2012
Conference number: 9


Conference9th International Workshop on Rare Event Simulation 2012
Abbreviated titleRESIM 2012


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


Dive into the research topics of 'Fast simulation for slow paths in Markov models'. Together they form a unique fingerprint.

Cite this