Cutoff for samples of Markov chains

Bernard Ycart

ESAIM: Probability and Statistics (2010)

  • Volume: 3, page 89-106
  • ISSN: 1292-8100

Abstract

top
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.

How to cite

top

Ycart, Bernard. "Cutoff for samples of Markov chains." ESAIM: Probability and Statistics 3 (2010): 89-106. <http://eudml.org/doc/197750>.

@article{Ycart2010,
abstract = { 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. },
author = {Ycart, Bernard},
journal = {ESAIM: Probability and Statistics},
keywords = {Independent Markov chains; cutoff; MCMC convergence.; independent Markov chains; MCMC convergence},
language = {eng},
month = {3},
pages = {89-106},
publisher = {EDP Sciences},
title = {Cutoff for samples of Markov chains},
url = {http://eudml.org/doc/197750},
volume = {3},
year = {2010},
}

TY - JOUR
AU - Ycart, Bernard
TI - Cutoff for samples of Markov chains
JO - ESAIM: Probability and Statistics
DA - 2010/3//
PB - EDP Sciences
VL - 3
SP - 89
EP - 106
AB - 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.
LA - eng
KW - Independent Markov chains; cutoff; MCMC convergence.; independent Markov chains; MCMC convergence
UR - http://eudml.org/doc/197750
ER -

References

top
  1. R. Bellman, Introduction to matrix analysis. McGraw-Hill, London (1960).  
  2. N. Bouleau and D. Lépingle, Numerical methods for stochastic processes. Wiley, New York (1994).  
  3. E. Çinlar, Introduction to stochastic processes. Prentice Hall, New York (1975).  
  4. P. Diaconis, The cutoff phenomenon in finite Markov chains. Proc. Natl. Acad. Sci. USA93 (1996) 1659-1664.  
  5. P. Diaconis, R. Graham and J. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions. Rand. Struct. Algorithms1 (1990) 51-72.  
  6. P. Diaconis and M. Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal.18 (1987) 208-218.  
  7. P. Doukhan, Mixing, properties and examples. Springer-Verlag, New York, Lecture Notes en Statist. 85 (1994).  
  8. W. Feller, An introduction to probability theory and its applications, Vol. I. Wiley, London (1968).  
  9. G.S. Fishman, Monte-Carlo concepts algorithms and applications. Springer-Verlag, New York (1996).  
  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.  
  11. J. Keilson, Markov chain models - rarity and exponentiality. Springer-Verlag, New York. Appl. Math. Sci. 28 (1979).  
  12. A.W. Massey, Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Research12 (1987) 350-367.  
  13. P. Mathé, Relaxation of product Markov chains on product spaces. Preprint WIAS, Berlin (1997).  
  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.  
  15. C.P. Robert, Méthodes de Monte-Carlo par chaînes de Markov. Economica, Paris (1996).  
  16. 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.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.