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 E. Nummelin, General irreducible Markov chains and non-negative operators, Cambridge Univ. Press, Cambridge, England, 1984, $\S 7.4$.
- 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 A. D. Sokal and L. E. Thomas, Lower bounds on the autocorrelation time of a reversible Markov chain, in preparation.
- 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
Additional Information
- © Copyright 1988 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 309 (1988), 557-580
- MSC: Primary 60J05; Secondary 58G25, 60J25, 60J27, 82A31
- DOI: https://doi.org/10.1090/S0002-9947-1988-0930082-9
- MathSciNet review: 930082