Simulating markov-reward processes with rare events

ABSTRACT

Simulating continuous-time Markov reward processes containing rarely visited, but economically important states requires long simulation times unless special measures are taken. In this article, we consider Markov reward processes in equilibrium, and we use the equilibrium equations to reallocate rewards. The effect of this reallocation is determined analytically for a number of small examples. In these examples, significant savings in run lengths were possible, especially in the case where the expected rewards are strongly influenced by low-probability boundary states. The emphasis of the article is on exploration; no large simulation problems have been considered.

REFERENCES

• 1: Daniel D. Deavours , William H. Sanders, An efficient disk-based tool for solving large Markov models, Performance Evaluation, v.33 n.1, p.67-84, June 1998 [doi>10.1016/S0166-5316(98)00010-8]
• 2: 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]
• 3: Grassmann, W. K. 1987. The asymptotic variance of a time average in a birth-death process. In Statistical and Computational Issues in Probability Modeling, Part 2, S. L. Albin and C. M. Harris, Eds. Annals of Operations Research, vol. 8. Balzers AG, Basel, Switzerland, 165--174.
• 4: Grassmann, W. K. 1993. Means and variances in Markov reward systems. In Linear Algebra, Markov Chains and Queueing Models, C. D. Meyer and R. J. Plemmons, Eds. The IMA Volumes in Mathematics and Its Applications, vol. 48. Springer-Verlag, New York, 193--204.
• 5: Grassmann, W. K., Chen, X., and Kashyap, B. R. 2001. Optimal service rates for the state-dependent M/G/1 queue in steady state. Oper. Res. Letters 29, 57--63.
• 6: Grassmann, W. K. and Heyman, D. P. 1990. Equilibrium distribution of block-structured Markov chains with repeating rows. J. Appl. Prob. 27, 557--576.
• 7: Grassmann, W. K. and Stanford, D. A. 1999. Matrix analytic methods. In Computational Probability, W. K. Grassmann, Ed. International Series in Operations Research and Management Science, vol. 24. Kluwer Academic Publishers, Boston, 153--203.
• 8: Grassmann, W. K., Taksar, M., and Heyman, D. P. 1993. Regenerative analysis and steady state distributions for Markov chains. Oper. Res. 33, 1107--1117.
• 9: Anne Greenbaum, Iterative methods for solving linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 10: Gerhard Haßlinger, Waiting time, busy periods and output models of a server analyzed via Wiener-Hopf factorization, Performance Evaluation, v.40 n.1-3, p.3-26, March 2000 [doi>10.1016/S0166-5316(99)00067-X]
• 11: 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]
• 12: Hordiijk, A., Iglehart, D. L., and Schassberger, R. 1976. Discrete methods for simulating continuous time Markov chains. Adv. Appl. Prob. 13, 772--788.
• 13: Jenkins, J. H. 1972. The relative efficiency of direct and maximum likelihood estimates of the mean waiting time in the simple queue, M/M/1. J. Appl. Prob. 9, 396--401.
• 14: Leonidas C. Kioussis , Douglas R. Miller, An importance sampling scheme for simulating the degradation and failure of complex systems during finite missions, Proceedings of the 15th conference on Winter Simulation, p.631-640, December 12-14, 1983, Arlington, Virginia, United States
• 15: Madansky, A. 1976. Optimal conditions for a simulation problem. Oper. Res. 24, 572--577.
• 16: Neuts, M. F. 1981. Matrix-Geometric Solutions in Stochastic Models, An Algorithmic Approach. Johns Hopkins University Press, Baltimore.
• 17: Neuts, M. F. 1989. Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York.
• 18: Emanuel Parzen, Stochastic processes, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 19: Reynolds, J. F. 1972. Some theorems on the covariance structure of markov chains. J. Appl. Prob. 9, 214--218.
• 20: Stewart, W. 1994. An Introduction to the Numerical Solution of Markov Chains. Princeton University Press, New Jersey.
• 21: Tan, B. 1999. Variance of the output as a function of time: Production line dynamics. EJOR 117, 470--484.
• 22: Aad P. A. Van Moorsel , Latha A. Kant , William H. Sanders, Computation of the Asymptotic Bias and Variance for Simulation of Markov Reward Models, Proceedings of the 29th Annual Simulation Symposium (SS '96), p.173, April 08-11, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Algorithms

Keywords:
Markov reward processes, Markovian event systems, Variance of time averages, rare event simulation, rare events, simulation