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: Other contributionOther research output

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 languageEnglish
PublisherNTNU University Press
Number of pages3
Place of PublicationTrondheim, Norway
ISBN (Print)not assigned
Publication statusPublished - Jun 2012
Externally publishedYes

Fingerprint

Change of Measure
Markov Model
Markov chain
Path
Sojourn Time
Rare Events
Importance Sampling
Model Checking
Stochastic Model
Simulation
Numerical Examples
Estimate
Context

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, Jun). Fast simulation for slow paths in Markov models. 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. 2012. Trondheim, Norway : NTNU University Press. 3 p.
@misc{49b5ff6e00724d31bcadd89c338b48f8,
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 = "English",
isbn = "not assigned",
publisher = "NTNU University Press",
type = "Other",

}

Reijsbergen, DP, de Boer, P-T, Scheinhardt, WRW & Haverkort, BRHM 2012, Fast simulation for slow paths in Markov models. NTNU University Press, Trondheim, Norway.

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

3 p. Trondheim, Norway : NTNU University Press. 2012, .

Research output: Other contributionOther research output

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

SN - not assigned

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. 2012. 3 p.