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

4 Citations (Scopus)
38 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

Keywords

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

Fingerprint Dive into the research topics of 'Path-ZVA: General, Efficient, and Automated Importance Sampling for Highly Reliable Markovian Systems'. Together they form a unique fingerprint.

Cite this