{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:18Z","timestamp":1750308738810,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2007,4]]},"abstract":"<jats:p>\n            In the context of rare-event simulation, splitting and importance sampling (IS) are the primary approaches to make important rare events happen more frequently in a simulation and yet recover an unbiased estimator of the target performance measure, with much smaller variance than a straightforward Monte Carlo (MC) estimator. Randomized quasi-Monte Carlo (RQMC) is another class of methods for reducing the noise of simulation estimators, by sampling more evenly than with standard MC. It typically works well for simulations that depend mostly on very few random numbers. In splitting and IS, on the other hand, we often simulate Markov chains whose sample paths are a function of a long sequence of independent random numbers generated during the simulation. In this article, we show that RQMC can be used jointly with splitting and\/or IS to construct better estimators than those obtained by either of these methods alone. We do that in a setting where the goal is to estimate the probability of reaching\n            <jats:italic>B<\/jats:italic>\n            before reaching (or returning to)\n            <jats:italic>A<\/jats:italic>\n            when starting\n            <jats:italic>A<\/jats:italic>\n            from a distinguished state not in\n            <jats:italic>B<\/jats:italic>\n            , where\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            are two disjoint subsets of the state space, and\n            <jats:italic>B<\/jats:italic>\n            is very rarely reached. This problem has several practical applications. The article is in fact a two-in-one: the first part provides a guided tour of splitting techniques, introducing along the way some improvements in the implementation of multilevel splitting. At the end of the article, we also give examples of situations where splitting is not effective. For these examples, we compare different ways of applying IS and combining it with RQMC.\n          <\/jats:p>","DOI":"10.1145\/1225275.1225280","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Rare events, splitting, and quasi-Monte Carlo"],"prefix":"10.1145","volume":"17","author":[{"given":"Pierre","family":"L'Ecuyer","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al, Canada"}]},{"given":"Val\u00e9rie","family":"Demers","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al, Canada"}]},{"given":"Bruno","family":"Tuffin","sequence":"additional","affiliation":[{"name":"IRISA--INRIA, Rennes, France"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.3.509"},{"key":"e_1_2_1_2_1","volume-title":"Monte Carlo and Quasi-Monte Carlo Methods","author":"Asmussen S.","year":"2000","unstructured":"Asmussen , S. 2002. Large deviations in rare events simulation: Examples, counterexamples, and alternatives . In Monte Carlo and Quasi-Monte Carlo Methods 2000 , K.-T. Fang, F. J. Hickernell, and H. Niederreiter, Eds. Springer-Verlag , Berlin, 1--9. Asmussen, S. 2002. Large deviations in rare events simulation: Examples, counterexamples, and alternatives. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K.-T. Fang, F. J. Hickernell, and H. Niederreiter, Eds. Springer-Verlag, Berlin, 1--9."},{"key":"e_1_2_1_3_1","first-page":"308","article-title":"Automatic importance estimation in forward Monte Carlo calculations","volume":"41","author":"Booth T. E.","year":"1982","unstructured":"Booth , T. E. 1982 . Automatic importance estimation in forward Monte Carlo calculations . Trans. Amer. Nuc. Soc. 41 , 308 -- 309 . Booth, T. E. 1982. Automatic importance estimation in forward Monte Carlo calculations. Trans. Amer. Nuc. Soc. 41, 308--309.","journal-title":"Trans. Amer. Nuc. Soc."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.13182\/NSE85-A18622"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.13182\/FST84-A23082"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.13182\/NSE92-A23897"},{"volume-title":"Introduction to Rare Event Simulation","author":"Bucklew J. A.","key":"e_1_2_1_7_1","unstructured":"Bucklew , J. A. 2004. Introduction to Rare Event Simulation . Springer-Verlag , New York . Bucklew, J. A. 2004. Introduction to Rare Event Simulation. Springer-Verlag, New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1515\/mcma.2002.8.4.321"},{"volume-title":"Proceedings of the 2005 Winter Simulation Conference, M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, Eds. 519--527","author":"Cancela H.","key":"e_1_2_1_9_1","unstructured":"Cancela , H. , Rubino , G. , and Tuffin , B . 2005. New measures of robustness in rare event simulation . In Proceedings of the 2005 Winter Simulation Conference, M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, Eds. 519--527 . Cancela, H., Rubino, G., and Tuffin, B. 2005. New measures of robustness in rare event simulation. In Proceedings of the 2005 Winter Simulation Conference, M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, Eds. 519--527."},{"key":"e_1_2_1_10_1","volume-title":"Tech. Rep. 5710, INRIA. Oct.","author":"C\u00e9rou F.","year":"2005","unstructured":"C\u00e9rou , F. and Guyader , A . 2005 . Adaptive multilevel splitting for rare event analysis. Tech. Rep. 5710, INRIA. Oct. C\u00e9rou, F. and Guyader, A. 2005. Adaptive multilevel splitting for rare event analysis. Tech. Rep. 5710, INRIA. Oct."},{"volume-title":"Proceedings of the 2005 Winter Simulation Conference, F. B. A. M. E. Kuhl, N. M. Steiger and J. A. Joines, Eds. 682--691","author":"C\u00e9rou F.","key":"e_1_2_1_11_1","unstructured":"C\u00e9rou , F. , LeGland , F. , Del Moral , P. , and Lezaud , P . 2005. Limit theorems for the multilevel splitting algorithm in the simulation of rare events . In Proceedings of the 2005 Winter Simulation Conference, F. B. A. M. E. Kuhl, N. M. Steiger and J. A. Joines, Eds. 682--691 . C\u00e9rou, F., LeGland, F., Del Moral, P., and Lezaud, P. 2005. Limit theorems for the multilevel splitting algorithm in the simulation of rare events. In Proceedings of the 2005 Winter Simulation Conference, F. B. A. M. E. Kuhl, N. M. Steiger and J. A. Joines, Eds. 682--691."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(94)90005-1"},{"volume-title":"Genealogical and Interacting Particle Systems with Applications. Probability and its Applications","author":"Del Moral P.","key":"e_1_2_1_13_1","unstructured":"Del Moral , P. 2004. Feynman-Kac Formulae . Genealogical and Interacting Particle Systems with Applications. Probability and its Applications . Springer , New York . Del Moral, P. 2004. Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Probability and its Applications. Springer, New York."},{"key":"e_1_2_1_14_1","unstructured":"Ermakov S. M. and Melas V. B. 1995. Design and Analysis of Simulation Experiments. Kluwer Academic Dordrecht The Netherlands.  Ermakov S. M. and Melas V. B. 1995. Design and Analysis of Simulation Experiments. Kluwer Academic Dordrecht The Netherlands."},{"volume-title":"Strategies for Quasi-Monte Carlo","author":"Fox B. L.","key":"e_1_2_1_15_1","unstructured":"Fox , B. L. 1999. Strategies for Quasi-Monte Carlo . Kluwer Academic , Boston, MA . Fox, B. L. 1999. Strategies for Quasi-Monte Carlo. Kluwer Academic, Boston, MA."},{"volume-title":"Proceedings of the 1998 Winter Simulation Conference. IEEE Press, 601--609","author":"Garvels M. J. J.","key":"e_1_2_1_17_1","unstructured":"Garvels , M. J. J. and Kroese , D. P . 1998. A comparison of RESTART implementations . In Proceedings of the 1998 Winter Simulation Conference. IEEE Press, 601--609 . Garvels, M. J. J. and Kroese, D. P. 1998. A comparison of RESTART implementations. In Proceedings of the 1998 Winter Simulation Conference. IEEE Press, 601--609."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460130408"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.736061"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.4.585"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02136829"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.11.1367"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.123381"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Hammersley J. M. and Handscomb D. C. 1964. Monte Carlo Methods. Methuen London.  Hammersley J. M. and Handscomb D. C. 1964. Monte Carlo Methods. Methuen London.","DOI":"10.1007\/978-94-009-5819-7"},{"volume-title":"The Theory of Branching Processes","author":"Harris T.","key":"e_1_2_1_25_1","unstructured":"Harris , T. 1963. The Theory of Branching Processes . Springer-Verlag , New York . Harris, T. 1963. The Theory of Branching Processes. Springer-Verlag, New York."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/203091.203094"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/175007.175008"},{"key":"e_1_2_1_28_1","volume-title":"Monte Carlo and Quasi-Monte Carlo Methods","author":"Hickernell F. J.","year":"2000","unstructured":"Hickernell , F. J. 2002. Obtaining o(n&minus;2&plus;&epsi;) convergence for lattice quadrature rules . In Monte Carlo and Quasi-Monte Carlo Methods 2000 , K.-T. Fang, F. J. Hickernell, and H. Niederreiter, Eds. Springer-Verlag , Berlin, 274--289. Hickernell, F. J. 2002. Obtaining o(n&minus;2&plus;&epsi;) convergence for lattice quadrature rules. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K.-T. Fang, F. J. Hickernell, and H. Niederreiter, Eds. Springer-Verlag, Berlin, 274--289."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.47.4.547.9827"},{"key":"e_1_2_1_30_1","first-page":"27","article-title":"Estimation of particle transmission by random sampling","volume":"12","author":"Kahn H.","year":"1951","unstructured":"Kahn , H. and Harris , T. E. 1951 . Estimation of particle transmission by random sampling . National Bureau of Standards Applied Mathematical Series 12 , 27 -- 30 . Kahn, H. and Harris, T. E. 1951. Estimation of particle transmission by random sampling. National Bureau of Standards Applied Mathematical Series 12, 27--30.","journal-title":"National Bureau of Standards Applied Mathematical Series"},{"volume-title":"Markov Chain Models---Rarity and Exponentiality","author":"Keilson J.","key":"e_1_2_1_31_1","unstructured":"Keilson , J. 1979. Markov Chain Models---Rarity and Exponentiality . Springer-Verlag , New York . Keilson, J. 1979. Markov Chain Models---Rarity and Exponentiality. Springer-Verlag, New York."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"L\u00e9cot C. and Tuffin B. 2004. Quasi-Monte Carlo methods for estimating transient measures of discrete time Markov chains. In Monte Carlo and Quasi-Monte Carlo Methods 2002 H. Niederreiter Ed. Springer-Verlag Berlin 329--343.  L\u00e9cot C. and Tuffin B. 2004. Quasi-Monte Carlo methods for estimating transient measures of discrete time Markov chains. In Monte Carlo and Quasi-Monte Carlo Methods 2002 H. Niederreiter Ed. Springer-Verlag Berlin 329--343.","DOI":"10.1007\/978-3-642-18743-8_20"},{"key":"e_1_2_1_33_1","unstructured":"L'Ecuyer P. L\u00e9cot C. and Tuffin B. 2005. A randomized quasi-Monte Carlo simulation method for Markov chains. INRIA Res. Rep. 5545 (April) Operations Research to appear.  L'Ecuyer P. L\u00e9cot C. and Tuffin B. 2005. A randomized quasi-Monte Carlo simulation method for Markov chains. INRIA Res. Rep. 5545 (April) Operations Research to appear."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"L'Ecuyer P. L\u00e9cot C. and Tuffin B. 2006. Randomized quasi-Monte Carlo simulation of Markov chains with an ordered state space. In Monte Carlo and Quasi-Monte Carlo Methods 2004 H. Niederreiter and D. Talay Eds. 331--342.  L'Ecuyer P. L\u00e9cot C. and Tuffin B. 2006. Randomized quasi-Monte Carlo simulation of Markov chains with an ordered state space. In Monte Carlo and Quasi-Monte Carlo Methods 2004 H. Niederreiter and D. Talay Eds. 331--342.","DOI":"10.1007\/3-540-31186-6_19"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.46.9.1214.12231"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"L'Ecuyer P. and Lemieux C. 2002. Recent advances in randomized quasi-Monte Carlo methods. In Modeling Uncertainty: An Examination of Stochastic Theory Methods and Applications M. Dror P. L'Ecuyer and F. Szidarovszky Eds. Kluwer Academic Boston 419--474.  L'Ecuyer P. and Lemieux C. 2002. Recent advances in randomized quasi-Monte Carlo methods. In Modeling Uncertainty: An Examination of Stochastic Theory Methods and Applications M. Dror P. L'Ecuyer and F. Szidarovszky Eds. Kluwer Academic Boston 419--474.","DOI":"10.1007\/0-306-48102-2_20"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190095.1190121"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/268437.268490"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/1428177"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.10.1426"},{"volume-title":"Proceedings of the 2nd International Workshop on Performability Modelling of Computer and Communication Systems.","author":"Nicola V. F.","key":"e_1_2_1_41_1","unstructured":"Nicola , V. F. , Shahabuddin , P. , and Heidelberger , P . 1993. Techniques for fast simulation of highly dependable systems . In Proceedings of the 2nd International Workshop on Performability Modelling of Computer and Communication Systems. Nicola, V. F., Shahabuddin, P., and Heidelberger, P. 1993. Techniques for fast simulation of highly dependable systems. In Proceedings of the 2nd International Workshop on Performability Modelling of Computer and Communication Systems."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/130653"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/272991.273010"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/945511.945518"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1515\/mcma.1998.4.2.95"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.8649"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(94)90017-5"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.40.3.333"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/224401.224460"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/318123.318239"},{"key":"e_1_2_1_51_1","unstructured":"Taylor H. M. and Karlin S. 1998. An Introduction to Stochastic Modeling third ed. Academic Press San Diego.  Taylor H. M. and Karlin S. 1998. An Introduction to Stochastic Modeling third ed. Academic Press San Diego."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032374748"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2004.25"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-405X(77)90016-2"},{"key":"e_1_2_1_55_1","article-title":"Rare event RESTART simulation of two-stage networks. Europ","author":"Vill\u00e9n-Altamirano J.","year":"2006","unstructured":"Vill\u00e9n-Altamirano , J. 2006 . Rare event RESTART simulation of two-stage networks. Europ . J. Oper. Res. to appear. Vill\u00e9n-Altamirano, J. 2006. Rare event RESTART simulation of two-stage networks. Europ. J. Oper. Res. to appear.","journal-title":"J. Oper. Res. to appear."},{"volume-title":"Proceedings of the 14th International Teletraffic Congress","author":"Vill\u00e9n-Altamirano M.","key":"e_1_2_1_56_1","unstructured":"Vill\u00e9n-Altamirano , M. , Martinez-Marr\u00f3n , A. , Gamo , J. , and Fern\u00e1ndez-Cuesta , F. 1994. Enhancement of the accelerated simulation method restart by considering multiple thresholds . In Proceedings of the 14th International Teletraffic Congress . Elsevier Science , 797--810. Vill\u00e9n-Altamirano, M., Martinez-Marr\u00f3n, A., Gamo, J., and Fern\u00e1ndez-Cuesta, F. 1994. Enhancement of the accelerated simulation method restart by considering multiple thresholds. In Proceedings of the 14th International Teletraffic Congress. Elsevier Science, 797--810."},{"key":"e_1_2_1_57_1","volume-title":"RESTART: A straightforward method for fast simulation of rare events. In Proceedings of the 1994 Winter Simulation Conference","author":"Vill\u00e9n-Altamirano M.","year":"1994","unstructured":"Vill\u00e9n-Altamirano , M. and Vill\u00e9n-Altamirano , J. 1994 . RESTART: A straightforward method for fast simulation of rare events. In Proceedings of the 1994 Winter Simulation Conference . IEEE Press , 282--289. Vill\u00e9n-Altamirano, M. and Vill\u00e9n-Altamirano, J. 1994. RESTART: A straightforward method for fast simulation of rare events. In Proceedings of the 1994 Winter Simulation Conference. IEEE Press, 282--289."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460130409"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147224.1147227"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1080\/01966324.1983.10737119"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1225275.1225280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1225275.1225280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:08Z","timestamp":1750278128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1225275.1225280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1225275.1225280"],"URL":"https:\/\/doi.org\/10.1145\/1225275.1225280","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}