×

Total variation cutoff in birth-and-death chains. (English) Zbl 1190.60005

The authors investigate the cutoff phenomenon for sequences of Markov chains where these chains exhibit sharp transitions in their convergence to their stationary distributions. It was observed recently by Y. Peres [“Sharp thresholds for mixing times”, in: American Institute of Mathematics (AIM) Research Workshop, Palo Alto; http://www.aimath.org/WWN/mixingtimes (2004)] that a necessary condition for cutoff phenomena for sequences of reversible chains is that the products of mixing-times and spectral gaps tend to infinity. Moreover, it was shown recently by P. Diaconis and L. Saloff-Coste [Ann. Appl. Probab. 16, No. 4, 2098–2122 (2006; Zbl 1127.60081)] that this condition is also sufficient for continuous-time birth-and-death chains starting in end points when convergence is measured in separation.
In the paper under review it is shown that the condition is also sufficient with respect to total variation distance for certain chains, namely for continuous-time birth-and-death chains as well as for socalled lazy discrete time birth-and-death chains where \(P(x,x)\geq1/2\) holds for all states \(x\). The main ingredient for the proof is a a sharp estimate for the difference for the mixing times \(t_{\text{mix}}(\varepsilon)-t_{\text{mix}}(1-\varepsilon)\) for \(\varepsilon\in]0,1/2[\) in terms of the product of the spectral gap and \(t_{\text{mix}}(1/4)\).

MSC:

60B10 Convergence of probability measures
60J27 Continuous-time Markov processes on discrete state spaces
60J05 Discrete-time Markov processes on general state spaces

Citations:

Zbl 1127.60081
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D., Random walks on finite groups and rapidly mixing Markov chains, Semin. Probab, XVII, 243-297 (1983) · Zbl 0514.60067
[2] Aldous, D.: Sharp thresholds for mixing times. In: American Institute of Mathematics (AIM) Research Workshop, Palo Alto, December 2004. Summary available at http://www.aimath.org/WWN/mixingtimes
[3] Aldous, D.; Diaconis, P., Shuffling cards and stopping times, Am. Math. Mon., 93, 333-348 (1986) · Zbl 0603.60006 · doi:10.2307/2323590
[4] Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs. In preparation. http://www.stat.berkeley.edu/ aldous/RWG/book.html
[5] Chen, G.-Y.: The cut-off phenomenon for finite Markov chains. Ph.D. Dissertation, Cornell University (2006)
[6] Chen, G.-Y.; Saloff-Coste, L., The cutoff phenomenon for ergodic Markov processes, Electron. J. Probab., 13, 26-78 (2008) · Zbl 1190.60007
[7] Diaconis, P., The cutoff phenomenon in finite Markov chains, Proc. Natl. Acad. Sci. USA, 93, 4, 1659-1664 (1996) · Zbl 0849.60070 · doi:10.1073/pnas.93.4.1659
[8] Diaconis, P.; Fill, J. A., Strong stationary times via a new form of duality, Ann. Probab., 18, 4, 1483-1522 (1990) · Zbl 0723.60083 · doi:10.1214/aop/1176990628
[9] Diaconis, P., Miclo, L.: On times to quasi-stationarity for birth and death processes. Preprint · Zbl 1186.60086
[10] Diaconis, P.; Saloff-Coste, L., Separation cut-offs for birth and death chains, Ann. Appl. Probab., 16, 4, 2098-2122 (2006) · Zbl 1127.60081 · doi:10.1214/105051606000000501
[11] Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Geb., 57, 2, 159-179 (1981) · Zbl 0485.60006 · doi:10.1007/BF00535487
[12] Ding, J., Lubetzky, E., Peres, Y.: The mixing time evolution of Glauber dynamics for the mean-field Ising Model. Preprint · Zbl 1173.82018
[13] Fill, J.A.: The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof. Preprint · Zbl 1178.60054
[14] Fill, J.A.: On hitting times and fastest strong stationary times for skip-free chains. Preprint · Zbl 1173.60337
[15] Goldstein, S., Maximal coupling, Z. Wahrsch. Verw. Geb., 46, 2, 193-204 (1978) · Zbl 0398.60097 · doi:10.1007/BF00533259
[16] Griffeath, D., A maximal coupling for Markov chains, Z. Wahrsch. Verw. Geb., 31, 95-106 (1975) · Zbl 0301.60043 · doi:10.1007/BF00539434
[17] Halmos, P. R., Finite-Dimensional Vector Spaces (1974), New York: Springer, New York · Zbl 0288.15002
[18] Karlin, S.; McGregor, J., Coincidence properties of birth and death processes, Pac. J. Math., 9, 1109-1140 (1959) · Zbl 0097.34102
[19] Keilson, J.: Markov chain models—rarity and exponentiality. In: Applied Mathematical Sciences, vol. 28. Springer, New York (1979) · Zbl 0411.60068
[20] Levin, D.A., Luczak, M., Peres, Y.: Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probab. Theory Relat. Fields (2008, to appear) · Zbl 1187.82076
[21] Levin, D.A., Peres, Y., Wilmer, E.: Markov chains and mixing times. In preparation (2007)
[22] Lindvall, T.: Lectures on the coupling method. In: Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics (A Wiley-Interscience Publication). Wiley, New York (1992) · Zbl 0850.60019
[23] Pitman, J. W., On coupling of Markov chains, Z. Wahrsch. Verw. Geb., 35, 4, 315-322 (1976) · Zbl 0356.60003 · doi:10.1007/BF00532957
[24] Peres, Y.: Sharp thresholds for mixing times. In: American Institute of Mathematics (AIM) Research Workshop, Palo Alto, December 2004. Summary available at http://www.aimath.org/WWN/mixingtimes
[25] Saloff-Coste, L.: Random walks on finite groups. Probab. Discrete Struct., pp. 263-346 (2004) · Zbl 1049.60006
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.