×

Cutoff for samples of Markov chains. (English) Zbl 0932.60077

Summary: We study the convergence to equilibrium of \(n\)-samples of independent Markov chains 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 the sense that as \(n\) tends to infinity, the total variation distance between the distribution of the chain and the asymptotic distribution tends to 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.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J27 Continuous-time Markov processes on discrete state spaces

Software:

Gibbsit
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] R. Bellman, Introduction to matrix analysis. McGraw-Hill, London ( 1960). Zbl0124.01001 MR122820 · Zbl 0124.01001
[2] N. Bouleau and D. Lépingle, Numerical methods for stochastic processes. Wiley, New York ( 1994). Zbl0822.60003 MR1274043 · Zbl 0822.60003
[3] E. Çinlar, Introduction to stochastic processes. Prentice Hall, New York ( 1975). Zbl0341.60019 MR380912 · Zbl 0341.60019
[4] P. Diaconis, The cutoff phenomenon in finite Markov chains. Proc. Natl. Acad. Sci. USA 93 ( 1996) 1659-1664. Zbl0849.60070 MR1374011 · Zbl 0849.60070 · doi:10.1073/pnas.93.4.1659
[5] P. Diaconis, R. Graham and J. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions. Rand. Struct. Algorithms 1 ( 1990) 51-72. Zbl0723.60085 MR1068491 · Zbl 0723.60085 · doi:10.1002/rsa.3240010105
[6] P. Diaconis and M. Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal. 18 ( 1987) 208-218. Zbl0617.60009 MR871832 · Zbl 0617.60009 · doi:10.1137/0518016
[7] P. Doukhan, Mixing, properties and examples. Springer-Verlag, New York, Lecture Notes en Statist. 85 ( 1994). Zbl0801.60027 MR1312160 · Zbl 0801.60027
[8] W. Feller, An introduction to probability theory and its applications, Vol. I. Wiley, London ( 1968). Zbl0155.23101 MR228020 · Zbl 0155.23101
[9] G.S. Fishman, Monte-Carlo concepts algorithms and applications. Springer-Verlag, New York ( 1996). Zbl0859.65001 MR1392474 · Zbl 0859.65001
[10] 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. Zbl0882.62040 MR1490044 · Zbl 0882.62040
[11] J. Keilson, Markov chain models - rarity and exponentiality. Springer-Verlag, New York. Appl. Math. Sci. 28 ( 1979). Zbl0411.60068 MR528293 · Zbl 0411.60068
[12] A.W. Massey, Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Research 12 ( 1987) 350-367. Zbl0622.60098 MR888982 · Zbl 0622.60098 · doi:10.1287/moor.12.2.350
[13] P. Mathé, Relaxation of product Markov chains on product spaces. Preprint WIAS, Berlin ( 1997). MR1646105
[14] 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. Zbl0844.62101 MR1397966 · Zbl 0844.62101
[15] C.P. Robert, Méthodes de Monte-Carlo par chaînes de Markov. Economica, Paris ( 1996). Zbl0917.60007 MR1419096 · Zbl 0917.60007
[16] L. Saloff-Coste, Lectures on finite Markov chains, P. Bernard, Ed., Ecole d’été de probabilités de Saint-Flour XXVI, Springer-Verlag, New York, Lecture Notes in Math. 1664 ( 1997) 301-413. Zbl0885.60061 MR1490046 · Zbl 0885.60061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.