Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-27T22:18:28.554Z Has data issue: false hasContentIssue false
  • English
  • Français

Simulating the Invariant Measures of Markov Chains Using Backward Coupling at Regeneration Times

Published online by Cambridge University Press:  27 July 2009

S. G. Foss ,
R. L. Tweedie  and
J. N. Corcoran
S. G. Foss
Affiliation:
Institute of Mathematics, 630090 Novosibirsk, Russia
R. L. Tweedie
Affiliation:
Department of Statistics, Colorado State University, Fort Collins, Colorado 80523
J. N. Corcoran
Affiliation:
Department of Statistics, Colorado State University, Fort Collins, Colorado 80523
Get access Rights & Permissions [Opens in a new window]

Abstract

We develop an algorithm for simulating approximate random samples from the invariant measure of a Markov chain using backward coupling of embedded regeneration times. Related methods have been used effectively for finite chains and for stochastically monotone chains: here we propose a method of implementation which avoids these restrictions by using a “cycle-length” truncation. We show that the coupling times have good theoretical properties and describe benefits and difficulties of implementing the methods in practice.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 12 , Issue 3 , July 1998 , pp. 303 - 320
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Borovkov, A.A. & Foss, S.G. (1992). Stochastically recursive sequences and their generalizations. Siberian Advances in Mathematics 2: 16–81.Google Scholar
2.Borovkov, A.A. & Foss, S.G. (1994). Two ergodicity criteria for stochastically recursive sequences. Acta Applicandae Mathematicae 34: 125–134.CrossRefGoogle Scholar
3.Down, D.G. & Meyn, S.P. Piecewise linear test functions for stability and instability of queueing networks. Queueing Systems(to appear).Google Scholar
4.Fill, J.A. (1998). An interruptible algorithm for perfect sampling via Markov chains. Annals of Applied Probability(to appear).CrossRefGoogle Scholar
5.Foss, S.G. (1983). On ergodicity conditions in multi-server queues. Siberian Mathematics Journal 24: 168–175.Google Scholar
6.Foss, S.G. & Tweedie, R.L. Perfect simulation and backward coupling. Stochastic Models(to appear preprint at http://www.stats.bris.ac.uk/MCMC/).Google Scholar
7.Häggström, O. & Nelander, K. (1997). Exact sampling from anti-monotone systems. Chalmers University of Technology Department of Mathematics Research Report 1997–03 (preprint at http://www.stats.bris.ac.uk/MCMC/).Google Scholar
8.Häggström, O., van Liesholt, M.N.M., & Møller, J. (1996). Characterisation results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes. Aalborg University Department of Mathematics Research Report R-96–2040 (to appear; preprint at http://www.stats.bris.ac.uk/MCMC/).Google Scholar
9.Kendall, W.S. (1996). Perfect simulation for the area-interaction point process. In Heyde, C.C. and Accardi, L. (eds.), Probability perspectives. Singapore: World Scientific Press.Google Scholar
10.Kifer, Ju. (1986). Ergodic theory of random transformations. Basel: Birkhauser.CrossRefGoogle Scholar
11.Lindvall, T. (1992). Lectures on the coupling method. New York: John Wiley & Sons.Google Scholar
12.Lund, R.B. & Tweedie, R.L. (1996). Geometric convergence rates for stochastically ordered Markov chains. Mathematics of Operations Research 21: 182–194.CrossRefGoogle Scholar
13.Lund, R.B. & Wilson, D.B. Perfect simulation of invariant measures in storage and network theory (in preparation).Google Scholar
14.Meyn, S.P. & Tweedie, R.L. (1993). Markov chains and stochastic stability. London: Springer-Verlag.CrossRefGoogle Scholar
15.Meyn, S.P. & Tweedie, R.L. (1994). Computable bounds for convergence rates of Markov chains. Annals of Applied Probability 4: 981–1011.CrossRefGoogle Scholar
16.Møller, J. (1997). Perfect simulation of conditionally specified models. Journal of the Royal Statistics Society, Series B (to appear; preprint at http://www.stats.bris.ac.uk/MCMC/).Google Scholar
17.Murdoch, D.J. & Green, P.J.Exact sampling from a continuous state space. Scandinavian Journal of Statistics (to appear; preprint at http://www.stats.bris.ac.uk/MCMC/).Google Scholar
18.Propp, J.G. & Wilson, D.B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9: 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
19.Rosenthal, J.S. (1995). Minorization conditions and convergence rates for Markov chain Monte Carlo. Journal of the American Statistics Association 90: 558–566.CrossRefGoogle Scholar
20.Scott, D.J. & Tweedie, R.L. (1996). Explicit rates of convergence of stochastically ordered Markov chains. InProceedings of the Athens Conference on Applied Probability and Time Series Analysis: Papers in Honour of J.M. Gani and E.J. Hannon. New York: Springer-Verlag, pp. 176–191.Google Scholar