Convergence rates of Markov chains on spaces of partitions
Steven P. Lalley (University of Chicago)
Abstract
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
References
- 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
This work is licensed under a Creative Commons Attribution 3.0 License.