The Library

Perfect simulation for a class of positive recurrent Markov chains

Tools

Connor, Stephen B. and Kendall, Wilfrid S.. (2007) Perfect simulation for a class of positive recurrent Markov chains. Annals of Applied Probability, Vol.17 (No.3). pp. 781-808. ISSN 1050-5164

Preview

PDF
WRAP_Kendall_ConnorKendall-2007a.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (381Kb)

Official URL: http://dx.doi.org/10.1214/105051607000000032

Abstract

This paper generalizes the work of Kendall [Electron. Comm. Probab. 9 (2004) 140-15 11, which showed that perfect simulation, in the form of dominated coupling from the past, is always possible (although not necessarily practical) for geometrically ergodic Markov chains. Here, we consider the more general situation of positive recurrent chains and explore when it is possible to produce such a simulation algorithm for these chains. We introduce a class of chains which we name tame, for which we show that perfect simulation is possible.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Ergodic theory, Markov processes
Journal or Publication Title:	Annals of Applied Probability
Publisher:	Institute of Mathematical Statistics
ISSN:	1050-5164
Date:	June 2007
Volume:	Vol.17
Number:	No.3
Number of Pages:	28
Page Range:	pp. 781-808
Identification Number:	10.1214/105051607000000032
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
References:	[1] BURDZY, K. and KENDALL, W. S. (2000). Efficient Markovian couplings: Examples and counterexamples. Ann. Appl. Probab. 10 362–409. MR1768241 [2] CONNOR, S. (2007). Coupling: Cutoffs, CFTP and tameness. Ph.D. thesis, Univ. Warwick. [3] CONNOR, S. and KENDALL, W. S. (2006). Perfect simulation for a class of positive recurrent Markov chains. Research Report 446, Univ. Warwick, UK. [4] DOUC, R., FORT, G.,MOULINES, E. and SOULIER, P. (2002). Computable bounds for subgeometric ergodicity. Technical Report 186, Equipe d’Analyse et Probabilités, Univ. d’Évry. [5] DOUC, R., FORT, G., MOULINES, E. and SOULIER, P. (2004). Practical drift conditions for subgeometric rates of convergence. Ann. Appl. Probab. 14 1353–1377. MR2071426 [6] FORT, G. and MOULINES, E. (2000). V -subgeometric ergodicity for a Hastings–Metropolis algorithm. Statist. Probab. Lett. 49 401–410. MR1796485 [7] FOSS, S. G. and TWEEDIE, R. L. (1998). Perfect simulation and backward coupling. Stochastic Models 14 187–203. MR1617572 [8] FOSTER, F. G. (1953). On the stochastic matrices associated with certain queuing processes. Ann. Math. Statist. 24 355–360. MR0056232 [9] GREEN, P. J. and MURDOCH, D. J. (1999). Exact sampling for Bayesian inference: Towards general purpose algorithms (with discussion). In Bayesian Statistics 6 (J. Bernardo, J. Berger, A. Dawid, and A. Smith, eds.) 301–321. The Clarendon Press, Oxford Univ. Press. Presented as an invited paper at the 6th Valencia InternationalMeeting on Bayesian Statistics, Alcossebre, Spain, June 1998. MR1723502 [10] GRIMMETT, G. R. and STIRZAKER, D. R. (2001). Probability and Random Processes, 2nd ed. Oxford Univ. Press. MR2059709 [11] JARNER, S. F. and ROBERTS, G. O. (2002). Polynomial convergence rates of Markov chains. Ann. Appl. Probab. 12 224–247. MR1890063 [12] JERRUM, M. (2003). Counting, sampling and integrating: Algorithms and complexity. Lectures in Mathematics ETH Zürich. Birkhäuser, Basel. MR1960003 [13] KENDALL, W. S. (1998). Perfect simulation for the area-interaction point process. In Probability Towards 2000 (L. Accardi and C. Heyde, eds.) 218–234. Springer, New York. MR1632588 [14] KENDALL, W. S. (2004). Geometric ergodicity and perfect simulation. Electron. Comm. Probab. 9 140–151. MR2108860 [15] KENDALL, W. S., LIANG, F. and WANG, J.-S., eds. (2005). Markov Chain Monte Carlo: Innovations and Applications. World Scientific, Hackensack, NJ. MR2238833 [16] KENDALL, W. S. andMØLLER, J. (2000). Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. in Appl. Probab. 32 844–865. MR1788098 [17] LINDVALL, T. (1992). Lectures on the Coupling Method. Wiley, New York. MR1180522 [18] MEYN, S. and TWEEDIE, R. (1993). Markov Chains and Stochastic Stability. Springer, London. MR1287609 [19] MOUNTFORD, T. S. and CRANSTON, M. (2000). Efficient coupling on the circle. In Game Theory, Optimal Stopping, Probability and Statistics. IMS Lecture Notes Monogr. Ser. 35 191–203. IMS, Beachwood, OH. MR1833860 [20] PROPP, J. G. and WILSON, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9 223–252. MR1611693 [21] ROBERT, C. P. and CASELLA, G. (2004). Monte Carlo Statistical Methods. Springer, New York. MR2080278 [22] ROBERTS, G. O. and ROSENTHAL, J. S. (2001). Small and pseudo-small sets for Markov chains. Stoch. Models 17 121–145. MR1853437 [23] TUOMINEN, P. and TWEEDIE, R. L. (1994). Subgeometric rates of convergence of f -ergodic Markov chains. Adv. in Appl. Probab. 26 775–798. MR1285459
URI:	http://wrap.warwick.ac.uk/id/eprint/31852