Variance reduction in mean time to failure simulations

ABSTRACT

We describe two variance reduction methods for estimating the mean time to failure (MTTF) in Markovian models of highly reliable systems. The first method is based on a ratio representation of the MTTF and employs importance sampling. The second method is based on a hybrid simulation/analytic technique where the number of simulated transitions are reduced by computing partial results analytically. Experiments with a large example show the effectiveness of both techniques for highly reliable systems.

REFERENCES

• 1: Chung, K.L. (1967). Markov Chains With Stationary Transition Probabilities, Second Edition. Springer- Verlag, New York.
• 2: Conway, A.E. and Goyal, A. (1987). Monte Carlo Simulation of Computer System Availability/Reliability Models. Proceedings of the Seventeenth Symposium on Fault-Tolerant Computing. Pittsburgh, Pennsylvania, 230-235.
• 3: Cottrei1, M., Fort, J.C. and Malgouyres, G. (1983). Large Deviations and Rare Events in the Study of Stochastic Algorithms. IEEE Transactions on Automatic Control AC-28, 907-920.
• 4: Crane, M.A. and Iglehart, D.L. (1975). Simulating Stable Stochastic, Systems, HI: Regenerative Processes and Discrete Event Simulations. Operations Research 23, 33-45.
• 5: Fox, B.L. and Glynn, P.W. (1986). Discrete-Time Conversion for Simulating Semi-Markov Processes. Operations Research Letters 5, 191-196.
• 6: Geist, R.ld. and Trivedi, K.S. (1983). Ultra-High Reliability Prediction for Fault-Tolerant Computer Systems. 1EEE Transactions on Computers C-32, 1118-1127.
• 7: Ambuj Goyal , Stephen S. Lavenberg, Modeling and analysis of computer system availability, IBM Journal of Research and Development, v.31 n.6, p.651-664, Dec. 1987
• 8: Ambuj Goyal , Philip Heidelberger , Perwez Shahabuddin, Measure specific dynamic importance sampling for availability simulations, Proceedings of the 19th conference on Winter simulation, p.351-357, December 14-16, 1987, Atlanta, Georgia, United States [doi>10.1145/318371.318607]
• 9: Hammersley, J.M. and Handscomb, D.C. (1964). Monte Carlo Methods. Methuen, London.
• 10: Heidelberger, P. (1979). A Variance Reduction Technique That Increases Regeneration Frequency. Current lssues in Computer Simulation. N.R. Adam and /k. Dogramaci (eds.). Academic Press, Inc., 257-269.
• 11: Hordijk, A., Iglehart, D.L. and Schassberger, R. (1976). Discrete Time Methods for Simulating Continuous Time Markov Chains. Adv. AppL Prob. 8, 772-788.
• 12: Lewis, E.E. and Bohm, F. (1984). Monte Carlo Simulation of Markov Unreliability Models. Nuclear Engineering and Design 77, 49-62.
• 13: Siegmund, D. (1976). Importance Sampling in the Monte Carlo Study of Sequential Tests. The Annals of Statistics 4, 673-684.
• 14: Walrand, J. (1987). Quick Simulation of Rare Events in Queueing Networks. Proceedings of the Second International Workshop on Applied Mathematics and Performance~ Reliability Models of Computer/Communication Systems. G. Iazeolla, P.J. Courtois and O.J. Boxma (eds). North Holland Publishing Company, Amsterdam, 275-286.

INDEX TERMS

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

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

General Terms:
Design, Experimentation, Measurement, Performance, Reliability, Theory