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

Official Date:

June 2007

Dates:

Date	Event
June 2007	Published

Volume:

Vol.17

Number:

No.3

Number of Pages:

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