Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 3 open journal systems 


The cutoff phenomenon for ergodic Markov processes

Guan-Yu Chen, Department of Applied Mathematics, National Chiao Tung University
Laurent Saloff-Coste, Department of Mathematics, Cornell University


Abstract
We consider the cutoff phenomenon in the context of families of ergodic Markov transition functions. This includes classical examples such as families of ergodic finite Markov chains and Brownian motion on families of compact Riemannian manifolds. We give criteria for the existence of a cutoff when convergence is measured in Lp-norm with 1<p<∞. This allows us to prove the existence of a cutoff in cases where the cutoff time is not explicitly known. In the reversible case, for 1<p<∞, we show that a necessary and sufficient condition for the existence of a max-Lp cutoff is that the product of the spectral gap by the max-Lp mixing time tends to infinity. This type of condition was suggested by Yuval Peres. Illustrative examples are discussed.


Full text: PDF

Pages: 26-78

Published on: January 20, 2008
Bibliography
  1. Aldous, David . Random walks on finite groups and rapidly mixing Markov chains. Seminar on probability, XVII, 243--297, Lecture Notes in Math., 986, Springer, Berlin, 1983. MR0770418 (86j:60156)
  2. Aldous, David ; Diaconis, Persi . Shuffling cards and stopping times. Amer. Math. Monthly 93 (1986), no. 5, 333--348. MR0841111 (88a:60021)
  3. Aldous, David ; Diaconis, Persi . Strong uniform times and finite random walks. Adv. in Appl. Math. 8 (1987), no. 1, 69--97. MR0876954 (88d:60175)
  4. Bayer, Dave ; Diaconis, Persi . Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2 (1992), no. 2, 294--313. MR1161056 (93d:60014)
  5. Brown, Mark ; Shao, Y.-S. Identifying coefficients in the spectral representation for first passage time distribution. Probab. Engrg. Inform. Sci, 1(1):69--74, 1987. Math. Review number not available.
  6. Chen, Guan-Yu. The cut-off phenomenon for finite Markov chains. PhD thesis, Cornell University, 2006.
  7. Chen, Guan-Yu ; Saloff-Coste, Laurent. The cut-off phenomenon for randomized riffle shuffles. To appear in Random Structures Algorithms.
  8. Diaconis, Persi. Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. MR0964069 (90a:60001)
  9. Diaconis., Persi . The cutoff phenomenon in finite Markov chains. Proc. Nat. Acad. Sci. U.S.A., 93(4):1659--1664, 1996. MR1374011(97b:60112)
  10. Diaconis, Persi ; Fill, James Allen ; Pitman, Jim . Analysis of top to random shuffles. Combin. Probab. Comput. 1 (1992), no. 2, 135--155. MR1179244 (93f:60011)
  11. Diaconis, Persi ; Saloff-Coste, Laurent . Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993), no. 4, 2131--2156. MR1245303 (95a:60009)
  12. Diaconis, Persi ; Saloff-Coste, Laurent . Separation cut-offs for birth and death chains. Ann. Appl. Probab. 16 (2006), no. 4, 2098--2122. MR2288715
  13. Diaconis, Persi ; Shahshahani, Mehrdad . Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159--179. MR0626813 (82h:60024)
  14. Dunford, Nelson ; Schwartz, Jacob. T. Linear operators. Part I. Wiley Classics Library. John Wiley & Sons Inc., New York, 1988. MR1009162 (90g:47001a)
  15. Feller, William . An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley & Sons Inc., New York, 1968. MR0228020 (37 #3604)
  16. Ismail, Mourad E. H. ; Masson, David R. ; Letessier, Jean ; Valent, Galliano . Birth and death processes and orthogonal polynomials. Orthogonal polynomials (Columbus, OH, 1989), 229--255, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 294, Kluwer Acad. Publ., Dordrecht, 1990. MR1100296 (93c:42021)
  17. Karlin, Samuel ; McGregor, James . Ehrenfest urn models. J. Appl. Probability 2 1965 352--376. MR0184284 (32 #1757)
  18. Karlin, Samuel ; McGregor, James L. The Hahn polynomials, formulas and an application. Scripta Math. 26 1961 33--46. MR0138806 (25 #2249)
  19. Keilson, Julian . Markov chain models---rarity and exponentiality. Applied Mathematical Sciences, 28. Springer-Verlag, New York-Berlin, 1979. xiii+184 pp. ISBN: 0-387-90405-0 MR0528293 (80f:60061)
  20. Miclo, L. An example of application of discrete Hardy's inequalities. Markov Process. Related Fields 5 (1999), no. 3, 319--330. MR1710983 (2000h:60081)
  21. Peres, Yuval ; Revelle, David . Mixing times for random walks on finite lamplighter groups. Electron. J. Probab. 9 (2004), no. 26, 825--845 (electronic). MR2110019 (2005m:60007)
  22. Porod, Ursula . The cut-off phenomenon for random reflections. Ann. Probab. 24 (1996), no. 1, 74--96. MR1387627 (97e:60012)
  23. Porod, U. The cut-off phenomenon for random reflections. II. Complex and quaternionic cases. Probab. Theory Related Fields 104 (1996), no. 2, 181--209. MR1373375 (97e:60013)
  24. Rosenthal, Jeffrey S. Random rotations: characters and random walks on ${rm SO}(N)$. Ann. Probab. 22 (1994), no. 1, 398--423. MR1258882 (95c:60008)
  25. Saloff-Coste, Laurent. Convergence to equilibrium and logarithmic Sobolev constant on manifolds with Ricci curvature bounded below. Colloq. Math. 67 (1994), no. 1, 109--121. MR1292948 (95g:58258)
  26. Saloff-Coste, L. Precise estimates on the rate at which certain diffusions tend to equilibrium. Math. Z. 217 (1994), no. 4, 641--677. MR1306030 (95m:60115)
  27. Saloff-Coste, L. On the convergence to equilibrium of Brownian motion on compact simple Lie groups. J. Geom. Anal. 14 (2004), no. 4, 715--733. MR2111426 (2005m:58081)
  28. Saloff-Coste, Laurent . Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), 301--413, Lecture Notes in Math., 1665, Springer, Berlin, 1997. MR1490046 (99b:60119)
  29. Saloff-Coste, Laurent . Random walks on finite groups. Probability on discrete structures, 263--346, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023654 (2004k:60133)
  30. Saloff-Coste, Laurent ; Woess, Wolfgang . Transition operators on co-compact $G$-spaces. Rev. Mat. Iberoamericana 22 (2006), no. 3, 747--799. MR2320401
  31. Van Assche, W. ; Parthasarathy, P. R. ; Lenin, R. B. Spectral representation of four finite birth and death processes. Math. Sci. 24 (1999), no. 2, 105--112. MR1746330 (2001c:60140)
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489