Geometric Bounds for Eigenvalues of Markov Chains

Persi Diaconis, Daniel W. Stroock

Type: Article

Publication Date: 1991-02-01

Citations: 914

DOI: https://doi.org/10.1214/aoap/1177005980

Abstract

We develop bounds for the second largest eigenvalue and spectral gap of a reversible Markov chain. The bounds depend on geometric quantities such as the maximum degree, diameter and covering number of associated graphs. The bounds compare well with exact answers for a variety of simple chains and seem better than bounds derived through Cheeger-like inequalities. They offer improved rates of convergence for the random walk associated to approximate computation of the permanent.

Locations

CiteSeer X (The Pennsylvania State University) - View - PDF
The Annals of Applied Probability - View - PDF

Similar Works

Action	Title	Year	Authors
+	Lower bounds for covering times for reversible Markov chains and random walks on graphs	1989	David Aldous
+	The smallest eigenvalue for reversible Markov chains	2004	Xiao‐Dong Zhang
+ PDF Chat	Comparison Theorems for Reversible Markov Chains	1993	Persi Diaconis Laurent Saloff‐Coste
+ PDF Chat	The spectral gap of sparse random digraphs	2021	Simon Coste
+	The smallest eigenvalue for reversible Markov chains*1	2004	X ZHANG
+	The Spectral Gap of Sparse Random Digraphs	2017	Simon Coste
+	The Spectral Gap of Sparse Random Digraphs	2017	Simon Coste
+	On the Convergence of Reversible Markov Chains	1993	Madhav P. Desai Vasant B. Rao
+	Geometric inequalities for the eigenvalues of concentrated Markov chains	2000	Olivier François
+	Geometric inequalities for the eigenvalues of concentrated Markov chains	2000	Olivier François
+ PDF Chat	Minorations pour les chaînes de Markov unidimensionnelles	1993	Thierry Coulhon Laurent Saloff‐Coste
+	Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains	1993	Salvatore Ingrassia
+	Spectral Methods	2023	Sébastien Roch
+ PDF Chat	Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding	2017	Russell Lyons Shayan Oveis Gharan
+ PDF Chat	Some inequalities for reversible Markov chains and branching random walks via spectral optimization	2022	Jonathan Hermon
+	A semidefinite bound for mixing rates of Markov chains	1996	Nabil Kahalé
+	Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding	2012	Russell Lyons Shayan Oveis Gharan
+	Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding	2012	Russell Lyons Shayan Oveis Gharan
+ PDF Chat	Random matrices: tail bounds for gaps between eigenvalues	2016	Hoi H. Nguyen Terence Tao Van Vu
+	Random Walks on Graphs: A Survey	2001	László Lovász

Works That Cite This (680)

Action	Title	Year	Authors
+	An Adaptive Sequential Monte Carlo Algorithm for Computing Permanents	2013	Ajay Jasra Junshan Wang
+	Reducing the Ising model to matchings	2009	Mark Huber Jenny Law
+ PDF Chat	Dynamic Phase Diagram of the REM	2019	Véronique Gayrard Lisa Hartung
+ PDF Chat	On the Convergence Time of Some Non-Reversible Markov Chain Monte Carlo Methods	2020	Marie Vialaret Florian Maire
+	Annealing and tempering for sampling and counting	2007	Dana Randall Eric Vigoda Nayantara Bhatnagar
+	Practical Markov Chain Monte Carlo	1992	Charles J. Geyer
+	Reversible Markov Chains and Random Walks on Graphs	2014	David Aldous James Allen Fill
+	Spatial Statistics and Bayesian Computation	1993	Julian Besag Peter J. Green
+	Convergence Rates for Markov Chains	1995	Jeffrey S. Rosenthal
+ PDF Chat	Ollivier’s Ricci Curvature, Local Clustering and Curvature-Dimension Inequalities on Graphs	2013	Jürgen Jost Shiping Liu

Works Cited by This (23)

Action	Title	Year	Authors
+	Algebraic Graph Theory	1974	Norman Biggs
+ PDF Chat	Algebraic connectivity of graphs	1973	Miroslav Fiedler
+	Group representations in probability and statistics	1988	Persi Diaconis
+ PDF Chat	Eigenvalues and expanders	1986	Ilan Alon
+	Bounds for eigenvalues of certain stochastic matrices	1981	H. J. Landau Andrew Odlyzko
+	Eigenvalues, diameter, and mean distance in graphs	1991	Bojan Mohar
+ PDF Chat	Strong Stationary Times Via a New Form of Duality	1990	Persi Diaconis James Allen Fill
+	λ1, Isoperimetric inequalities for graphs, and superconcentrators	1985	Noga Alon Vitali Milman
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+	Upper bounds on the maximum modulus of subdominant eigenvalues of nonnegative matrices	1985	Uriel G. Rothblum Choon Peng Tan