Bounds on the 𝐿² spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality

Lawler, Gregory F.; Sokal, Alan D.

doi:10.1090/S0002-9947-1988-0930082-9

Bounds on the $L^ 2$ spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality
HTML articles powered by AMS MathViewer

by Gregory F. Lawler and Alan D. Sokal PDF

Trans. Amer. Math. Soc. 309 (1988), 557-580 Request permission

Abstract:

We prove a general version of Cheeger’s inequality for discrete-time Markov chains and continuous-time Markovian jump processes, both reversible and nonreversible, with general state space. We also prove a version of Cheeger’s inequality for Markov chains and processes with killing. As an application, we prove ${L^2}$ exponential convergence to equilibrium for random walk with inward drift on a class of countable rooted graphs.

References

Jeff Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Papers dedicated to Salomon Bochner, 1969) Princeton Univ. Press, Princeton, N. J., 1970, pp. 195–199. MR 0402831
Peter Buser, On Cheeger’s inequality $\lambda _{1}\geq h^{2}/4$, Geometry of the Laplace operator (Proc. Sympos. Pure Math., Univ. Hawaii, Honolulu, Hawaii, 1979) Proc. Sympos. Pure Math., XXXVI, Amer. Math. Soc., Providence, R.I., 1980, pp. 29–77. MR 573428
Isaac Chavel, Eigenvalues in Riemannian geometry, Pure and Applied Mathematics, vol. 115, Academic Press, Inc., Orlando, FL, 1984. Including a chapter by Burton Randol; With an appendix by Jozef Dodziuk. MR 768584
Pierre H. Bérard, Spectral geometry: direct and inverse problems, Lecture Notes in Mathematics, vol. 1207, Springer-Verlag, Berlin, 1986. With appendixes by Gérard Besson, and by Bérard and Marcel Berger. MR 861271, DOI 10.1007/BFb0076330
N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794. MR 743744, DOI 10.1090/S0002-9947-1984-0743744-X
Alan D. Sokal and Lawrence E. Thomas, Exponential convergence to equilibrium for a class of random-walk models, J. Statist. Phys. 54 (1989), no. 3-4, 797–828. MR 988560, DOI 10.1007/BF01019776
Paul Richard Halmos, A Hilbert space problem book, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 17, Springer-Verlag, New York-Berlin, 1982. MR 675952, DOI 10.1007/978-1-4684-9330-6
Tosio Kato, Perturbation theory for linear operators, 2nd ed., Grundlehren der Mathematischen Wissenschaften, Band 132, Springer-Verlag, Berlin-New York, 1976. MR 0407617
Tosio Kato, Some mapping theorems for the numerical range, Proc. Japan Acad. 41 (1965), 652–655. MR 222693

General irreducible Markov chains and non-negative operators

C. Kipnis and S. R. S. Varadhan, Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions, Comm. Math. Phys. 104 (1986), no. 1, 1–19. MR 834478, DOI 10.1007/BF01210789
Lawrence E. Thomas and Zhong Yin, Approach to equilibrium for random walks on graphs and for stochastic infinite particle processes, J. Math. Phys. 27 (1986), no. 10, 2475–2477. MR 857388, DOI 10.1063/1.527310
Alberto Berretti and Alan D. Sokal, New Monte Carlo method for the self-avoiding walk, J. Statist. Phys. 40 (1985), no. 3-4, 483–531. MR 806712, DOI 10.1007/BF01017183
E. B. Davies, Metastable states of symmetric Markov semigroups. I, Proc. London Math. Soc. (3) 45 (1982), no. 1, 133–150. MR 662668, DOI 10.1112/plms/s3-45.1.133
E. B. Davies, Metastable states of symmetric Markov semigroups. I, Proc. London Math. Soc. (3) 45 (1982), no. 1, 133–150. MR 662668, DOI 10.1112/plms/s3-45.1.133
E. B. Davies, Metastable states of symmetric Markov semigroups. I, Proc. London Math. Soc. (3) 45 (1982), no. 1, 133–150. MR 662668, DOI 10.1112/plms/s3-45.1.133
E. B. Davies, Spectral properties of metastable Markov semigroups, J. Functional Analysis 52 (1983), no. 3, 315–329. MR 712583, DOI 10.1016/0022-1236(83)90071-X
E. B. Davies, Metastability and the Ising model, J. Statist. Phys. 27 (1982), no. 4, 657–675. MR 661682, DOI 10.1007/BF01013440
N. Alon and V. D. Milman, $\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88. MR 782626, DOI 10.1016/0095-8956(85)90092-9
M. Gromov and V. D. Milman, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), no. 4, 843–854. MR 708367, DOI 10.2307/2374298
W. E. Donath and A. J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Develop. 17 (1973), 420–425. MR 329965, DOI 10.1147/rd.175.0420

Lower bounds on the autocorrelation time of a reversible Markov chain

Miroslav Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973), 298–305. MR 318007, DOI 10.21136/CMJ.1973.101168
Miroslav Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J. 25(100) (1975), no. 4, 619–633. MR 387321, DOI 10.21136/CMJ.1975.101357
Miroslav Fiedler, Algebraische Zusammenhangszahl der Graphen und ihre numerische Bedeutung, Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen (Tagung, Math. Forschungsinst. Oberwolfach, Oberwolfach, 1974) International Series of Numerical Mathematics, Vol. 29, Birkhäuser, Basel, 1975, pp. 69–85. MR 0432493
Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR 572262
D. M. Cvetković, Some possible directions in further investigations of graph spectra, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq. Math. Soc. János Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp. 47–67. MR 642032
Peter Buser, On the bipartition of graphs, Discrete Appl. Math. 9 (1984), no. 1, 105–109. MR 754431, DOI 10.1016/0166-218X(84)90093-3
Miroslav Fiedler, Bounds for eigenvalues of doubly stochastic matrices, Linear Algebra Appl. 5 (1972), 299–310. MR 573021, DOI 10.1016/0024-3795(72)90011-0
Miroslav Fiedler, A quantitative extension of the Perron-Frobenius theorem, Linear and Multilinear Algebra 1 (1973), no. 1, 81–88. MR 318192, DOI 10.1080/03081087308817007
Miroslav Fiedler and Vlastimil Pták, A quantitative extension of the Perron-Frobenius theorem for doubly stochastic matrices, Czechoslovak Math. J. 25(100) (1975), no. 3, 339–353. MR 387322, DOI 10.21136/CMJ.1975.101329
Thea Pignataro and Dennis Sullivan, Ground state and lowest eigenvalue of the Laplacian for noncompact hyperbolic surfaces, Comm. Math. Phys. 104 (1986), no. 4, 529–535. MR 841667, DOI 10.1007/BF01211062
Jozef Dodziuk, Thea Pignataro, Burton Randol, and Dennis Sullivan, Estimating small eigenvalues of Riemann surfaces, The legacy of Sonya Kovalevskaya (Cambridge, Mass., and Amherst, Mass., 1985) Contemp. Math., vol. 64, Amer. Math. Soc., Providence, RI, 1987, pp. 93–121. MR 881458, DOI 10.1090/conm/064/881458