Sharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels

Ravi Montenegro (University of Massachusetts Lowell)

Abstract


We show how the evolving set methodology of Morris and Peres can be used to show Cheeger inequalities for bounding the spectral gap of a finite Markov kernel. This leads to sharp versions of several previous Cheeger inequalities, including ones involving edge-expansion, vertex-expansion, and mixtures of both. A bound on the smallest eigenvalue also follows.

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

Pages: 377-389

Publication Date: October 14, 2007

DOI: 10.1214/ECP.v12-1269

References

  1. N. Alon. Eigenvalues and expanders. Combinatorica 6:2 (1986), 83--96. Math. Review 88e:05077
  2. S. Bobkov, C. Houdré and P. Tetali. &lambda&infin, vertex isoperimetry and concentration. Combinatorica 20:2 (2000), 153--172. Math. Review 2001h:05066
  3. J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner) (1969), 195--199, Princeton Univ. Press, Princeton, NJ, USA. Math. Review 0402831
  4. P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab 1:1 (1991), 36--61. Math. Review 92h:60103
  5. R. A. Horn and C. R. Johnson. Matrix analysis. (1985) Cambridge Univ. Press, Cambridge. Math. Review 87e:15001
  6. M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved. Proceedings of the 20th ACM Symposium on theory of computing, 1988. (1998) 235--243. Math. Review number not available.
  7. 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:2 (1988), 557--580. Math. Review 89h:60105
  8. B. Morris and Y. Peres. Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields 133:2 (2005), 245--266. Math. Review 2007a:60042
  9. R. Montenegro and P. Tetali. Mathematical Aspects of Mixing Times in Markov Chains. Foundations and Trends in Theoretical Computer Science 1:3 (2006), NOW Publishers, Boston-Delft.
  10. T. Stoyanov. Isoperimetric and Related Constants for Graphs and Markov Chains. (2001), Ph.D. Thesis, Department of Mathematics, Georgia Institute of Technology.
Bookmark and Share


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