Geometric Bounds for Eigenvalues of Markov Chains
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203 · see citing works
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 4,049 · see citing works
Biggs, N. (1974) · doi:10.1017/cbo9780511608704 · Cited by 2,940 · see citing works
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705 · see citing works
Group representations in probability and statistics
Diaconis, P. (1988) · doi:10.1214/lnms/1215467407 · Cited by 1,381 · see citing works
Self-citationTHE LAPLACIAN SPECTRUM OF GRAPHS y
Mohar, B. (1991) · Cited by 1,119 · see citing works
Alon, N. (1986) · COMBINATORICA · doi:10.1007/bf02579166 · Cited by 1,101 · see citing works
Isoperimetric inequalities and applications
Bandle, C. (1980) · Medical Entomology and Zoology · Cited by 913 · see citing works
λ1, Isoperimetric inequalities for graphs, and superconcentrators
Alon, N., & Milman, V. D. (1985) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(85)90092-9 · Cited by 874 · see citing works
Jerrum, M., & Sinclair, A. (1989) · SIAM Journal on Computing · doi:10.1137/0218077 · Cited by 767 · see citing works
Approximate counting, uniform generation and rapidly mixing Markov chains
Sinclair, A., & Jerrum, M. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90067-9 · Cited by 765 · see citing works
Random Walk and the Theory of Brownian Motion
Kac, M. (1947) · American Mathematical Monthly · doi:10.1080/00029890.1947.11990189 · Cited by 553 · see citing works
Difference equations, isoperimetric inequality and transience of certain random walks
Dodziuk, J. (1984) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1984-0743744-x · Cited by 476 · see citing works
Fill, J. A. (1991) · The Annals of Applied Probability · doi:10.1214/aoap/1177005981 · Cited by 343 · see citing works
Eigenvalues, diameter, and mean distance in graphs
Mohar, B. (1991) · Graphs and Combinatorics · doi:10.1007/bf01789463 · Cited by 306 · see citing works
Lawler, G. F., & Sokal, A. D. (1988) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1988-0930082-9 · Cited by 283 · see citing works
Strong Stationary Times Via a New Form of Duality
Diaconis, P. W., & Fill, J. A. (1990) · The Annals of Probability · doi:10.1214/aop/1176990628 · Cited by 272 · see citing works
Self-citationHow hard is it to marry at random? (On the approximation of the permanent)
Broder, A. Z. (1986) · doi:10.1145/12130.12136 · Cited by 173 · see citing works
Asymptotic analysis of a random walk on a hypercube with many dimensions
Diaconis, P. W., Graham, R., & Morrison, J. A. (1990) · Random Structures and Algorithms · doi:10.1002/rsa.3240010105 · Cited by 166 · see citing works
Self-citationTime to Reach Stationarity in the Bernoulli–Laplace Diffusion Model
Diaconis, P. W., & Shahshahani, M. (1987) · SIAM Journal on Mathematical Analysis · doi:10.1137/0518016 · Cited by 163 · see citing works
Self-citationSimulated annealing via Sobolev inequalities
Holley, R. A., & Stroock, D. W. (1988) · Communications in Mathematical Physics · doi:10.1007/bf01224127 · Cited by 162 · see citing works
Self-citationAldous, D. (1987) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964800000267 · Cited by 133 · see citing works
Fast uniform generation of regular graphs
Jerrum, M., & Sinclair, A. (1990) · Theoretical Computer Science · doi:10.1016/0304-3975(90)90164-d · Cited by 118 · see citing works
Bounds for eigenvalues of certain stochastic matrices
Landau, H. J., & Odlyzko, A. M. (1981) · Linear Algebra and its Applications · doi:10.1016/0024-3795(81)90003-3 · Cited by 88 · see citing works
Upper bounds on the maximum modulus of subdominant eigenvalues of nonnegative matrices
Rothblum, U. G., & Tan, C. P. (1985) · Linear Algebra and its Applications · doi:10.1016/0024-3795(85)90125-9 · Cited by 73 · see citing works
Orthogonal Polynomials and Chevalley Groups
Stanton, D. (1984) · Springer eBooks · doi:10.1007/978-94-010-9787-1_2 · Cited by 72 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- ALDoUs, D. (1983). Random walk on finite groups and rapidly mixing Markov chains. Séminaire de Probabilités XVII. Lecture Notes in Math. 986 243–297. Springer, New York.
- MIHAIL, M. (1989). Combinatorial aspects of expanders. Ph.D. dissertation, Dept. Computer Science, Harvard Univ.
- SAxL, J. (1981). On multiplicity-free permutation representations. Finite Geometrics and Designs. London Math. Soc. Lecture Note Ser. 48 337–353. Cambridge Univ. Press.
- SENETA, E. (1981). Non-negative Matrices and Markov Chains, 2nd ed. Springer, New York. n n y () di mixing Markov chains. Inform. and Comput. 82 93–133.
Cited by
Sorted by citations
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439 · see citing works
Practical markov chain monte carlo
Geyer, C. J. (1992) · Statistical Science · doi:10.1214/ss/1177011137 · Cited by 2,045 · see citing works
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,073 · see citing works
“Such bounds have been explored at great length within Markov chain literature, see e.g., the seminal paper [18] or the monograph [29], resulting in many different techniques, each giving accurate bounds on some graphs, and others.”
BackgroundQuantum optimization of maximum independent set using Rydberg atom arrays
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., et al. (2022) · Science · doi:10.1126/science.abo6587 · Cited by 430 · see citing works
Data Fusion and Multicue Data Matching by Diffusion Maps
Lafon, S., Keller, Y., & Coifman, R. R. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.223 · Cited by 312 · see citing works
Magniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294 · see citing works
Accelerating Gaussian diffusions
Hwang, C.-R., Hwang-Ma, S.-Y., & Sheu, S.-J. (1993) · The Annals of Applied Probability · doi:10.1214/aoap/1177005371 · Cited by 108 · see citing works
- Authors
- Diaconis, P., & Stroock, D.
- ORCID
- Diaconis, Persi
- Venue
- The Annals of Applied Probability
- Publisher
- Institute of Mathematical Statistics
- Published
- 1991-02-01
- Volume
- 1
- Issue
- 1
- Pages
- 36-61
- ISSN
- 1050-5164 (ISSN-L)
- 2168-8737
- OpenAlex
- W2043694962
- Cited by
- 882
- References
- 26
- Citations by year
- 2026: 8 · 2025: 18 · 2024: 6 · 2023: 15 · 2022: 16 · 2021: 20 · 2020: 18 · 2019: 38 · 2018: 21 · 2017: 16 · 2016: 32 · 2015: 30 · 2014: 31 · 2013: 36 · 2012: 42
- FWCI
- 22.07
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- The Annals of Applied Probability (publishedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- Topics
- Physical Sciences › Mathematics › Statistics and Probability › Markov Chains and Monte Carlo Methods
- Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Keywords
- Markov chains, eigenvalue bounds, second largest eigenvalue, spectral gap, reversible Markov chains, graph diameter, covering number, Cheeger inequality, random walks, permanent computation, convergence rate
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
