Splitting for rare event simulation: analysis of simple cases

ABSTRACT

An approach to rare event simulation uses the technique of splitting. The basic idea is to split sample paths of the stochastic process into multiple copies when they approach closer to the rare set; this increases the overall number of hits to the rare set for a given amount of simulation time. This paper analyzes the bias and efficiency of some simple cases of this method.

REFERENCES

• 1: Bayes, A.j. 1970. Statistical techniques for simulation models. The Australian Computer Journal 2: 180-184.
• 2: Feller, W. 1968. An Introduction to Probability Theory and Its Applications, Volume I, Third Edition. New York: John Wiley & Sons, Inc.
• 3: Glasserman, P., P. Heidelberger, P. Shahabuddin, and T. Zajic. 1996. Multilevel Splitting for Estimating Rare Event Probabilities. IBM Research Report, Yorktown Heights, New York.
• 4: Peter W. Glynn , Ward Whitt, The asymptotic efficiency of simulation estimators, Operations Research, v.40 n.3, p.505-520, May–June 1992 [doi>10.1287/opre.40.3.505]
• 5: Hammersley, J., and D. Handscomb. 1965. Monte Carlo Methods. Methuen dz Co. Ltd., London.
• 6: Harris, T. 1989. The Theory of Branching Processes. Dover, New York.
• 7: 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]
• 8: Hopmans, A.C.M., and J.P.C. Kleijnen. 1979. Importance sampling in system simulation: A practical failure? Mathematics and Computing in Simulation XXI:209-220.
• 9: Kahn, H., and T.E. Harris. 1951. Estimation of Particle Transmission by Random Sampling. National Bureau of Standards Applied Mathematics Series 12, 27-30.
• 10: Perwez Shahabuddin, Rare event simulation in stochastic models, Proceedings of the 27th conference on Winter simulation, p.178-185, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224460]
• 11: Vill@n-Altamirano, M., and J. Vill~n-Altamirano. 1991. RESTART: A method for accelerating rare events simulation. In Proceedings of the 13th International Teletraffic Congress, Queuing performance and control in ATM, 71-76, North Holland Publishing Company.
• 12: Vill~n-Altamarino, M., A. Martinez Matron, J. Gamo and F. Fernandez-Cuesta. 1994. Enhancement of acclerated simulation method RESTART by considering multiple threshholds. In Proceedings of the 14th International Teletraffic Congress, The fundamental role of teletraffic in the evolution of telecommunication networks, 787-810, Elsevier.
• 13: Manuel Villén-Altamirano , José Villén-Altamirano, Restart: a straightforward method for fast simulation of rare events, Proceedings of the 26th conference on Winter simulation, p.282-289, December 11-14, 1994, Orlando, Florida, United States