Adaptive monte carlo methods for rare event simulation: adaptive monte carlo methods for rare event simulations

ABSTRACT

We review two types of adaptive Monte Carlo methods for rare event simulations. These methods are based on importance sampling. The first approach selects importance sampling distributions by minimizing the variance of importance sampling estimator. The second approach selects importance sampling distributions by minimizing the cross entropy to the optimal importance sampling distribution. We also review the basic concepts of importance sampling in the rare event simulation context. To make the basic concepts concrete, we introduce these ideas via the study of rare events of M/M/1 queues.

REFERENCES

• 1: Al-Qaq, W. A., M. Devetsikiotis, and J. K. Townsend. 1995. Stochastic gradient optimization of importance sampling for the efficient simulation of digital communication systems. IEEE Transactions on Communications, 43:2975--2985.
• 2: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 3: Bucklew, J. 1990. Large Deviation Techniques in Decision, Simulation, and Estimation. John Wiley and Sons, Inc., New York.
• 4: Pieter-Tjerk de Boer , Victor F. Nicola , Reuven Y. Rubinstein, Techniques for simulating difficutl queueing problems: adaptive importance sampling simulation of queueing networks, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 5: Dembo, A. and O. Zeitouni. 1993. Large Deviation Techniques and Applications. Jones and Bartlett, Boston.
• 6: Devetsikiotis, M. and J. K. Townsend. 1993a. An algorithmic approach to the optimization of importance sampling parameters in digital communication system simulation. IEEE Transactions on Communications 41:1464--1473.
• 7: Michael Devetsikiotis , J. Keith Townsend, Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.293-305, June 1993 [doi>10.1109/90.234852]
• 8: Fu, M. C., and J. Q. Hu. 1997. Conditional Monte Carlo: Gradient estimation and optimization applications. Kluwer Academic Publisher, Boston.
• 9: Glasserman, P. 1991. Gradient estimation via perturbation analysis. Boston: Kluwer.
• 10: Peter W. Glynn, Stochastic approximation for Monte Carlo optimization, Proceedings of the 18th conference on Winter simulation, p.356-365, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318459]
• 11: Peter W. Glynn, Likelihood ratio gradient estimation for stochastic systems, Communications of the ACM, v.33 n.10, p.75-84, Oct. 1990 [doi>10.1145/84537.84552]
• 12: Glynn, P. W. 1994. Efficiency improvement techniques. Annals of Oper. Res., 53:175--197.
• 13: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 14: Hammersley, J. M. and D. C. Handscomb. 1965. Monte Carlo Methods. Methuen & Co. Ltd., London.
• 15: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 16: Lehtonen, T. and H. Nyrhinen. 1992. Simulating level-crossing probabilities by importance sampling. Adv. in Appl. Probab., 24(4):858--874.
• 17: Lieber, D., R. Y. Rubinstein and D. Elmakis. 1997. Quick estimation of rare events in stochastic networks. IEEE Trans. Rel., 46(2):254--265.
• 18: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 19: Kapur, J. N. and H. K. Kesavan. 1992. Entropy Optimization Principles with Applications. Academic Press.
• 20: Karlin, S. and H. M. Taylor. 1975. A First Course in Stochastic Processes. Academic Press, New York-London, second edition.
• 21: Kiefer, J., and J. Wolfowitz. 1952. Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics, 23:462--466.
• 22: Robbins, H., and S. Monro. 1951. A stochastic approximation method. Annals of Mathematical Statistics, 22:400--407.
• 23: Reuven Y. Rubinstein, Sensitivity analysis of discrete event systems by the “push out” method, Annals of Operations Research, v.39 n.1-4, p.229-250, 1992 [doi>10.1007/BF02060943]
• 24: Rubinstein, R. Y. 1997. Optimization of computer simulation models with rare events. European Journal of Operations Research 99:89--112.
• 25: Rubinstein, R. Y. 1999. Rare event simulation via crossentropy and importance sampling. In Second International Workshop on Rare Event Simulation, RESIM 99, 1--17.
• 26: Rubinstein, R. Y. and B. Melamed. 1998. Modern Simulation and Modeling. Wiley.
• 27: Siegmund, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist., 4(4):673--684.
• 28: Yi Su , Michael C. Fu, Simulation in financial engineering: importance sampling in derivative securities pricing, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 29: Felisa J. Vázquez-Abad , Daniel Dufresne, Accelerated simulation for pricing Asian options, Proceedings of the 30th conference on Winter simulation, p.1493-1500, December 13-16, 1998, Washington, D.C., United States