Mixing Time Bounds via the Spectral Profile

Sharad Goel (Standford University, USA)
Ravi Montenegro (University of Massachusetts Lowell, USA)
Prasad Tetali (Georgia Institute of Technology, USA)

Abstract


On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of finite Markov chains, proving upper and lower $L^{\infty}$ mixing time bounds via the spectral profile. This approach lets us recover and refine previous conductance-based bounds of mixing time (including the Morris-Peres result), and in general leads to sharper estimates of convergence rates. We apply this method to several models including groups with moderate growth, the fractal-like Viscek graphs, and the product group $Z_a \times Z_b$, to obtain tight bounds on the corresponding mixing times.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-26

Publication Date: January 24, 2006

DOI: 10.1214/EJP.v11-300

References

  1. D. Aldous and J. Fill, Reversible Markov chains and random walks on graphs, Monograph in preparation available on the web at stat-www.berkeley.edu/users/aldous/RWG/book.html.
  2. Martin Barlow, Thierry Coulhon, and Alexander Grigor'yan, Manifolds and graphs with slow heat kernel decay, Invent. Math. 144 (2001), 609-649. MR1833895
  3. Sergey G. Bobkov and Prasad Tetali, Modified log-Sobolev inequalities in discrete settings, Proc. of the ACM STOC 2003, 2003, pp.287-296.
  4. T. Coulhon, A. Grigor'yan, and C. Pittet, A geometric approach to on-diagonal heat kernel lower bound on groups, Ann. Inst. Fourier 51 (2001), 1763-1827. MR1871289
  5. E. Carlen, S. Kusuoka, and D. Stroock, Upper bounds for symmetric Markov transition functions, Ann. Inst. H. Poincaré Probab. Statist. 23 (1987), 245-287. MR0898496
  6. T. Coulhon, Ultracontractivity and Nash type inequalities, J. Funct. Anal. 141 (1996), 510-539. MR1418518
  7. Thierry Coulhon and Laurent Saloff-Coste, Marches aléatoires nonsymétriques sur les groupes unimodulaires, C. R. Acad. Sci. Paris Sér. I Math. 310 (1990), no. 8, 627-630. MR1065425
  8. Thierry Coulhon and Laurent Saloff-Coste, Puissances d'un opérateur régularisant, Ann. Inst. H. Poincaré Probab. Statist. 26 (1990), no. 3, 419-436. MR1066086
  9. E.B. Davies, Heat kernels and spectral theory, Cambridge University Press, 1990. MR1103113
  10. P. Diaconis and L. Saloff-Coste, Moderate growth and random walk on finite groups, Geom. and Funct. Anal. 4 (1994), 1-34. MR1254308
  11. Persi Diaconis and Laurent Saloff-Coste, An application of harnack inequalities to random walk on nilpotent quotients, Proceedings of the Conference in Honor of Jean-Pierre Kahane (Orsay, 1993), J. Fourier Anal. Appl., Special Issue, 1995, pp. 189-207. MR1364885
  12. P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Prob. 6 (1996), 695-750. MR1410112
  13. P. Diaconis and L. Saloff-Coste, Nash inequalities for finite Markov chains, J. Theoret. Probab. 9 (1996), no. 2, 459-510. MR1385408
  14. A. Grigor'yan, Heat kernel upper bounds on a complete non-compact manifold, Revista Matemática Iberoamericana 10 (1994), 395-452. MR1286481
  15. L. Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), 1061-1083. MR0420249
  16. L. Gross, Logarithmic Sobolev inequalities and contractivity properties of semigroups, Lecture Notes in Mathematics, vol. 1563, Springer, 1993. MR1292277
  17. L. Lovász and R. Kannan, Faster mixing via average conductance, Annual ACM Symposium on theory of computing (Atlanta, GA, 1999), ACM, 1999, pp. 282-287. MR1798047
  18. R. Latala and K. Oleszkiewicz, Between Sobolev and Poincaré, Geometric Aspects of Functional Analysis, Lect. Notes in Math., vol. 1745, 2000, pp. 147-168. MR1796718
  19. G.F. Lawler and A.D. Sokal, Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality, Trans. Amer. Math. Soc. 309 (1988), 557-580. MR0930082
  20. Ben Morris and Yuval Peres, Evolving sets, mixing and heat kernel bounds, Preprint. MR2120476
  21. J. Nash, Continuity of solutions of parabolic and elliptic equations, Amer. J. Math. 80 (1958), 931-954. MR0100158
  22. Ch. Pittet and L. Saloff-Coste, Isoperimetry, volume growth and random walks, Monograph in preparation.
  23. Laurent Saloff-Coste, Lectures on finite Markov chains, Lectures on Probability Theory and Statistics (P. Bernard, ed.), Lecture Notes in Mathematics, vol. 1665, Ecole d'Eté de Probabiltés de Saint-Flour XXVI, Springer, 1996. MR1490046
  24. A.J. Sinclair and M. R. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation 82 (1989), 93-133. MR1003059
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.