{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:40:58Z","timestamp":1792798858585,"version":"4.5.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T00:00:00Z","timestamp":1531440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SENSATION","award":["318490"],"award-info":[{"award-number":["318490"]}],"id":[{"id":"https:\/\/ror.org\/041gvrq41","id-type":"ROR","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["612.064.812"],"award-info":[{"award-number":["612.064.812"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"EU projects QUANTICOL","award":["600708"],"award-info":[{"award-number":["600708"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>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 \u201ctowards\u201d 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 \u201crare\u201d 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.<\/jats:p>","DOI":"10.1145\/3161569","type":"journal-article","created":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T12:08:17Z","timestamp":1531483697000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Path-ZVA"],"prefix":"10.1145","volume":"28","author":[{"given":"Dani\u00ebl","family":"Reijsbergen","sequence":"first","affiliation":[{"name":"University of Edinburgh, Scotland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pieter-Tjerk De","family":"Boer","sequence":"additional","affiliation":[{"name":"University of Twente, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Werner","family":"Scheinhardt","sequence":"additional","affiliation":[{"name":"University of Twente, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandeep","family":"Juneja","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2010.13"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/24.974123"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exp003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICECCS.2008.11"},{"key":"e_1_2_1_5_1","volume-title":"European Workshop on Performance Engineering. Springer, 275--290","author":"Budde C. E.","unstructured":"C. E. Budde , P. R. D\u2019Argenio , and H. Hermanns . 2015. Rare event simulation with fully automated importance splitting . In European Workshop on Performance Engineering. Springer, 275--290 . C. E. Budde, P. R. D\u2019Argenio, and H. Hermanns. 2015. Rare event simulation with fully automated importance splitting. In European Workshop on Performance Engineering. Springer, 275--290."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"M. Capi\u0144ski and P. E. Kopp. 2004. Measure Integral and Probability. Springer.  M. Capi\u0144ski and P. E. Kopp. 2004. Measure Integral and Probability. Springer.","DOI":"10.1007\/978-1-4471-0645-6"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 5th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation. 351--365","author":"Carrasco J. A.","year":"1992","unstructured":"J. A. Carrasco . 1992 . Failure distance based simulation of repairable fault-tolerant systems . In Proceedings of the 5th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation. 351--365 . J. A. Carrasco. 1992. Failure distance based simulation of repairable fault-tolerant systems. In Proceedings of the 5th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation. 351--365."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2006.874910"},{"key":"e_1_2_1_9_1","volume-title":"Renewal Theory. Methuen 8 Co","author":"Cox D. R.","unstructured":"D. R. Cox . 1962. Renewal Theory. Methuen 8 Co ., London . D. R. Cox. 1962. Renewal Theory. Methuen 8 Co., London."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 2007 Winter Simulation Conference. IEEE, 403--411","author":"de Boer P. T.","unstructured":"P. T. de Boer , P. L\u2019Ecuyer , G. Rubino , and B. Tuffin . 2007. Estimating the probability of a rare event over a finite time horizon . In Proceedings of the 2007 Winter Simulation Conference. IEEE, 403--411 . P. T. de Boer, P. L\u2019Ecuyer, G. Rubino, and B. Tuffin. 2007. Estimating the probability of a rare event over a finite time horizon. In Proceedings of the 2007 Winter Simulation Conference. IEEE, 403--411."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.237881"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203094"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-007-9051-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"S. Juneja and P. Shahabuddin. 2001. Fast simulation of Markov chains with small transition probabilities. Management Science (2001) 547--562.  S. Juneja and P. Shahabuddin. 2001. Fast simulation of Markov chains with small transition probabilities. Management Science (2001) 547--562.","DOI":"10.1287\/mnsc.47.4.547.9827"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"M. Kwiatkowska G. Norman and D. Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In Computer Aided Verification. Springer 585--591.   M. Kwiatkowska G. Norman and D. Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In Computer Aided Verification. Springer 585--591.","DOI":"10.1007\/978-3-642-22110-1_47"},{"key":"e_1_2_1_17_1","unstructured":"A. M. Law and W. D. Kelton. 1991. Simulation Modeling and Analysis. McGraw-Hill New York.   A. M. Law and W. D. Kelton. 1991. Simulation Modeling and Analysis. McGraw-Hill New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667072.1667078"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2008 Winter Simulation Conference. IEEE, 170--181","author":"L\u2019Ecuyer P.","unstructured":"P. L\u2019Ecuyer and B. Tuffin . 2008. Approximate zero-variance simulation . In Proceedings of the 2008 Winter Simulation Conference. IEEE, 170--181 . P. L\u2019Ecuyer and B. Tuffin. 2008. Approximate zero-variance simulation. In Proceedings of the 2008 Winter Simulation Conference. IEEE, 170--181."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-009-0532-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0029-5493(84)90060-8"},{"key":"e_1_2_1_22_1","volume-title":"General conditions for bounded relative error in simulations of highly reliable Markovian systems. Advances in Applied Probability","author":"Nakayama M. K.","year":"1996","unstructured":"M. K. Nakayama . 1996. General conditions for bounded relative error in simulations of highly reliable Markovian systems. Advances in Applied Probability ( 1996 ), 687--727. M. K. Nakayama. 1996. General conditions for bounded relative error in simulations of highly reliable Markovian systems. Advances in Applied Probability (1996), 687--727."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2010.39"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40196-1_31"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2010.04.176"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/320251.320260"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.40.3.333"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3161569","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3161569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:26:53Z","timestamp":1750199213000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3161569"}},"subtitle":["General, Efficient, and Automated Importance Sampling for Highly Reliable Markovian Systems"],"short-title":[],"issued":{"date-parts":[[2018,7,13]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3161569"],"URL":"https:\/\/doi.org\/10.1145\/3161569","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,13]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}