 |
|
|
| | | | | |
|
|
|
|
|
Geometric Ergodicity and Perfect Simulation
|
Wilfrid S. Kendall, University of Warwick
|
Abstract
This note extends the work of Foss and Tweedie (1998), who showed
that availability of the classic Coupling from the Past (CFTP) algorithm of
Propp and Wilson (1996) is essentially equivalent to uniform
ergodicity for a Markov chain (see also Hobert and Robert, 2004).
In this note we show that all geometrically ergodic chains possess
dominated CFTP algorithms (not necessarily
practical!) which are rather closely connected to Foster-Lyapunov
criteria. Hence geometric ergodicity implies dominated CFTP.
|
Full text: PDF
Pages: 140-151
Published on: October 26, 2004
|
Bibliography
| Burdzy, K.; Kendall, W. S. Efficient Markovian couplings: examples and counterexamples.
Ann. Appl. Probab. 10 (2000), no. 2, 362--409. MR1768241 (2002b:60129) |
| Cai, Y.; Kendall, W. S. Perfect simulation for correlated Poisson random variables conditioned to be positive.
Stat. Comput. 12 (2002), no. 3, 229--243. MR1933509 |
| Corcoran, J. N.; Tweedie, R. L. Perfect sampling of ergodic Harris chains.
Ann. Appl. Probab. 11 (2001), no. 2, 438--451. MR1843053 (2002g:60111) |
| Foss, S. G.; Tweedie, R. L. Perfect simulation and backward coupling.
Special issue in honor of Marcel F. Neuts.
Comm. Statist. Stochastic Models 14 (1998), no. 1-2, 187--203. MR1617572 (99f:60123) |
| Goldstein, S. Maximal coupling.
Z. Wahrsch. Verw. Gebiete 46 (1978/79), no. 2, 193--204. MR0516740 (80k:60041) |
| Griffeath, D. A maximal coupling for Markov chains.
Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 31 (1974/75), 95--106. MR0370771 (51 #6996) |
| Grimmett, G. R.; Stirzaker, D. R. Probability and random processes.
Second edition.
The Clarendon Press, Oxford University Press, New York, 1992. xii+541 pp. ISBN: 0-19-853666-6; 0-19-853665-8 MR1199812 (93m:60002) |
| Hayes, T.; Vigoda, E.
A non-Markovian coupling for randomly sampling colorings.
Preprint, University of Chicago Department of Computer
Science (2003).
Link
to PDF file
|
| Hobert, J. P.; Robert, C. P. A mixture representation of $pi$ with applications in Markov chain Monte Carlo and perfect sampling.
Ann. Appl. Probab. 14 (2004), no. 3, 1295--1305. MR2071424 |
| Huber, M.
Time dependent update functions for perfect sampling.
Conference presentation at IMS meeting on Monte Carlo Markov
chain methods in Singapore (March, 2004).
|
| Kendall, W. S. Perfect simulation for the area-interaction point process.
Probability towards 2000 (New York, 1995),
218--234, Lecture Notes in Statist., 128, Springer, New York, 1998. MR1632588 (99e:62144) |
| Kendall, W. S.; Møller, J. Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes.
Adv. in Appl. Probab. 32 (2000), no. 3, 844--865. MR1788098 (2001h:62176) |
| Meyn, S. P.; Tweedie, R. L. Markov chains and stochastic stability.
Communications and Control Engineering Series. Springer-Verlag London, Ltd., London, 1993. xvi+ 548 pp. ISBN: 3-540-19832-6 MR1287609 (95j:60103) |
| Murdoch, D. J.; Green, P. J. Exact sampling from a continuous state space.
Scand. J. Statist. 25 (1998), no. 3, 483--502. MR1650023 |
| Nummelin, E. A splitting technique for Harris recurrent Markov chains.
Z. Wahrsch. Verw. Gebiete 43 (1978), no. 4, 309--318. MR0501353 (58 #18732) |
| Propp, J. G.; Wilson,
D. B. Exact sampling with coupled Markov chains and applications to statistical mechanics.
Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995).
Random Structures Algorithms 9 (1996), no. 1-2, 223--252. MR1611693 (99k:60176) |
| Roberts, G. O.; Rosenthal, J. S. Small and pseudo-small sets for Markov chains.
Stoch. Models 17 (2001), no. 2, 121--145. MR1853437 (2002f:60136) |
| Roberts, G. O.; Rosenthal, J. S. One-shot coupling for certain stochastic recursive sequences.
Stochastic Process. Appl. 99 (2002), no. 2, 195--208. MR1901153 (2003d:60136) |
| Rosenthal, J. S. Quantitative convergence rates of Markov chains: a simple account.
Electron. Comm. Probab. 7 (2002), 123--128 (electronic). MR1917546 (2003m:60188) |
| Wilson, D. B. How to couple from the past using a read-once source of randomness.
Random Structures Algorithms 16 (2000), no. 1, 85--113. MR1728354 (2000h:65025) |
| Wilson, D. B. Layered multishift coupling for use in perfect sampling algorithms (with a primer on CFTP).
Monte Carlo methods (Toronto, ON, 1998),
143--179, Fields Inst. Commun., 26, Amer. Math. Soc., Providence, RI, 2000. MR1772313 (2001h:65014) |
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context