Abstract
Original language | English |
---|---|
Article number | 22 |
Number of pages | 25 |
Journal | ACM transactions on modeling and computer simulation |
Volume | 28 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Aug 2018 |
Fingerprint
Keywords
- Rare-event simulation
- Importance sampling
- Highly reliable systems
Cite this
}
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 journal › Article › Academic › peer-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 -