Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger? (English) Zbl 0935.60057

From the authors’ summary: “The Poincaré and Cheeger bounds are useful for the second largest eigenvalue of a reversible Markov chain. There are versions of these bounds which involve choosing paths. This paper studies these path-related bounds and shows that Poincaré bound is superior to the Cheeger bound for simple random walk on a finite group with any symmetric generating set.”
For related papers see P. Diaconis and D. Stroock [Ann. Appl. Probab. 1, No. 1, 36-61 (1991; Zbl 0731.60061)], M. Jerrum and A. Sinclair [SIAM J. Comput. 18, No. 6, 1149-1178 (1989; Zbl 0723.05107)] and A. Sinclair [Comb. Probab. Comput. 1, No. 4, 351-370 (1992; Zbl 0801.90039)].


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60C05 Combinatorial probability
Full Text: DOI


[1] Aldous, D. (1987). On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probab. Engrg. Inform. Sci. 1 33-46. · Zbl 1133.60327
[2] Alon, N. (1986). Eigenvalues and expanders. Combinatorica 6 83-96. · Zbl 0661.05053
[3] Alon, N. and Millman, V. D. (1985). 1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38 73-88. · Zbl 0549.05051
[4] Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analy sis (Papers dedicated to Salomon Bochner, 1969) 195-199. Princeton Univ. Press. · Zbl 0212.44903
[5] Chung, F. (1997). Spectral Graph Theory. Amer. Math. Soc., Providence, RI. · Zbl 0867.05046
[6] Diaconis, P. (1988). Group Representations in Probability and Statistics. IMS, Hay ward, CA. Diaconis, P. and Saloff-Coste, L. (1993a). Comparison techniques for random walk on finite groups. Ann. Probab. 21 2131-2156. Diaconis, P. and Saloff-Coste, L. (1993b). Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696-730. · Zbl 0695.60012
[7] Diaconis, P. and Saloff-Coste, L. (1994). Moderate growth and random walk on finite groups. Geom. Funct. Anal. 4 1-36. Diaconis, P. and Saloff-Coste, L. (1996a). Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695-750. Diaconis, P. and Saloff-Coste, L. (1996b). Nash inequalities for finite Markov chains. J. Theoret. Probab. 9 459-510. · Zbl 0795.60005
[8] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete. 57 159-179. · Zbl 0485.60006
[9] Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36-61. · Zbl 0731.60061
[10] Humphrey s, J. (1990). Reflection Groups and Coxeter Groups. Cambridge Univ. Press.
[11] Jerrum, M. and Sinclair, A. (1989). Approximating the permanent. SIAM J. Comput. 18 1149- 1178. · Zbl 0723.05107
[12] Kahale, N. (1997). A semidefinite bound for mixing rates of Markov chains. Random Structures Algorithms. To appear. (Preliminary version appears in Lecture Notes in Comput. Sci. 1084 190-203. Springer, Berlin.) · Zbl 0889.90154
[13] Kannan, R. (1994). Markov chains and poly nomial time algorithms. In Proceedings of the 35th Annual Sy mposium on Foundations of Computer Science 656-671. IEEE, New York.
[14] Lubotzky, A., Phillips, R. and Sarnak, P. (1988). Ramanujan graphs. Combinatorica 8 261-278. · Zbl 0661.05035
[15] Moon, J. W. (1968). On the maximum degree in a random tree. Michigan Math. J. 15 429-432. · Zbl 0176.22403
[16] Polyá, G. and Szeg ö, S. (1951). Isoperimetric Inequalities in Mathematical physics. Princeton Univ. Press. · Zbl 0044.38301
[17] Sinclair, A. (1992). Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351-370. · Zbl 0801.90039
[18] Szekeres, G. (1983). Distribution of labeled trees by diameter. Combinatorial Mathematics X. Lecture Notes in Math. 1036 392-397. Springer, Berlin. · Zbl 0524.05026
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.