Convergence rates of Markov chains on spaces of partitions

Harry Crane (Rutgers University)
Steven P. Lalley (University of Chicago)


We study the convergence rate to stationarity for a class of exchangeable partition-valued Markov chains called cut-and-paste chains. The law governing the transitions of a cut-and-paste chain are determined by products of i.i.d. stochastic matrices, which describe the chain induced on the simplex by taking asymptotic frequencies.  Using this representation, we establish upper bounds for the mixing times of ergodic cut-and-paste chains, and under certain conditions on the distribution of the governing random matrices we show that the "cutoff phenomenon" holds.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-23

Publication Date: June 13, 2013

DOI: 10.1214/EJP.v18-2389


  • Bougerol, Philippe; Lacroix, Jean. Products of random matrices with applications to Schrödinger operators. Progress in Probability and Statistics, 8. Birkhäuser Boston, Inc., Boston, MA, 1985. xii+283 pp. ISBN: 0-8176-3324-3 MR0886674
  • Crane, Harry. A consistent Markov partition process generated from the paintbox process. J. Appl. Probab. 48 (2011), no. 3, 778--791. MR2884815
  • Harry Crane. Homogeneous cut-and-paste processes. Preprint, 2012.
  • Furstenberg, H.; Kesten, H. Products of random matrices. Ann. Math. Statist. 31 1960 457--469. MR0121828
  • Golʹdsheĭd, I. Ya.; Margulis, G. A. Lyapunov exponents of a product of random matrices. (Russian) Uspekhi Mat. Nauk 44 (1989), no. 5(269), 13--60; translation in Russian Math. Surveys 44 (1989), no. 5, 11--71 MR1040268
  • Golubitsky, Martin; Keeler, Emmett B.; Rothschild, Michael. Convergence of the age structure: applications of the projective metric. Theoret. Population Biology 7 (1975), 84--93. MR0371433
  • Karlin, Samuel; Taylor, Howard M. A first course in stochastic processes. Second edition. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1975. xvii+557 pp. MR0356197
  • Kingman, J. F. C. Subadditive ergodic theory. With discussion by D. L. Burkholder, Daryl Daley, H. Kesten, P. Ney, Frank Spitzer and J. M. Hammersley, and a reply by the author. Ann. Probability 1 (1973), 883--909. MR0356192
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937
  • Petersen, Karl. Ergodic theory. Cambridge Studies in Advanced Mathematics, 2. Cambridge University Press, Cambridge, 1983. xii+329 pp. ISBN: 0-521-23632-0 MR0833286

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.