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

Fulman, Jason; Wilmer, Elizabeth L.

Ann. Appl. Probab. 9, No. 1, 1-13 (1999).

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)].

Reviewer: G.Oprişan (Bucureşti)

MSC:

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

Keywords:

Markov chains; eigenvalue; Poincaré and Cheeger inequalities

Citations:

Zbl 0731.60061; Zbl 0723.05107; Zbl 0801.90039

References:

[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 · doi:10.1017/S0269964800000267
[2]	Alon, N. (1986). Eigenvalues and expanders. Combinatorica 6 83-96. · Zbl 0661.05053 · doi:10.1007/BF02579166
[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 · doi:10.1016/0095-8956(85)90092-9
[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 · doi:10.1007/BF01898359
[8]	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
[9]	Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36-61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[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 · doi:10.1137/0218077
[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 · doi:10.1002/(SICI)1098-2418(199712)11:4<299::AID-RSA2>3.0.CO;2-U
[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 · doi:10.1007/BF02126799
[15]	Moon, J. W. (1968). On the maximum degree in a random tree. Michigan Math. J. 15 429-432. · Zbl 0176.22403 · doi:10.1307/mmj/1029000098
[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 · doi:10.1017/S0963548300000390
[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 · doi:10.1007/BFb0071532