Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-14T18:40:22.210Z Has data issue: false hasContentIssue false
  • English
  • Français

Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains

Published online by Cambridge University Press:  12 September 2008

Salvatore Ingrassia
Salvatore Ingrassia
Affiliation:
Istituto di Statistica - Facoltà di Economia e Commercio, Università di Catania, Corso Italia, 55 – 95129 Catania (Italy) email: ingrax@mathct.cineca.it
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider the problem of estimating the spectral gap of a reversible Markov chain in terms of geometric quantities associated with the underlying graph. This quantity provides a bound on the rate of convergence of a Markov chain towards its stationary distribution. We give a critical and systematic treatment of this subject, summarizing and comparing the results of the two main approaches in the literature, algebraic and functional. The usefulness and drawbacks of these bounds are also discussed here.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 3 , September 1993 , pp. 301 - 323
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aldous, D. (1981) Random walks on finite groups and rapidly mixing Markov chains. In: Seminaire de Probabilities XVII. Springer- Verlag Lecture Notes in Mathematics 986 243–297.CrossRefGoogle Scholar
[2]Aldous, D. and Diaconis, P. (1987) Strong uniform times and finite random walks. Advances in Applied Mathematics 8 69–97.CrossRefGoogle Scholar
[3]Cacoullos, T. (1982) On upper and lower bounds for the variance of a function of a random variable. Annals of Probability 10 788–809.CrossRefGoogle Scholar
[4]Cheeger, J. (1970) A lower bound for the smallest eigenvalue of the Laplacian. In: Gunning, R. C. (ed.) Problems in Analysis, Princeton University Press, New Jersey185–189.Google Scholar
[5]Chen, L. H. Y. (1985) Poincaré-type inequalities via stochastic integrals. Z. Wahrschenlichkeits theorie verw. 69 251–277.CrossRefGoogle Scholar
[6]Chernoff, H. (1981) A note on an inequality involving the normal distribution. The Annals of Probability 9 533–536.CrossRefGoogle Scholar
[7]Cvetković, D. M., Doob, M. and Sachs, H. (1979) Spectra of graphs. Theory and application, Academic Press, New York.Google Scholar
[8]Dautray, R. and Lions, J. L. (1988) Mathematical analysis and numerical methods for science and technology, vol. 2 “Functional and variational methods”, Springer-Verlag, Berlin Heidelberg.Google Scholar
[9]Desai, M. P. (1992) An eigenvalue-based approach to the finite time behaviour of simulated annealing, Ph. D. thesis, Coordinate Science Laboratory, University of Illinois at Urbana Champaign.Google Scholar
[10]Diaconis, P. and Shahshahani, M. (1986) Products of random matrices as they arise in the study of random walks on groups. Contemporary Mathematics 50 183–195.CrossRefGoogle Scholar
[11]Diaconis, P. and Stroock, D. (1991) Geometric bounds for eigenvalues of Markov chains. Annals of Applied Probability 1 36–61.CrossRefGoogle Scholar
[12]Doyle, P. G. and Snell, J. L. (1984) Random walk and electric networks, Mathematical Association of America, Washington.CrossRefGoogle Scholar
[13]Feller, W. (1968) An introduction to probability theory and its applications, Vol. 1, John Wiley and Sons.Google Scholar
[14]Fiedler, M. (1972) Bounds for eigenvalues of doubly stochastic matrices. Linear Algebra and its Applications 5 299–310.CrossRefGoogle Scholar
[15]Fiedler, M. (1973) Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23 298–305.CrossRefGoogle Scholar
[16]Fiedler, M. (1989) Laplacian of graphs and algebraic connectivity. Combinatorics and Graph Theory 25 57–70.Google Scholar
[17]Fiedler, M. and Ptak, V. (1975) A quantitative extension of the Perron-Frobenius theorem for doubly stochastic matrices. Czechoslovak Mathematical Journal 25 (3) 339–353.CrossRefGoogle Scholar
[18]Fill, J. A. (1991) Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Annals of Applied Probability 1 64–87.CrossRefGoogle Scholar
[19]Gerl, P. (1985) Random walks on graphs. In: Probability Measure on Groups VIII. Springer-Verlag Lecture Notes in Mathematics 1210 285–303.CrossRefGoogle Scholar
[20]Gerl, P. (1985) Sobolev inequalities and random walks. In: Probability Measure on Groups VIII. Springer-Verlag Lecture Notes in Mathematics 1210 84–96.CrossRefGoogle Scholar
[21]Hanlon, P. (1992) A Markov chain on the symmetric group and Jack symmetric function. Discrete Mathematics 99 123–140.CrossRefGoogle Scholar
[22]Hwang, C. R. and Sheu, S. J. (1987) A generalization of Chernoff inequality via stochastic integrals. Probability Theory and Related Fields 75 149–157.CrossRefGoogle Scholar
[23]Ingrassia, S. (1991) Spettri di catene di Markov e algoritmi di ottimizzazione, Tesi di Dottorato, Università di Napoli.Google Scholar
[24]Ingrassia, S. (1993) On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds. Annals of Applied Probability. (To appear.)Google Scholar
[25]Kemeny, J. G. and Snell, J. L. (1975) Finite Markov chains, Van Nostrand.Google Scholar
[26]Klassen, C.-A. J. (1985) On an inequality of Chernoff. Annals of Probability 13 (3) 966–974.CrossRefGoogle Scholar
[27]Landau, H. J. and Odlyzko, A. M. (1981) Bounds for eigenvalues of certain stochastic matrices. Linear Algebra and its Application 38 5–15.CrossRefGoogle Scholar
[28]Lawler, G. and Sokal, A. (1989) Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality. Transactions of the American Mathematical Society 309 (2) 557–580.Google Scholar
[29]Maas, C. (1987) Transportation in graphs and the admittance spectrum. Discrete Applied Mathematics 16 31–49.CrossRefGoogle Scholar
[30]Mohar, B. (1988) The Laplacian spectrum of graphs. Proc. 6th Inter. Conf. Kalamazoo.Google Scholar
[31]Pachpatte, B. G. (1985) Discrete analogous of some inequalities ascribed to Wirtinger. Utilitas Mathematica 28 137–143.Google Scholar
[32]Seneta, E. (1981) Non-negative matrices and Markov chains, Springer-Verlag, New York.CrossRefGoogle Scholar
[33]Sinclair, A. (1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing 1 351–370.CrossRefGoogle Scholar
[34]Sinclair, A. and Jerrum, M. (1989) Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82 (1) 93–133.CrossRefGoogle Scholar
[35]Sokal, A. (1989) Monte Carlo methods in statistical mechanics: foundations and new algorithms, Troisième cycle de la physique en Suisse Romande.Google Scholar
[36]Stampacchia, G. (1966) Equations elliptiques du second ordre à coefficients discontinus, Les Presses de l'Univ. Montreal.Google Scholar
[37]Telcs, A. (1989) Random walks on graphs, electric networks and fractals. Probability Theory and its Related Fields 82 (3) 435–449.CrossRefGoogle Scholar
[38]Weinberger, H. (1974) Variational methods for eigenvalue approximation. SI AM Conf. Board of the Math. Sciences 15.Google Scholar