Abstract
We describe a new Monte Carlo algorithm for the consistent and unbiased estimation of multidimensional integrals and the efficient sampling from multidimensional densities. The algorithm is inspired by the classical splitting method and can be applied to general static simulation models. We provide examples from rare-event probability estimation, counting, and sampling, demonstrating that the proposed method can outperform existing Markov chain sampling methods in terms of convergence speed and accuracy.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Botev, Z.I.: Three examples of a practical exact Markov chain sampling. Postgraduate Seminar Paper, School of Mathematics and Physics, The University of Queensland. http://espace.library.uq.edu.au/view/UQ:130865 (2007)
Botev, Z.I.: An algorithm for rare-event probability estimation using the product rule of probability theory. Technical report, School of Mathematics and Physics, The University of Queensland. http://espace.library.uq.edu.au/view/UQ:151299 (2008)
Botev, Z.I.: Splitting methods for efficient combinatorial counting and rare-event probability estimation. Technical report, School of Mathematics and Physics, The University of Queensland. http://espace.library.uq.edu.au/view/UQ:178513 (2009)
Botev, Z.I., Kroese, D.P.: The generalized cross entropy method, with applications to probability density estimation. Methodol. Comput. Appl. Probab. (2009). doi:10.1007/s11009-009-9133-7
Brooks, S.P., Roberts, G.O.: Convergence assessment techniques for Markov Chain Monte Carlo. Stat. Comput. 8, 319–335 (1998)
Brooks, S.P., Dellaportas, P., Roberts, G.O.: An approach to diagnosing total variation convergence of MCMC algorithms. J. Comput. Graph. Stat. 1, 251–265 (1997)
Cérou, F., Guyader, A.: Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25, 417–443 (2007)
Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Rare-event simulation for a static distribution. INRIA-00350762 (2009)
Chen, M.H., Shao, Q.M., Ibrahim, J.G.: Monte Carlo Methods in Bayesian Computation. Springer, New York (2000)
Gander, W., Gautschi, W.: Adaptive quadrature—revisited. BIT Numer. Math. 40, 84–101 (2000)
Garvels, M.J.J.: The splitting method in rare event simulation. PhD thesis, University of Twente, The Netherlands, October 2000
Garvels, M.J.J., Kroese, D.P.: A comparison of RESTART implementations. In: Proceedings of the 1998 Winter Simulation Conference, pp. 601–609. Washington, DC (1998)
Garvels, M.J.J., Kroese, D.P., van Ommeren, J.C.W.: On the importance function in splitting simulation. Eur. Trans. Telecommun. 13(4), 363–371 (2002)
Gelman, A., Rubin, D.: Inference from iterative simulation using multiple sequences (with discussion). Stat. Sci. 7, 457–511 (1992)
Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: A look at multilevel splitting. In: Niederreiter, H. (ed.) Monte Carlo and Quasi Monte Carlo Methods 1996. Lecture Notes in Statistics, vol. 127, pp. 99–108. Springer, New York (1996)
Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: A large deviations perspective on the efficiency of multilevel splitting. IEEE Trans. Autom. Control 43(12), 1666–1679 (1998)
Gu, J., Purdom, P.W., Franco, J., Wah, B.W.: Algorithms for the satisfiability (SAT) problem: a survey. In: Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics, vol. 35. American Mathematical Society, Providence (1996)
Hoos, H.H., Stützle, T.: SATLIB: an online resource for research on SAT. In: Gent, I.P., Maaren, H.V., Walsh, T. (eds.) SAT 2000, pp. 283–292. IOS Press, The Netherlands (2000). www.satlib.org
Johansen, A.M., Del Moral, P., Doucet, A.: Sequential Monte Carlo samplers for rare events. In: Proc. 6th International Workshop on Rare Event Simulation (2006)
Kahn, H., Harris, T.E.: Estimation of Particle Transmission by Random Sampling. National Bureau of Standards Applied Mathematics Series (1951)
Kou, S.C., Zhou, Q., Wong, W.H.: Equi-energy sampler with applications in statistical inference and statistical mechanics. Ann. Stat. 34, 1581–1619 (2006)
Lagnoux-Renaudie, A.: Rare event simulation. Probab. Eng. Inf. Sci. 20(1), 45–66 (2006)
Lagnoux-Renaudie, A.: Rare event simulation: effective splitting model under cost constraint. In: Stochastic Processes and Their Applications, pp. 1820–1851 (2008)
L’Ecuyer, P., Demers, V., Tuffin, B.: Splitting for rare-event simulation. In: Proceedings of the 2006 Winter Simulation Conference, pp. 137–148 (2006)
L’Ecuyer, P., Demers, V., Tuffin, B.: Rare events, splitting, and quasi-Monte Carlo. ACM Trans. Model. Comput. Simul. 17(2), 1–44 (2007)
Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2001)
Del Moral, P.: Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications. Springer, New York (2004)
Del Moral, P., Doucet, A., Jasra, A.: Sequential Monte Carlo samplers. J. R. Stat. Soc. B 68(3), 411–436 (2006)
Robert, C.P., Casella, G.: Monte Carlo Statistical Methods, 2nd edn. Springer, New York (2004)
Rubinstein, R.Y., Kroese, D.P.: The Cross-Entropy Method. Springer, New York (2004)
Rubinstein, R.Y., Kroese, D.P.: Simulation and the Monte Carlo Method, 2nd edn. Wiley, New York (2007)
Villén-Altamirano, M., Villén-Altamirano, J.: RESTART: a method for accelerating rare event simulations. In: Cohen, J.W., Pack, C.D. (eds.) Proceedings of the 13th International Teletraffic Congress, Queueing, Performance and Control in ATM, pp. 71–76 (1991)
Villén-Altamirano, M., Villén-Altamirano, J.: RESTART: a straightforward method for fast simulation of rare events. In: Tew, J.D., Manivannan, S., Sadowski, D.A., Seila, A.F. (eds.) Proceedings of the 1994 Winter Simulation Conference, pp. 282–289 (1994)
Villén-Altamirano, M., Villén-Altamirano, J.: About the efficiency of RESTART. In: Proceedings of the RESIM’99 Workshop, pp. 99–128. University of Twente, The Netherlands (1999)
Welsh, D.J.A.: Complexity: Knots, Coloring and Counting. Cambridge University Press, Cambridge (1993)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Botev, Z.I., Kroese, D.P. Efficient Monte Carlo simulation via the generalized splitting method. Stat Comput 22, 1–16 (2012). https://doi.org/10.1007/s11222-010-9201-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11222-010-9201-4