IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v207y2010i3p1380-1397.html
   My bibliography  Save this article

The cross-entropy method with patching for rare-event simulation of large Markov chains

Author

Listed:
  • Kaynar, Bahar
  • Ridder, Ad

Abstract

There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a general state-dependent importance sampling method which partitions the state space and applies the cross-entropy method to each partition. We investigate two versions of our algorithm and apply them to several examples of reliability and queueing models. In all these examples we compare our method with other importance sampling schemes. The performance of the importance sampling schemes is measured by the relative error of the estimator and by the efficiency of the algorithm. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:207:y:2010:i:3:p:1380-1397
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00484-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Perwez Shahabuddin, 1994. "Importance Sampling for the Simulation of Highly Reliable Markovian Systems," Management Science, INFORMS, vol. 40(3), pages 333-352, March.
    2. T. P. I. Ahamed & V. S. Borkar & S. Juneja, 2006. "Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation," Operations Research, INFORMS, vol. 54(3), pages 489-504, June.
    3. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    4. Paul Glasserman & Philip Heidelberger & Perwez Shahabuddin & Tim Zajic, 1999. "Multilevel Splitting for Estimating Rare Event Probabilities," Operations Research, INFORMS, vol. 47(4), pages 585-600, August.
    5. Peter W. Glynn & Donald L. Iglehart, 1989. "Importance Sampling for Stochastic Simulations," Management Science, INFORMS, vol. 35(11), pages 1367-1392, November.
    6. P. T. de Boer & D. P. Kroese & R. Y. Rubinstein, 2004. "A Fast Cross-Entropy Method for Estimating Buffer Overflows in Queueing Networks," Management Science, INFORMS, vol. 50(7), pages 883-895, July.
    7. Sigrún Andradóttir & Daniel P. Heyman & Teunis J. Ott, 1995. "On the Choice of Alternative Measures in Importance Sampling with Markov Chains," Operations Research, INFORMS, vol. 43(3), pages 509-519, June.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Kleijnen, Jack P.C. & Ridder, A.A.N. & Rubinstein, R.Y., 2010. "Variance Reduction Techniques in Monte Carlo Methods," Other publications TiSEM 87680d1a-53c1-4107-ada4-7, Tilburg University, School of Economics and Management.
    2. 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.
    3. Nikola Gradojevic & Marko Caric, 2017. "Predicting Systemic Risk with Entropic Indicators," Journal of Forecasting, John Wiley & Sons, Ltd., vol. 36(1), pages 16-25, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bahar Kaynar & Ad Ridder, 2009. "The Cross-Entropy Method with Patching for Rare-Event Simulation of Large Markov Chains," Tinbergen Institute Discussion Papers 09-084/4, Tinbergen Institute.
    2. 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.
    3. 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.
    4. 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.
    5. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    6. Tito Homem-de-Mello, 2007. "A Study on the Cross-Entropy Method for Rare-Event Probability Estimation," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 381-394, August.
    7. 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.
    8. T. P. I. Ahamed & V. S. Borkar & S. Juneja, 2006. "Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation," Operations Research, INFORMS, vol. 54(3), pages 489-504, June.
    9. 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.
    10. Cheng-Der Fuh & Yanwei Jia & Steven Kou, 2023. "A General Framework for Importance Sampling with Latent Markov Processes," Papers 2311.12330, arXiv.org.
    11. 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.
    12. M. Garvels, 2011. "A combined splitting—cross entropy method for rare-event probability estimation of queueing networks," Annals of Operations Research, Springer, vol. 189(1), pages 167-185, September.
    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. Fakhouri H. & Nasroallah A., 2009. "On the simulation of Markov chain steady-state distribution using CFTP algorithm," Monte Carlo Methods and Applications, De Gruyter, vol. 15(2), pages 91-105, January.
    15. Paul Glasserman & Jeremy Staum, 2001. "Conditioning on One-Step Survival for Barrier Option Simulations," Operations Research, INFORMS, vol. 49(6), pages 923-937, December.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. Philippe Jehiel & Jakub Steiner, 2020. "Selective Sampling with Information-Storage Constraints [On interim rationality, belief formation and learning in decision problems with bounded memory]," The Economic Journal, Royal Economic Society, vol. 130(630), pages 1753-1781.

    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:eee:ejores:v:207:y:2010:i:3:p:1380-1397. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.