Fast simulation for slow paths in Markov models

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

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 proceeding › Conference contribution › Scientific › peer-review

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 language	English
Title of host publication	Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012
Place of Publication	Trondheim, Norway
Publisher	NTNU University Press
Number of pages	3
ISBN (Print)	not assigned
Publication status	Published - Jun 2012
Externally published	Yes
Event	9th International Workshop on Rare Event Simulation 2012 - Trondheim, Norway Duration: 25 Jun 2012 → 27 Jun 2012 Conference number: 9

Conference

Conference	9th International Workshop on Rare Event Simulation 2012
Abbreviated title	RESIM 2012
Country/Territory	Norway
City	Trondheim
Period	25/06/12 → 27/06/12

Keywords

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

Cite this

@inproceedings{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 = jun,

language = "English",

isbn = "not assigned",

booktitle = "Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012",

publisher = "NTNU University Press",

note = "9th International Workshop on Rare Event Simulation 2012, RESIM 2012 ; Conference date: 25-06-2012 Through 27-06-2012",

}

Fast simulation for slow paths in Markov models. / Reijsbergen, D.P.; de Boer, Pieter-Tjerk; Scheinhardt, Willem R.W. et al.
Proceedings of the Ninth International Workshop on Rare Event Simulation, RESIM 2012. Trondheim, Norway: NTNU University Press, 2012.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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.

N1 - Conference code: 9

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

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

PB - NTNU University Press

CY - Trondheim, Norway

T2 - 9th International Workshop on Rare Event Simulation 2012

Y2 - 25 June 2012 through 27 June 2012

ER -

Fast simulation for slow paths in Markov models

Abstract

Conference

Keywords

Fingerprint

Cite this