×

zbMATH — the first resource for mathematics

Separation cut-offs for birth and death chains. (English) Zbl 1127.60081
Summary: This paper gives a necessary and sufficient condition for a sequence of birth and death chains to converge abruptly to stationarity, that is, to present a cut-off. The condition involves the notions of spectral gap and mixing time. Y. Peres has observed that for many families of Markov chains, there is a cut-off if and only if the product of spectral gap and mixing time tends to infinity. We establish this for arbitrary birth and death chains in continuous time when the convergence is measured in separation and the chains all start at 0.

MSC:
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60B10 Convergence of probability measures
60J05 Discrete-time Markov processes on general state spaces
60J27 Continuous-time Markov processes on discrete state spaces
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. Seminar on Probability XVII . Lecture Notes in Math . 986 243–297. Springer, Berlin. · Zbl 0514.60067 · numdam:SPS_1983__17__243_0 · eudml:113445
[2] Aldous, D. and Diaconis, P. (1986). Shuffling cards and stopping times. Amer. Math. Monthly 93 333–348. JSTOR: · Zbl 0603.60006 · doi:10.2307/2323590 · links.jstor.org
[3] Aldous, D. and Diaconis, P. (1986). Strong uniform times and finite random walks. Adv. in Appl. Math. 8 69–97. · Zbl 0631.60065 · doi:10.1016/0196-8858(87)90006-6
[4] Aldous, D. and Fill, J. Reversible Markov Chains and Random Walks on Graphs . Book project. Available at http://www.stat.berkeley.edu/users/aldous/RWG/book.html.
[5] Bannai, E. and Ito, T. (1987). Algebraic Combinatorics . I . Association Schemes . Benjamin, Menlo Park, CA. · Zbl 0555.05019
[6] Belsley, E. (1993). Rates of convergence of Markov chains related to association schemes. Ph.D. dissertation, Harvard Univ.
[7] Belsley, E. (1998). Rates of convergences of random walk on distance regular graphs. Probab. Theory Related Fields 112 493–533. · Zbl 0923.60010 · doi:10.1007/s004400050198
[8] Brown, M. and Shao, Y.-S. (1987). Identifying coefficients in the spectral representation for first passage time distributions. Probab. Engrg. Inform. Sci. 1 69–74. · Zbl 1133.60342 · doi:10.1017/S0269964800000309
[9] Brouwer, A. E., Cohen, A. M. and Neumaier, A. (1989). Distance-Regular Graphs . Springer, Berlin. · Zbl 0747.05073
[10] Chen, G.-Y. (2006). The cut-off phenomenon for finite Markov chains. Ph.D. dissertation, Cornell Univ.
[11] Chen, G.-Y. and Saloff-Coste, L. (2006). \(L^p\) cut-offs for finite Markov chains.
[12] Curtiss, J. H. (1942). A note on the theory of moment generating functions. Ann. Math. Statist. 13 430–433. · Zbl 0063.01024 · doi:10.1214/aoms/1177731541
[13] D’Aristotle, A. (1993). The nearest neighbor random walk on subspaces of a vector space and rate of convergence. J. Theoret. Probab. 8 321–346. · Zbl 0818.60061 · doi:10.1007/BF02212882
[14] Diaconis, P. (1988). Group Representations in Probability and Statistics . IMS, Hayward, CA. · Zbl 0695.60012
[15] Diaconis, P. (1996). The cutoff phenomenon in finite Markov chains. Proc. Natl. Acad. Sci. USA 93 1659–1664. JSTOR: · Zbl 0849.60070 · doi:10.1073/pnas.93.4.1659 · links.jstor.org
[16] Diaconis, P. and Fill, J. (1990). Strong stationary times via a new form of duality. Ann. Probab. 18 1483–1522. · Zbl 0723.60083 · doi:10.1214/aop/1176990628
[17] Diaconis, P. and Hanlon, P. (1992). Eigen analysis for some examples of the Metropolis algorithm. In Hypergeometric Functions on Domains of Positivity , Jack Polynomials , and Applications 99–117. Amer. Math. Soc., Providence RI. · Zbl 0789.05091
[18] Diaconis, P. and Ram, A. (2000). Analysis of systematic scan Metropolis algorithms using Iwahori–Hecke algebra techniques. Michigan Math. J. 48 157–189. · Zbl 0998.60069 · doi:10.1307/mmj/1030132713
[19] Diaconis, P. and Saloff-Coste, L. (1993). Comparison techniques for random walk on finite groups. Ann. Probab. 21 2131–2156. · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[20] Diaconis, P. and Saloff-Coste, L. (1998). What do we know about the Metropolis algorithm? In 27th Annual ACM Symposium on the Theory of Computing ( STOC ’ 95 ) ( Las Vegas , NV ). J. Comput. System Sci. 57 20–36. · Zbl 0920.68054 · doi:10.1006/jcss.1998.1576
[21] Diaconis, P. and Saloff-Coste, L. (1996). Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695–750. · Zbl 0867.60043 · doi:10.1214/aoap/1034968224
[22] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159–179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[23] Diaconis, P. and Shahshahani, M. (1987). Time to reach stationarity in the Bernoulli–Laplace diffusion model. SIAM J. Math. Anal. 18 208–218. · Zbl 0617.60009 · doi:10.1137/0518016
[24] Feller, W. (1971). An Introduction to Probability Theory and Its Applications. II , 2nd ed. Wiley, New York. · Zbl 0219.60003
[25] Fill, J. (1992). Strong stationary duality for continuous-time Markov chains. I. Theory. J. Theoret. Probab. 5 45–70. · Zbl 0746.60075 · doi:10.1007/BF01046778
[26] Ismail, M., Masson, D., Letessier, J. and Valent, G. (1990). Birth and death processes and orthogonal polynomials. In Orthogonal Polynomials ( Columbus , OH , 1989) 229–255. NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 294 . Kluwer Acad. Publ., Dordrecht. · Zbl 0704.60084
[27] Karlin, S. and McGregor, J. (1961). The Hahn polynomials, formulas and and application. Scripta Math . 26 33–46. · Zbl 0104.29103
[28] Karlin, S. and McGregor, J. (1965). Ehrenfest urn models. J. Appl. Probab. 2 352–376. JSTOR: · Zbl 0143.40501 · doi:10.2307/3212199 · links.jstor.org
[29] Keilson, J. (1979). Markov Chain Models—Rarity and Exponentiality . Springer, New York. · Zbl 0411.60068
[30] Lovász, L. and Winkler, P. (1998). Mixing times. In Microsurveys in Discrete Probability 85–133. Amer. Math. Soc., Providence RI. · Zbl 0908.60065
[31] Pak, I. and Van Vu, H. (2001). On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes. Discrete Appl. Math. 110 251–272. · Zbl 0983.60036 · doi:10.1016/S0166-218X(00)00201-8
[32] Parthasarathy, P. R. and Lenin, R. B. (1997). On the exact transient solution of finite birth and death processes with specific quadratic rates. Math. Sci. 22 92–105. · Zbl 0898.60084
[33] Parthasarathy, P. R. and Lenin, R. B. (1999). An inverse problem in birth and death processes. Comput. Math. Appl. 38 33–40. · Zbl 0938.60089 · doi:10.1016/S0898-1221(99)00166-2
[34] Saloff-Coste, L. (1997). Lectures on finite Markov chains. Lectures on Probability Theory and Statistics 301–413. Lecture Notes in Math. 1665 301–413. Springer, Berlin. · Zbl 0885.60061 · doi:10.1007/BFb0092621
[35] Steutel, F. W. and van Harn, K. (2000). Infinite Divisibility of Probability Distributions on the Real Line . Dekker, New York. · Zbl 1063.60001
[36] Van Assche, W., Parthasarathy, P. R. and Lenin, R. B. (1999). Spectral representation of four finite birth and death processes. Math. Sci. 24 105–112. · Zbl 0971.60085
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.