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

Importance functions for restart simulation of general Jackson networks

Author

Listed:
  • Villén-Altamirano, José

Abstract

RESTART is an accelerated simulation technique that allows the evaluation of extremely low probabilities. In this method a number of simulation retrials are performed when the process enters regions of the state space where the chance of occurrence of the rare event is higher. These regions are defined by means of a function of the system state called the importance function. Guidelines for obtaining suitable importance functions and formulas for the importance function of two-stage networks were provided in previous papers. In this paper, we obtain effective importance functions for RESTART simulation of Jackson networks where the rare set is defined as the number of customers in a particular ('target') node exceeding a predefined threshold. Although some rough approximations and assumptions are used to derive the formulas of the importance functions, they are good enough to estimate accurately very low probabilities for different network topologies within short computational time.

Suggested Citation

  • Villén-Altamirano, José, 2010. "Importance functions for restart simulation of general Jackson networks," European Journal of Operational Research, Elsevier, vol. 203(1), pages 156-165, May.
    • Handle: RePEc:eee:ejores:v:203:y:2010:i:1:p:156-165
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00523-2
    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. 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.
    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. Balsamo, Simonetta & Marin, Andrea, 2013. "Separable solutions for Markov processes in random environments," European Journal of Operational Research, Elsevier, vol. 229(2), pages 391-403.

    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. Kontosakos, Vasileios E. & Mendonca, Keegan & Pantelous, Athanasios A. & Zuev, Konstantin M., 2021. "Pricing discretely-monitored double barrier options with small probabilities of execution," European Journal of Operational Research, Elsevier, vol. 290(1), pages 313-330.
    2. 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.
    3. 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.
    4. 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.
    5. Paredes, R. & Dueñas-Osorio, L. & Meel, K.S. & Vardi, M.Y., 2019. "Principled network reliability approximation: A counting-based approach," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    6. Krystul, Jaroslav & Le Gland, François & Lezaud, Pascal, 2012. "Sampling per mode for rare event simulation in switching diffusions," Stochastic Processes and their Applications, Elsevier, vol. 122(7), pages 2639-2667.
    7. Michael B. Giles, 2008. "Multilevel Monte Carlo Path Simulation," Operations Research, INFORMS, vol. 56(3), pages 607-617, June.
    8. Lagnoux-Renaudie, Agnès, 2008. "Effective branching splitting method under cost constraint," Stochastic Processes and their Applications, Elsevier, vol. 118(10), pages 1820-1851, October.
    9. Fabian Dickmann & Nikolaus Schweizer, 2014. "Faster Comparison of Stopping Times by Nested Conditional Monte Carlo," Papers 1402.0243, arXiv.org.
    10. D.D. Riley & X. Koutsoukos, 2014. "Probabilistic verification of a biodiesel production system using statistical model checking," Mathematical and Computer Modelling of Dynamical Systems, Taylor & Francis Journals, vol. 20(5), pages 452-469, September.
    11. James Hodgson & Adam M. Johansen & Murray Pollock, 2022. "Unbiased Simulation of Rare Events in Continuous Time," Methodology and Computing in Applied Probability, Springer, vol. 24(3), pages 2123-2148, September.
    12. Pierre L'Ecuyer & Christian Lécot & Bruno Tuffin, 2008. "A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains," Operations Research, INFORMS, vol. 56(4), pages 958-975, August.
    13. Zdravko I. Botev & Pierre L'Ecuyer & Gerardo Rubino & Richard Simard & Bruno Tuffin, 2013. "Static Network Reliability Estimation via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 56-71, February.
    14. Zdravko I. Botev & Pierre L’Ecuyer, 2020. "Sampling Conditionally on a Rare Event via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 986-995, October.
    15. Thomas Dean & Paul Dupuis, 2011. "The design and analysis of a generalized RESTART/DPR algorithm for rare event simulation," Annals of Operations Research, Springer, vol. 189(1), pages 63-102, September.
    16. Hao Ma & Henk A. P. Blom, 2022. "Random Assignment Versus Fixed Assignment in Multilevel Importance Splitting for Estimating Stochastic Reach Probabilities," Methodology and Computing in Applied Probability, Springer, vol. 24(4), pages 2313-2338, December.
    17. Reuven Rubinstein, 2013. "Stochastic Enumeration Method for Counting NP-Hard Problems," Methodology and Computing in Applied Probability, Springer, vol. 15(2), pages 249-291, June.
    18. 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.
    19. 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.
    20. Paul Glasserman & Jeremy Staum, 2001. "Conditioning on One-Step Survival for Barrier Option Simulations," Operations Research, INFORMS, vol. 49(6), pages 923-937, December.

    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:203:y:2010:i:1:p:156-165. 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.