Explicit criteria on separation cutoff for birth and death chains

Abstract

The criteria on separation cutoff for birth and death chains were obtained by Diaconis and Saloff-Coste in 2006. These criteria are involving all eigenvalues. In this paper, we obtain the explicit criterion, which depends only on the birth and death rates. Furthermore, we present two ways to estimate moments of the fastest strong stationary time and then give another but equivalent criterion explicitly.

Keywords

Separation cutoff / birth and death chain / hitting time / fastest strong stationary time (FSST) / eigenvalue / stochastic monotonicity / duality / boundary theory

References

[1] Aldous D, Diaconis P. Strong uniform times and finite random walks. Adv in Appl Math, 1987, 8(1): 69-97

[2] Aldous D, Fill J A. Reversible Markov Chains and Random Walks on Graphs. 2003

[3] Billingsley P. Probability and Measures. 3rd ed. New York: Wiley, 1995

[4] Chen M F. From Markov Chains to Non-Equilibrium Particle Systems. 2nd ed. Singapore: World Scientific, 2004

[5] Chen M F. Speed of stability for birth-death processes. Front Math China, 2010, 5(3): 379-515

[6] Diaconis P. The cutoff phenomenon in finite Markov chains. Proc Natl Acad Sci USA, 1996, 93(4): 1659-1664

[7] Diaconis P, Fill J A. Strong stationary times via a new form of duality. Ann Probab, 1990, 18: 1483-1522

[8] Diaconis P, Saloff-Coste L. What do we know about the Metropolis algorithm. J Comput System Sci, 1998, 57: 20-36

[9] Diaconis P, Saloff-Coste L. Separation cut-offs for birth and death chains. Ann Appl Probab, 2006, 16(4): 2098-2122

[10] Feller W. An Introduction to Probability Theory and Its Applications, II. 2nd ed. New York: Wiley, 1971

[11] Fill J A. Strong stationary duality for continuous-time Markov chains, Part I: theory. J Theoret Probab, 1992, 5(1): 45-69

[12] Gong Y, Mao Y H, Zhang C. Hitting time distribution for a denumerable birth-death process. J Theoret Probab, 2012, 25: 950-980

[13] Levin D A, Peres Y, Wilmer E L. Markov Chains and Mixing Times.Providence: Amer Math Sos, 2008

[14] Mao Y H. Algebraic convergence for discrete-time ergodic Markov chains. Science in China (Series A), 2003, 46(5): 621-630

[15] Mao Y H. Ergodic degrees for continuous-time Markov chains. Sci China Ser A, 2004, 47(2): 161-174

[16] Mao Y H. The eigentime identity for ergodic Markov chains. J Appl Probab, 2004, 41(4): 1071-1080

[17] Mao Y H. Convergence rates for reversible Markov chains without the assumption of nonnegative definite matrices. Sci China Math, 2010, 53(8): 1979-1988

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg