Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-04T19:43:05.890Z Has data issue: false hasContentIssue false
  • English
  • Français

Cutoff for samples of Markov chains

Published online by Cambridge University Press:  15 August 2002

Bernard Ycart
Bernard Ycart*
Affiliation:
LMC/IMAG, BP. 53, 38041 Grenoble Cedex 9, France; [email protected].
Get access

Abstract

We study the convergence to equilibrium of n-samples of independent Markovchains in discrete and continuous time. They are defined as Markov chains on the n-fold Cartesian product of the initial state space by itself, and they converge to the direct product of n copies of the initial stationary distribution. Sharp estimates for the convergence speed are given in terms of the spectrum of the initial chain. A cutoff phenomenon occurs in thesense that as n tends to infinity, the total variation distancebetween the distribution of the chain and the asymptotic distribution tendsto 1 or 0 at all times. As an application,an algorithm is proposed for producing an n-sample of the asymptotic distribution of the initial chain, with an explicit stopping test.

Keywords

Independent Markov chainscutoffMCMC convergence.
Type
Research Article
Information
ESAIM: Probability and Statistics , Volume 3 , 1999 , pp. 89 - 106
Copyright
© EDP Sciences, SMAI, 1999

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

R. Bellman, Introduction to matrix analysis. McGraw-Hill, London (1960).
N. Bouleau and D. Lépingle, Numerical methods for stochastic processes. Wiley, New York (1994).
E. Çinlar, Introduction to stochastic processes. Prentice Hall, New York (1975).
Diaconis, P., The cutoff phenomenon in finite Markov chains. Proc. Natl. Acad. Sci. USA 93 (1996) 1659-1664. CrossRef
Diaconis, P., Graham, R. and Morrison, J., Asymptotic analysis of a random walk on a hypercube with many dimensions. Rand. Struct. Algorithms 1 (1990) 51-72. CrossRef
Diaconis, P. and Shahshahani, M., Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal. 18 (1987) 208-218. CrossRef
P. Doukhan, Mixing, properties and examples. Springer-Verlag, New York, Lecture Notes en Statist. 85 (1994).
W. Feller, An introduction to probability theory and its applications, Vol. I. Wiley, London (1968).
G.S. Fishman, Monte-Carlo concepts algorithms and applications. Springer-Verlag, New York (1996).
E. Giné, Lectures on some aspects of the bootstrap, P. Bernard, Ed., École d'été de probabilités de Saint-Flour XXVI, Springer-Verlag, New York, Lectures Notes in Math. 1664 (1997) 37-151.
J. Keilson, Markov chain models - rarity and exponentiality. Springer-Verlag, New York. Appl. Math. Sci. 28 (1979).
Massey, A.W., Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Research 12 (1987) 350-367. CrossRef
P. Mathé, Relaxation of product Markov chains on product spaces. Preprint WIAS, Berlin (1997).
A.E. Raftery and S. Lewis, Implementing MCMC, W.R. Gilks, S.T. Richardson and D.J. Spiegelhalter, Eds., Markov Chain Monte-Carlo in practice, Chapman and Hall, London (1992) 115-130.
C.P. Robert, Méthodes de Monte-Carlo par chaînes de Markov. Economica, Paris (1996).
L. Saloff-Coste, Lectures on finite Markov chains, P. Bernard, Ed., École d'été de probabilités de Saint-Flour XXVI, Springer-Verlag, New York, Lecture Notes in Math. 1664 (1997) 301-413.