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

Fakhouri H. and Nasroallah A.
Additional contact information
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

Monte Carlo Methods and Applications, 2009, vol. 15, issue 2, 91-105

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.

Keywords: Monte Carlo; simulation; Markov chain; steady-state distribution; coupling from the past; importance sampling (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1515/MCMA.2009.005 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:15:y:2009:i:2:p:91-105:n:1

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/MCMA.2009.005

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().