Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?

DOI10.1214/aoap/1029962594zbMath0935.60057OpenAlexW2060191528MaRDI QIDQ1296583

Jason Fulman, Elizabeth L. Wilmer

Publication date: 25 April 2000

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1029962594

zbMATH Keywords

eigenvalueMarkov chainsPoincaré and Cheeger inequalities

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Related Items

Constructing optimal transition matrix for Markov chain Monte Carlo, Exact and asymptotic results on coarse Ricci curvature of graphs, A note on geometric bounds for eigenvalues, The smallest eigenvalue for reversible Markov chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Geometric bounds for eigenvalues of Markov chains
• Ramanujan graphs
• Eigenvalues and expanders
• Moderate growth and random walk on finite groups
• On the maximum degree in a random tree
• Approximating the Permanent
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Generating a random permutation with random transpositions
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Isoperimetric Inequalities in Mathematical Physics. (AM-27)