Path-ZVA: General, Efficient, and Automated Importance Sampling for Highly Reliable Markovian Systems

D.P. Reijsbergen (Corresponding Author), Pieter-Tjerk de Boer, Willem R.W. Scheinhardt, Sandeep Juneja

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
5 Downloads (Pure)

Abstract

We introduce Path-ZVA: an efficient simulation technique for estimating the probability of reaching a rare goal state before a regeneration state in a (discrete-time) Markov chain. Standard Monte Carlo simulation techniques do not work well for rare events, so we use importance sampling; i.e., we change the probability measure governing the Markov chain such that transitions “towards” the goal state become more likely. To do this, we need an idea of distance to the goal state, so some level of knowledge of the Markov chain is required. In this article, we use graph analysis to obtain this knowledge. In particular, we focus on knowledge of the shortest paths (in terms of “rare” transitions) to the goal state. We show that only a subset of the (possibly huge) state space needs to be considered. This is effective when the high dependability of the system is primarily due to high component reliability, but less so when it is due to high redundancies. For several models, we compare our results to well-known importance sampling methods from the literature and demonstrate the large potential gains of our method.
Original languageEnglish
Article number22
Number of pages25
JournalACM transactions on modeling and computer simulation
Volume28
Issue number3
DOIs
Publication statusPublished - 1 Aug 2018

Fingerprint

Importance sampling
Importance Sampling
Markov processes
Markov chain
Path
Rare Events
Dependability
Regeneration
Sampling Methods
Shortest path
Probability Measure
Redundancy
State Space
Discrete-time
Monte Carlo Simulation
Likely
Subset
Graph in graph theory
Demonstrate
Knowledge

Keywords

  • Rare-event simulation
  • Importance sampling
  • Highly reliable systems

Cite this

@article{3f7b1a0f882b46d7bd93d3d337cab7bc,
title = "Path-ZVA: General, Efficient, and Automated Importance Sampling for Highly Reliable Markovian Systems",
abstract = "We introduce Path-ZVA: an efficient simulation technique for estimating the probability of reaching a rare goal state before a regeneration state in a (discrete-time) Markov chain. Standard Monte Carlo simulation techniques do not work well for rare events, so we use importance sampling; i.e., we change the probability measure governing the Markov chain such that transitions “towards” the goal state become more likely. To do this, we need an idea of distance to the goal state, so some level of knowledge of the Markov chain is required. In this article, we use graph analysis to obtain this knowledge. In particular, we focus on knowledge of the shortest paths (in terms of “rare” transitions) to the goal state. We show that only a subset of the (possibly huge) state space needs to be considered. This is effective when the high dependability of the system is primarily due to high component reliability, but less so when it is due to high redundancies. For several models, we compare our results to well-known importance sampling methods from the literature and demonstrate the large potential gains of our method.",
keywords = "Rare-event simulation, Importance sampling, Highly reliable systems",
author = "D.P. Reijsbergen and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.} and Sandeep Juneja",
year = "2018",
month = "8",
day = "1",
doi = "10.1145/3161569",
language = "English",
volume = "28",
journal = "ACM transactions on modeling and computer simulation",
issn = "1049-3301",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

Path-ZVA : General, Efficient, and Automated Importance Sampling for Highly Reliable Markovian Systems. / Reijsbergen, D.P. (Corresponding Author); de Boer, Pieter-Tjerk ; Scheinhardt, Willem R.W.; Juneja, Sandeep.

In: ACM transactions on modeling and computer simulation, Vol. 28, No. 3, 22, 01.08.2018.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Path-ZVA

T2 - General, Efficient, and Automated Importance Sampling for Highly Reliable Markovian Systems

AU - Reijsbergen, D.P.

AU - de Boer, Pieter-Tjerk

AU - Scheinhardt, Willem R.W.

AU - Juneja, Sandeep

PY - 2018/8/1

Y1 - 2018/8/1

N2 - We introduce Path-ZVA: an efficient simulation technique for estimating the probability of reaching a rare goal state before a regeneration state in a (discrete-time) Markov chain. Standard Monte Carlo simulation techniques do not work well for rare events, so we use importance sampling; i.e., we change the probability measure governing the Markov chain such that transitions “towards” the goal state become more likely. To do this, we need an idea of distance to the goal state, so some level of knowledge of the Markov chain is required. In this article, we use graph analysis to obtain this knowledge. In particular, we focus on knowledge of the shortest paths (in terms of “rare” transitions) to the goal state. We show that only a subset of the (possibly huge) state space needs to be considered. This is effective when the high dependability of the system is primarily due to high component reliability, but less so when it is due to high redundancies. For several models, we compare our results to well-known importance sampling methods from the literature and demonstrate the large potential gains of our method.

AB - We introduce Path-ZVA: an efficient simulation technique for estimating the probability of reaching a rare goal state before a regeneration state in a (discrete-time) Markov chain. Standard Monte Carlo simulation techniques do not work well for rare events, so we use importance sampling; i.e., we change the probability measure governing the Markov chain such that transitions “towards” the goal state become more likely. To do this, we need an idea of distance to the goal state, so some level of knowledge of the Markov chain is required. In this article, we use graph analysis to obtain this knowledge. In particular, we focus on knowledge of the shortest paths (in terms of “rare” transitions) to the goal state. We show that only a subset of the (possibly huge) state space needs to be considered. This is effective when the high dependability of the system is primarily due to high component reliability, but less so when it is due to high redundancies. For several models, we compare our results to well-known importance sampling methods from the literature and demonstrate the large potential gains of our method.

KW - Rare-event simulation

KW - Importance sampling

KW - Highly reliable systems

U2 - 10.1145/3161569

DO - 10.1145/3161569

M3 - Article

VL - 28

JO - ACM transactions on modeling and computer simulation

JF - ACM transactions on modeling and computer simulation

SN - 1049-3301

IS - 3

M1 - 22

ER -