Abstract
We consider a general class of branching methods with killing for the estimation of rare events. The class includes a number of existing schemes, including RESTART and DPR (Direct Probability Redistribution). A method for the design and analysis is developed when the quantity of interest can be embedded in a sequence whose limit is determined by a large deviation principle. A notion of subsolution for the related calculus of variations problem is introduced, and two main results are proved. One is that the number of particles and the total work scales subexponentially in the large deviation parameter when the branching process is constructed according to a subsolution. The second is that the asymptotic performance of the schemes as measured by the variance of the estimate can be characterized in terms of the subsolution. Some examples are given to demonstrate the performance of the method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Asmussen, S., & Glynn, P. (2007). Stochastic simulation: algorithms and analysis. New York: Springer.
Bardi, M., & Capuzzo-Dolcetta, I. (1997). Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations. Boston: Birkhäuser.
Crisan, D., & Lyons, T. (2002). Minimal entropy approximations and optimal algorithms for the filtering problem. Monte Carlo Methods and Applications, 8, 343–356.
Dean, T. (2008). A subsolutions approach to the analysis and implementation of splitting algorithms in rare event simulation. PhD Thesis, Brown University.
Dean, T., & Dupuis, P. (2009). Splitting for rare event simulation: A large deviation approach to design and analysis. Stochastic Processes and Their Applications, 119(2), 562–587.
Dupuis, P., & Ellis, R. (1997). A weak convergence approach to the theory of large deviations. New York: Wiley.
Dupuis, P., & Wang, H. (2007). Subsolutions of an Isaacs equation and efficient schemes for importance sampling. Mathematics of Operations Research, 32, 1–35.
Dupuis, P., & Wang, H. (2008). Importance sampling for Jackson networks. Preprint.
Dupuis, P., Ishii, H., & Soner, H. M. (1990). A viscosity solution approach to the asymptotic analysis of queueing systems. Annals Probability, 18, 226–255.
Dupuis, P., Sezer, A., & Wang, H. (2007). Dynamic importance sampling for queueing networks. Annals Applied Probability, 17, 1306–1346.
Freidlin, M. I., & Wentzell, A. D. (1984). Random perturbations of dynamical systems. New York: Springer.
Gelenbe, E., & Pujolle, G. (1987). Introduction to queueing networks. New York: Wiley.
Gilks, W. R., Richardson, S., & Spiegelhalter, D. J. (Eds.) (1996). Markov chain Monte Carlo in practice. London: Chapman & Hall.
Glasserman, P., Heidelberger, P., Shahabuddin, P., & Zajic, T. (1998). A large deviations perspective on the efficiency of multilevel splitting. IEEE Transaction Automatic Control, 43, 1666–1679.
Glasserman, P., Heidelberger, P., Shahabuddin, P., & Zajic, T. (1999). Multilevel splitting for estimating rare event probabilities. Operational Research, 47, 585–600.
Haraszti, Z., & Townsend, J. K. (1998). The theory of direct probability redistribution and its application to rare event simulation. In Proc. of the IEEE international conference on communications 1998 (pp. 1443–1450).
Haraszti, Z., & Townsend, J. K. (1999). The theory of direct probability redistribution and its application to rare event simulation. ACM Transactions on Modelling and Computer Simulation, 9, 105–140.
L’Ecuyer, P., Demers, V., & Tuffin, B. (2007). Rare events, splitting and quasi-Monte Carlo. ACM Transactions on Modeling and Computer Simulation (TOMACS), 17(2), Article 9.
Madras, N. (2002). Lectures on Monte Carlo methods. Providence: American Mathematical Society.
Meyn, S. P., & Tweedie, R. L. (1994). Markov chains and stochastic stability. Berlin: Springer.
Moran, P. (1975). The estimation of standard errors in Monte Carlo simulation experiments. Biometrika, 62, 1–4.
Norris, J. R. (1998). Markov chains. Cambridge: Cambridge University Press.
Sandmann, W. (Ed.) (2006). Proceedings of the 6th international workshop on rare event simulation, RESIM 2006, Bamberg, Germany, 8–10 October 2006, 296 pp.
Sezer, A. (2009). Importance sampling for a Markov modulated queuing network. Stochastic Processes and Their Applications, 119(2), 491–517.
Villen-Altamirano, J. (2007). Rare event RESTART simulation of two-stage networks. European Journal of Operations Research, 179, 148–159.
Villen-Altamirano, M., & Villen-Altamirano, J. (1991). RESTART: A method for accelerating rare event simulations. In Proc. of the 13th international teletraffic congress, queueing, performance and control in ATM (pp. 71–76). Amsterdam: Elsevier.
Villen-Altamirano, M., & Villen-Altamirano, J. (1994). RESTART: A straightforward method for fast simulation of rare events. In Proc. of the 1994 winter simulation conference (pp. 282–289).
Villen-Altamirano, M., & Villen-Altamirano, J. (2002). Analysis of RESTART simulation: Theoretical basis and sensitivity study. European Transactions on Telecommunications, 13, 373–385.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of T. Dean supported in part by the National Science Foundation (NSF-DMS-0404806 and NSF-DMS-0706003).
Research of P. Dupuis supported in part by the National Science Foundation (NSF-DMS-0404806 and NSF-DMS-0706003), the Army Research Office (W911NF-05-1-0289), and the Air Force Office of Scientific Research (FA9550-07-1-0544).
Rights and permissions
About this article
Cite this article
Dean, T., Dupuis, P. The design and analysis of a generalized RESTART/DPR algorithm for rare event simulation. Ann Oper Res 189, 63–102 (2011). https://doi.org/10.1007/s10479-009-0664-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-009-0664-7