The theory of direct probability redistribution and its application to rare event simulation

ABSTRACT

Rare event simulation is an important area of simulation theory, producing algorithms that can significantly reduce the simulation time when analyzing problems that involve rare events. However, existing rare event simulation techniques are rather restrictive, i.e., applicable only to systems with modest complexity. In this paper, we first develop a Markov chain transformation theory that can redistribute steady-state probabilities in a finite-size discrete-time Markov chain in an arbitrary and controlled manner. We descriptively name the theoretical procedure “direct probability redistribution” (DPR). In the second part of the paper, we develop DPR theory into a simulation algorithm that uses trajectory splitting to realize the DPR effect without knowledge of the transition probability matrix, thus allowing for easy application to systems with realistic complexity. DPR-based splitting can significantly reduce the simulation time by increasing the visitng frequency of rare states, and it avoids the problems associated with the decreasing likelihood ratio, which can be a limitation in conventional Importance Sampling techniques. The main advantage of the DPR-based simulation technique over existing splitting techniques is that DPR does not impose any restrictions on the state transitions and it provides asymptotically unbiased estimates even if the rare event set overlaps many splitting partitions. We conclude by providing examples where DPR-based simulation has been successfully applied to nontrivial queuing problems, including a system with flow control.

REFERENCES

• 1: BAYES, B.A. 1970. Statistical techniques for simulation models. Aust. Comput. J. 2, 4 (Nov.), 180-184.
• 2: 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]
• 3: GERSHT, A. AND LEE, K.J. 1991. A congestion control framework for ATM networks. IEEE J. Sel. Areas Commun. 9, 7 (Sept.), 1119-1130.
• 4: Paul Glasserman , Philip Heidelberger , Perwez Shahabuddin , Tim Zajic, Splitting for rare event simulation: analysis of simple cases, Proceedings of the 28th conference on Winter simulation, p.302-308, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256635]
• 5: GLASSERMAN, P., HEIDELBERGER, P., SHAHABUDDIN, P., AND ZAJIC, T. 1997. A look at multilevel splitting. In Proceedings of the Symposium on Monte Carlo and Quasi-Monte Carlo Methods 1996 (New York, NY), H. Niederreiter, P. Hellekalek, G. Larcher, and P. Zinterhof, Eds. Springer-Verlag, New York, NY, 98-101.
• 6: GLASSERMAN, P., HEIDELBERGER, P., SHAHABUDDIN, P., AND ZAJIC, T. 1998. A large deviations perspective on the efficiency of multilevel splitting. IEEE Trans. Automat. Contr. 43, 12 (Dec.), 1666-1679.
• 7: Paul Glasserman , Philip Heidelberger , Perwez Shahabuddin , Tim Zajic, Multilevel Splitting for Estimating Rare Event Probabilities, Operations Research, v.47 n.4, p.585-600, April 1999 [doi>10.1287/opre.47.4.585]
• 8: 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]
• 9: Ambuj Goyal , Perwez Shahabuddin , Philip Heidelberger , Victor F. Nicola , Peter W. Glynn, A Unified Framework for Simulating Markovian Models of Highly Dependable Systems, IEEE Transactions on Computers, v.41 n.1, p.36-51, January 1992 [doi>10.1109/12.123381]
• 10: GUNTHER, F. L. AND WOLFF, R.W. 1980. The almost regenerative method for stochastic system simulations. Oper. Res. 28, 2 (Mar.-Apr.), 375-386.
• 11: HAMMERSLEY, J. M. AND HANDSCOMB, D. C. 1964. Monte Carlo Methods. Methuen and Co., Ltd., London, England.
• 12: HARASZTI, Z. AND TOWNSEND, J. K. 1998. The theory of direct probability redistribution and its application to rare event simulation. In Proceedings of the IEEE International Conference on Communications (ICC'98, Piscataway, NJ, June), IEEE Press, Piscataway, NJ, 1443- 1450.
• 13: 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]
• 14: ISAACSON, D. L. AND MADSEN, R.W. 1976. Markov Chains: Theory and Applications. John Wiley and Sons, Inc., New York, NY.
• 15: KAHN, H. AND MARSHALL, A. W. 1953. Methods of reducing sample size in Monte Carlo computations. Oper. Res. Soc. Amer. 1,263-278.
• 16: SADOWSKY, J. S. AND BUCKLEW, J.A. 1990. On large deviation theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theor. IT-36, 3 (May), 579-588.
• 17: STEWART, W. J. 1994. Introduction to the Numerical Solution of Markov Processes. Princeton University Press, Princeton, NJ.
• 18: VILL N-ALTAMIRANO, J. 1998. RESTART method for the case where rare events can occur in retrials from any threshold. Int. J. Electron. Commun. 52, 3 (Nov.), 183-189.
• 19: VILL N-ALTAMIRANO, M., MART NEZ-MARR N, A., GAMO, J., AND FERN NDEZ-CUESTA, F. 1994. Enhancement of the accelerated simulation method RESTART by considering multiple thresholds. In Proceedings of the 14th International Teletraffic Congress (ITC 14, Amsterdam, The Netherlands), Elsevier North-Holland, Inc., Amsterdam, The Netherlands, 797-810.
• 20: VILL N-ALTAMIRANO, M. AND VILL N-ALTAMIRANO, J. 1991. RESTART: A method for accelerating rare event simulations. In Proceedings of the 13th International Teletraffic Congress: Queueing, Performance and Control in ATM (ITC 13, Copenhagen, Denmark, June), J. W. Cohen and C. D. Pack, Eds. Elsevier North-Holland, Inc., Amsterdam, The Netherlands, 71-76.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Performance, Theory

Keywords:
DPR, RESTART, accelerated simulation, discrete event simulation, importance sampling, queuing, rare event simulation, splitting