Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Bounds on the $ L\sp 2$ spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality


Authors: Gregory F. Lawler and Alan D. Sokal
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] J. Cheeger, A lower bound for the lowest eigenvalue of the Laplacian, Problems in Analysis: A Symposium in Honor of S. Bochner (R. C. Gunning, ed.), Princeton Univ. Press, Princeton, N.J., 1970, pp. 195-199. MR 0402831 (53:6645)
  • [2] P. Buser, On Cheeger's inequality $ {\lambda _1} \geqslant {h^2}/4$, Geometry of the Laplace Operator, Proc. Sympos. Pure. Math. (R. Osserman and A. Weinstein, eds.), vol. 36, Amer. Math. Soc., Providence, R.I., 1980, pp. 29-77. MR 573428 (83b:58075)
  • [3] I. Chavel, Eigenvalues in Riemannian geometry, Academic Press, Orlando, Fla., 1984. MR 768584 (86g:58140)
  • [4] P. H. Bérard, Spectral geometry: Direct and inverse problems, Lecture Notes in Math., no. 1207, Springer-Verlag, Berlin-Heidelberg-New York, 1986. MR 861271 (88f:58146)
  • [5] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83-96. MR 875835 (88e:05077)
  • [6] J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), 787-794. MR 743744 (85m:58185)
  • [7] A. D. Sokal and L. E. Thomas, Exponential convergence to equilibrium for a class of random-walk models, J. Statist. Phys. (submitted). MR 988560 (90e:60084)
  • [8] P. R. Halmos, A Hilbert space problem book, 2nd ed., Springer-Verlag, Berlin-Heidelberg-New York, 1982. MR 675952 (84e:47001)
  • [9] T. Kato, Perturbation theory for linear operators, 2nd ed., Springer-Verlag, Berlin-Heidelberg-New York, 1976. MR 0407617 (53:11389)
  • [10] -, Some mapping theorems for the numerical range, Proc. Japan Acad. 41 (1965), 652-655. MR 0222693 (36:5743)
  • [11] E. Nummelin, General irreducible Markov chains and non-negative operators, Cambridge Univ. Press, Cambridge, England, 1984, $ \S7.4$.
  • [12] C. Kipnis and S. R. S. Varadhan, Central limit theorems for additive functionals of reversible Markov processes and applications to simple exclusions, Comm. Math. Phys. 104 (1986), 1-19. MR 834478 (87i:60038)
  • [13] L. E. Thomas and Zhong Yin, Approach to equilibrium for random walks on graphs and for stochastic infinite particle systems, J. Math. Phys. 27 (1986), 2475-2477. MR 857388 (88d:82023)
  • [14] A. Berretti and A. D. Sokal, New Monte Carlo method for the self-avoiding walk, J. Statist. Phys. 40 (1985), 483-531. MR 806712 (86k:82003)
  • [15] E. B. Davies, Metastable states of symmetric Markov semigroups. I, Proc. London Math. Soc. (3) 45 (1982), 133-150. MR 662668 (84e:47056a)
  • [16] -, Metastable states of symmetric Markov semigroups. II, J. London Math. Soc (2) 26 (1982), 541-556. MR 684567 (84e:47056b)
  • [17] -, Dynamical stability of metastable states, J. Funct. Anal. 46 (1982), 373-386. MR 661877 (84e:47056c)
  • [18] -, Spectral properties of metastable Markov semigroups, J. Funct. Anal. 52 (1983), 315-329. MR 712583 (84k:47037)
  • [19] -, Metastability and the Ising model, J. Statist. Phys. 27 (1982), 657-675. MR 661682 (84g:82013)
  • [20] N. Alon and V. D. Milman, $ {\lambda _1}$, isoperimetric inequalities for graphs, and superconcentrators, J. Comb. Theory Ser. B 38 (1985), 73-88. MR 782626 (87b:05092)
  • [21] M. Gromov and V. D. Milman, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), 843-854. MR 708367 (84k:28012)
  • [22] W. E. Donath and A. J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Develop. 17 (1973), 420-425. MR 0329965 (48:8304)
  • [23] A. D. Sokal and L. E. Thomas, Lower bounds on the autocorrelation time of a reversible Markov chain, in preparation.
  • [24] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak. Math. J. 23 (1973), 298-305. MR 0318007 (47:6556)
  • [25] -, A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak. Math. J. 25 (1975), 619-633. MR 0387321 (52:8164)
  • [26] -, Algebraische Zusammenhangszahl der Graphen und ihre numerische Bedeutung, Numerische Methoden bei Graphentheoretischen und Kombinatorischen Problemen (L. Collatz, G. Meinardus and H. Werner, eds.), Birkhäuser, Basel-Stuttgart, 1975, pp. 69-85. MR 0432493 (55:5481)
  • [27] D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs, Academic Press, New York, 1980. MR 572262 (81i:05054)
  • [28] -, Some possible directions in further investigations of graph spectra, Algebraic Methods in Graph Theory (L. Lovász and V. T. Sós, eds.), vol. I, Colloq. Math. Soc. Janos Bolyai, no. 25, North-Holland, Amsterdam, 1981, pp. 47-67. MR 642032 (83b:05090)
  • [29] P. Buser, On the bipartition of graphs, Discrete Appl. Math. 9 (1984), 105-109. MR 754431 (86a:05072)
  • [30] M. Fiedler, Bounds for eigenvalues of doubly stochastic matrices, Linear Algebra Appl. 5 (1972), 299-310. MR 0573021 (58:28042)
  • [31] -, A quantitative extension of the Perron-Frobenius theorem, Linear and Multilinear Algebra 1 (1973), 81-88. MR 0318192 (47:6739)
  • [32] M. Fiedler and V. Pták, A quantitative extension of the Perron-Frobenius theorem for doubly stochastic matrices, Czechoslovak. Math. J. 25 (1975), 339-353. MR 0387322 (52:8165)
  • [33] T. Pignataro and D. Sullivan, Ground state and lowest eigenvalue of the Laplacian for non-compact hyperbolic surfaces, Comm. Math. Phys. 104 (1986), 529-535. MR 841667 (87m:58178)
  • [34] J. Dodziuk, T. Pignataro, B. Randol and D. Sullivan, Estimating small eigenvalues of Riemann surfaces, Contemp. Math., vol. 64, Amer. Math. Soc., Providence, R.I., 1987, pp. 93-121. MR 881458 (88h:58119)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 60J05, 58G25, 60J25, 60J27, 82A31

Retrieve articles in all journals with MSC: 60J05, 58G25, 60J25, 60J27, 82A31


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1988-0930082-9
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society