Fast simulation for slow paths in Markov models

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

20 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

Publication series

Name
PublisherNTNU University Press

Keywords

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

Cite this

Reijsbergen, D. P., de Boer, P-T., Scheinhardt, W. R. W., & Haverkort, B. R. H. M. (2012). Fast simulation for slow paths in Markov models. In Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012 (pp. 36-38). Trondheim, Norway: NTNU University Press.
Reijsbergen, D.P. ; de Boer, Pieter-Tjerk ; Scheinhardt, Willem R.W. ; Haverkort, Boudewijn R.H.M. / Fast simulation for slow paths in Markov models. Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012. Trondheim, Norway : NTNU University Press, 2012. pp. 36-38
@inproceedings{dbab396abe364f5393ae0d06405be581,
title = "Fast simulation for slow paths in Markov models",
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.",
keywords = "METIS-287910, IR-80763, Large times, EWI-22016, Rewards, Importance sampling, Rare event simulation",
author = "D.P. Reijsbergen and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.} and Haverkort, {Boudewijn R.H.M.}",
year = "2012",
month = "6",
language = "Undefined",
isbn = "not assigned",
publisher = "NTNU University Press",
pages = "36--38",
booktitle = "Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012",

}

Reijsbergen, DP, de Boer, P-T, Scheinhardt, WRW & Haverkort, BRHM 2012, Fast simulation for slow paths in Markov models. in Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012. NTNU University Press, Trondheim, Norway, pp. 36-38.

Fast simulation for slow paths in Markov models. / Reijsbergen, D.P.; de Boer, Pieter-Tjerk; Scheinhardt, Willem R.W.; Haverkort, Boudewijn R.H.M.

Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012. Trondheim, Norway : NTNU University Press, 2012. p. 36-38.

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

TY - GEN

T1 - Fast simulation for slow paths in Markov models

AU - Reijsbergen, D.P.

AU - de Boer, Pieter-Tjerk

AU - Scheinhardt, Willem R.W.

AU - Haverkort, Boudewijn R.H.M.

PY - 2012/6

Y1 - 2012/6

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

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

KW - METIS-287910

KW - IR-80763

KW - Large times

KW - EWI-22016

KW - Rewards

KW - Importance sampling

KW - Rare event simulation

M3 - Conference contribution

SN - not assigned

SP - 36

EP - 38

BT - Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012

PB - NTNU University Press

CY - Trondheim, Norway

ER -

Reijsbergen DP, de Boer P-T, Scheinhardt WRW, Haverkort BRHM. Fast simulation for slow paths in Markov models. In Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012. Trondheim, Norway: NTNU University Press. 2012. p. 36-38