IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v40y1994i3p333-352.html
   My bibliography  Save this article

Importance Sampling for the Simulation of Highly Reliable Markovian Systems

Author

Listed:
  • Perwez Shahabuddin

    (IBM Research Division, T. J. Watson Research Center, Yorktown Heights, New York 10598)

Abstract

In this paper we investigate importance sampling techniques for the simulation of Markovian systems with highly reliable components. The need for simulation arises because the state space of such systems is typically huge, making numerical computation inefficient. Naive simulation is inefficient due to the rarity of the system failure events. Failure biasing is a useful importance sampling technique for the simulation of such systems. However, until now, this technique has been largely heuristic. We present a mathematical framework for the study of failure biasing. Using this framework we derive variance reduction results which explain the orders of magnitude of variance reduction obtained in practice. We show that in many cases the magnitude of the variance reduction is such that the relative errors of the estimates remain bounded as the failure rates of components tend to zero. We also prove that the failure biasing heuristic in its original form may not give bounded relative error for a large class of systems and that a modification of the heuristic works for the general case. The theoretical results in this paper agree with experiments on the subject which have been reported in a previous paper.

Suggested Citation

  • Perwez Shahabuddin, 1994. "Importance Sampling for the Simulation of Highly Reliable Markovian Systems," Management Science, INFORMS, vol. 40(3), pages 333-352, March.
    • Handle: RePEc:inm:ormnsc:v:40:y:1994:i:3:p:333-352
    DOI: 10.1287/mnsc.40.3.333
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.40.3.333
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.40.3.333?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Cancela Héctor & Rubino Gerardo & Tuffin Bruno, 2002. "MTTF Estimation using importance sampling on Markov models," Monte Carlo Methods and Applications, De Gruyter, vol. 8(4), pages 321-342, December.
    2. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    3. Helton, J.C. & Hansen, C.W. & Sallaberry, C.J., 2014. "Conceptual structure and computational organization of the 2008 performance assessment for the proposed high-level radioactive waste repository at Yucca Mountain, Nevada," Reliability Engineering and System Safety, Elsevier, vol. 122(C), pages 223-248.
    4. Helton, J.C. & Johnson, J.D. & Oberkampf, W.L., 2006. "Probability of loss of assured safety in temperature dependent systems with multiple weak and strong links," Reliability Engineering and System Safety, Elsevier, vol. 91(3), pages 320-348.
    5. Xiao, Gang & Li, Zhizhong & Li, Ting, 2007. "Dependability estimation for non-Markov consecutive-k-out-of-n: F repairable systems by fast simulation," Reliability Engineering and System Safety, Elsevier, vol. 92(3), pages 293-299.
    6. Paul Glasserman & Sandeep Juneja, 2008. "Uniformly Efficient Importance Sampling for the Tail Distribution of Sums of Random Variables," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 36-50, February.
    7. Pierre L’Ecuyer & Bruno Tuffin, 2011. "Approximating zero-variance importance sampling in a reliability setting," Annals of Operations Research, Springer, vol. 189(1), pages 277-297, September.
    8. Ad Ridder & Bruno Tuffin, 2012. "Probabilistic Bounded Relative Error Property for Learning Rare Event Simulation Techniques," Tinbergen Institute Discussion Papers 12-103/III, Tinbergen Institute.
    9. Ad Ridder, 2005. "Importance Sampling Simulations of Markovian Reliability Systems Using Cross-Entropy," Annals of Operations Research, Springer, vol. 134(1), pages 119-136, February.
    10. Kuruganti, I. & Strickland, S., 1997. "Optimal importance sampling for Markovian systems with applications to tandem queues," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 44(1), pages 61-79.
    11. Hernan P. Awad & Peter W. Glynn & Reuven Y. Rubinstein, 2013. "Zero-Variance Importance Sampling Estimators for Markov Process Expectations," Mathematics of Operations Research, INFORMS, vol. 38(2), pages 358-388, May.
    12. Helton, J.C. & Johnson, J.D. & Oberkampf, W.L., 2007. "Verification test problems for the calculation of probability of loss of assured safety in temperature-dependent systems with multiple weak and strong links," Reliability Engineering and System Safety, Elsevier, vol. 92(10), pages 1374-1387.
    13. Barry L. Nelson, 2004. "50th Anniversary Article: Stochastic Simulation Research in Management Science," Management Science, INFORMS, vol. 50(7), pages 855-868, July.
    14. Villén-Altamirano, J., 2014. "Asymptotic optimality of RESTART estimators in highly dependable systems," Reliability Engineering and System Safety, Elsevier, vol. 130(C), pages 115-124.
    15. Nam Kyoo Boots & Perwez Shahabuddin, 2001. "Simulating Tail Probabilities in GI/GI.1 Queues and Insurance Risk Processes with Subexponentail Distributions," Tinbergen Institute Discussion Papers 01-012/4, Tinbergen Institute.
    16. Kaynar, Bahar & Ridder, Ad, 2010. "The cross-entropy method with patching for rare-event simulation of large Markov chains," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1380-1397, December.
    17. Helton, Jon C. & Sallaberry, Cedric J., 2009. "Computational implementation of sampling-based approaches to the calculation of expected dose in performance assessments for the proposed high-level radioactive waste repository at Yucca Mountain, Nev," Reliability Engineering and System Safety, Elsevier, vol. 94(3), pages 699-721.
    18. Helton, J.C. & Johnson, J.D. & Sallaberry, C.J. & Storlie, C.B., 2006. "Survey of sampling-based methods for uncertainty and sensitivity analysis," Reliability Engineering and System Safety, Elsevier, vol. 91(10), pages 1175-1209.
    19. Paul Glasserman & Philip Heidelberger & Perwez Shahabuddin, 2000. "Variance Reduction Techniques for Estimating Value-at-Risk," Management Science, INFORMS, vol. 46(10), pages 1349-1364, October.
    20. Alexander L Krall & Michael E Kuhl & Shanchieh J Yang, 2022. "Estimation of cyber network risk using rare event simulation," The Journal of Defense Modeling and Simulation, , vol. 19(1), pages 37-55, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:40:y:1994:i:3:p:333-352. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.