IDEAS home Printed from https://ideas.repec.org/a/eee/matcom/v44y1997i1p61-79.html
   My bibliography  Save this article

Optimal importance sampling for Markovian systems with applications to tandem queues

Author

Listed:
  • Kuruganti, I.
  • Strickland, S.

Abstract

Importance sampling is a change-of-measure technique for speeding up the simulation of rare events in stochastic systems. In this paper we establish a number of properties characterizing optimal importance sampling measures for Markovian systems. We use these properties to develop a new method for computing the optimal measure and give specific results for a tandem queueing system. Optimal measures, though as diffcult to compute as the rare event probability itself, give useful insight into the characteristics of importance sampling measures. Our approach has no immediate computational advantage over other methods, but it suggests a number of heuristic approximations which may lead to computationally attractive methods.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:matcom:v:44:y:1997:i:1:p:61-79
    DOI: 10.1016/S0378-4754(97)00049-9
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378475497000499
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/S0378-4754(97)00049-9?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
    ---><---

    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. Peter W. Glynn & Donald L. Iglehart, 1989. "Importance Sampling for Stochastic Simulations," Management Science, INFORMS, vol. 35(11), pages 1367-1392, November.
    Full references (including those not matched with items on IDEAS)

    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. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Barry L. Nelson, 2004. "50th Anniversary Article: Stochastic Simulation Research in Management Science," Management Science, INFORMS, vol. 50(7), pages 855-868, July.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Prusty, B Rajanarayan & Jena, Debashisha, 2017. "A critical review on probabilistic load flow studies in uncertainty constrained power systems with photovoltaic generation and a new approach," Renewable and Sustainable Energy Reviews, Elsevier, vol. 69(C), pages 1286-1302.
    14. Dassios, Angelos & Jang, Jiwook & Zhao, Hongbiao, 2015. "A risk model with renewal shot-noise Cox process," Insurance: Mathematics and Economics, Elsevier, vol. 65(C), pages 55-65.
    15. N. Hilber & N. Reich & C. Schwab & C. Winter, 2009. "Numerical methods for Lévy processes," Finance and Stochastics, Springer, vol. 13(4), pages 471-500, September.
    16. 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.
    17. 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.
    18. 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.
    19. N-H Shih, 2005. "Estimating completion-time distribution in stochastic activity networks," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 744-749, June.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:matcom:v:44:y:1997:i:1:p:61-79. 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.journals.elsevier.com/mathematics-and-computers-in-simulation/ .

    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.