IDEAS home Printed from https://ideas.repec.org/a/bpj/mcmeap/v15y2009i2p91-105n1.html
   My bibliography  Save this article

On the simulation of Markov chain steady-state distribution using CFTP algorithm

Author

Listed:
  • Fakhouri H.

    (Department of Mathematics, Cadi Ayyad University, Faculty of Sciences Semlalia, B.P. 2390, Marrakesh, Morocco. Email: h.fakhouri@ucam.ac.ma)

  • Nasroallah A.

    (Department of Mathematics, Cadi Ayyad University, Faculty of Sciences Semlalia, B.P. 2390, Marrakesh, Morocco. Email: nasroallah@ucam.ac.ma)

Abstract

The famous Propp and Wilson (Random Structures and Algorithms 9: 223–252, 1996, Journal of the American Statistical Association 90: 558–566, 1998) protocol called coupling from the past (CFTP) allows exact sampling from steady-state distribution of a Markov chain. When the Markov chain is stiff (i.e. existence of rarely visited states), CFTP spends a prohibitive time to reach stationarity. To reduce this time we propose to combine the variance reduction technique Importance Sampling (IS) with CFTP. Also we propose another technique, based on the power of the Markov chain kernel, to reduce the CFTP simulation time in standard case. When the period δ of the simulated Markov chain is greater than one (δ > 1), the stopping condition of CFTP is not satisfied. To break the deadlock of CFTP in this case, we propose to transform the studied chain on δ subchains that are aperiodic and for which CFTP can be applied. Some numerical examples are presented to bring the utility of the proposed simulation techniques.

Suggested Citation

  • 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.
    • Handle: RePEc:bpj:mcmeap:v:15:y:2009:i:2:p:91-105:n:1
    DOI: 10.1515/MCMA.2009.005
    as

    Download full text from publisher

    File URL: https://doi.org/10.1515/MCMA.2009.005
    Download Restriction: For access to full text, subscription to the journal or payment for the individual article is required.
    File URL: https://libkey.io/10.1515/MCMA.2009.005?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. A. Mira & J. Møller & G. O. Roberts, 2001. "Perfect slice samplers," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 63(3), pages 593-606.
    2. G. Casella & K. L. Mengersen & C. P. Robert & D. M. Titterington, 2002. "Perfect samplers for mixtures of distributions," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 64(4), pages 777-790, October.
    3. Peter W. Glynn & Donald L. Iglehart, 1989. "Importance Sampling for Stochastic Simulations," Management Science, INFORMS, vol. 35(11), pages 1367-1392, November.
    4. 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. Nasroallah Abdelaziz & Bounnite Mohamed Yasser, 2019. "A kind of dual form for coupling from the past algorithm, to sample from Markov chain steady-state probability," Monte Carlo Methods and Applications, De Gruyter, vol. 25(4), pages 317-327, December.
    2. Bounnite Mohamed Yasser & Nasroallah Abdelaziz, 2015. "Widening and clustering techniques allowing the use of monotone CFTP algorithm," Monte Carlo Methods and Applications, De Gruyter, vol. 21(4), pages 301-312, December.

    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. Bounnite Mohamed Yasser & Nasroallah Abdelaziz, 2015. "Widening and clustering techniques allowing the use of monotone CFTP algorithm," Monte Carlo Methods and Applications, De Gruyter, vol. 21(4), pages 301-312, December.
    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. 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.
    4. Nasroallah Abdelaziz & Bounnite Mohamed Yasser, 2019. "A kind of dual form for coupling from the past algorithm, to sample from Markov chain steady-state probability," Monte Carlo Methods and Applications, De Gruyter, vol. 25(4), pages 317-327, December.
    5. Cheng-Der Fuh & Yanwei Jia & Steven Kou, 2023. "A General Framework for Importance Sampling with Latent Markov Processes," Papers 2311.12330, arXiv.org.
    6. 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.
    7. 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.
    8. 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.
    9. Marcin Kacperczyk & Paul Damien & Stephen G. Walker, 2013. "A new class of Bayesian semi-parametric models with applications to option pricing," Quantitative Finance, Taylor & Francis Journals, vol. 13(6), pages 967-980, May.
    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. Sandeep Juneja & Perwez Shahabuddin, 2001. "Fast Simulation of Markov Chains with Small Transition Probabilities," Management Science, INFORMS, vol. 47(4), pages 547-562, April.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Francesco Strino & Fabio Parisi & Yuval Kluger, 2011. "VDA, a Method of Choosing a Better Algorithm with Fewer Validations," PLOS ONE, Public Library of Science, vol. 6(10), pages 1-8, October.
    17. Xie, Junfei & Wan, Yan & Mills, Kevin & Filliben, James J. & Lei, Yu & Lin, Zongli, 2019. "M-PCM-OFFD: An effective output statistics estimation method for systems of high dimensional uncertainties subject to low-order parameter interactions," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 159(C), pages 93-118.
    18. Frikha Noufel & Sagna Abass, 2012. "Quantization based recursive importance sampling," Monte Carlo Methods and Applications, De Gruyter, vol. 18(4), pages 287-326, December.
    19. Steiner, Jakub & Jehiel, Philippe, 2017. "On Second Thoughts, Selective Memory, and Resulting Behavioral Biases," CEPR Discussion Papers 12546, C.E.P.R. Discussion Papers.
    20. Fodstad, Marte & Crespo del Granado, Pedro & Hellemo, Lars & Knudsen, Brage Rugstad & Pisciella, Paolo & Silvast, Antti & Bordin, Chiara & Schmidt, Sarah & Straus, Julian, 2022. "Next frontiers in energy system modelling: A review on challenges and the state of the art," Renewable and Sustainable Energy Reviews, Elsevier, vol. 160(C).

    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:bpj:mcmeap:v:15:y:2009:i:2:p:91-105:n:1. 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: Peter Golla (email available below). General contact details of provider: https://www.degruyter.com .

    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.