IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v54y2006i3p489-504.html
   My bibliography  Save this article

Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation

Author

Listed:
  • T. P. I. Ahamed

    (Department of Electrical Engineering, T. K. M. College of Engineering, Kollam 691005, India)

  • V. S. Borkar

    (School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India)

  • S. Juneja

    (School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India)

Abstract

For a discrete-time finite-state Markov chain, we develop an adaptive importance sampling scheme to estimate the expected total cost before hitting a set of terminal states. This scheme updates the change of measure at every transition using constant or decreasing step-size stochastic approximation. The updates are shown to concentrate asymptotically in a neighborhood of the desired zero-variance estimator. Through simulation experiments on simple Markovian queues, we observe that the proposed technique performs very well in estimating performance measures related to rare events associated with queue lengths exceeding prescribed thresholds. We include performance comparisons of the proposed algorithm with existing adaptive importance sampling algorithms on some examples. We also discuss the extension of the technique to estimate the infinite horizon expected discounted cost and the expected average cost.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:54:y:2006:i:3:p:489-504
    DOI: 10.1287/opre.1060.0291
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1060.0291
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1060.0291?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
    ---><---

    References listed on IDEAS

    as
    1. Peter W. Glynn & Donald L. Iglehart, 1993. "Notes: Conditions for the Applicability of the Regenerative Method," Management Science, INFORMS, vol. 39(9), pages 1108-1111, September.
    2. Peter W. Glynn & Donald L. Iglehart, 1989. "Importance Sampling for Stochastic Simulations," Management Science, INFORMS, vol. 35(11), pages 1367-1392, November.
    3. 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. 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.
    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. 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.
    4. Vivek Borkar & Jerzy Filar, 2013. "Markov chains, Hamiltonian cycles and volumes of convex bodies," Journal of Global Optimization, Springer, vol. 55(3), pages 633-639, March.
    5. 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.

    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. 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.
    2. Barry L. Nelson, 2004. "50th Anniversary Article: Stochastic Simulation Research in Management Science," Management Science, INFORMS, vol. 50(7), pages 855-868, July.
    3. 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.
    4. Cheng-Der Fuh & Yanwei Jia & Steven Kou, 2023. "A General Framework for Importance Sampling with Latent Markov Processes," Papers 2311.12330, arXiv.org.
    5. 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.
    6. 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.
    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. 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.
    9. 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.
    10. 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.
    11. Samet, Haidar & Khorshidsavar, Morteza, 2018. "Analytic time series load flow," Renewable and Sustainable Energy Reviews, Elsevier, vol. 82(P3), pages 3886-3899.
    12. Shane G. Henderson & Peter W. Glynn, 1999. "Derandomizing Variance Estimators," Operations Research, INFORMS, vol. 47(6), pages 907-916, December.
    13. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    14. 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.
    15. 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.
    16. Mulvey, John M. & Rosenbaum, Daniel P. & Shetty, Bala, 1999. "Parameter estimation in stochastic scenario generation systems," European Journal of Operational Research, Elsevier, vol. 118(3), pages 563-577, November.
    17. Bosetti, Valentina & Marangoni, Giacomo & Borgonovo, Emanuele & Diaz Anadon, Laura & Barron, Robert & McJeon, Haewon C. & Politis, Savvas & Friley, Paul, 2015. "Sensitivity to energy technology costs: A multi-model comparison analysis," Energy Policy, Elsevier, vol. 80(C), pages 244-263.
    18. 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.
    19. Dantzig, George B. & Infanger, Gerd, 1997. "Intelligent control and optimization under uncertainty with application to hydro power," European Journal of Operational Research, Elsevier, vol. 97(2), pages 396-407, March.
    20. Basrak, Bojan & Conroy, Michael & Olvera-Cravioto, Mariana & Palmowski, Zbigniew, 2022. "Importance sampling for maxima on trees," Stochastic Processes and their Applications, Elsevier, vol. 148(C), pages 139-179.

    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:oropre:v:54:y:2006:i:3:p:489-504. 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: 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.