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

DOI10.1214/AOAP/1029962594MaRDI QIDQ1296583zbMATH OpenOpenAlexFDO

Authors 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

Markov chainseigenvaluePoincaré and Cheeger inequalities

Mathematics Subject Classification ID

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

Recommendations

• Geometric bounds for eigenvalues of Markov chains
• Comparison theorems for reversible Markov chains
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Estimations pour les chaînes de Markov réversibles

Cites work

• scientific article; zbMATH DE number 3829941 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 1097578 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Approximating the Permanent
• Eigenvalues and expanders
• Generating a random permutation with random transpositions
• Geometric bounds for eigenvalues of Markov chains
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Isoperimetric Inequalities in Mathematical Physics. (AM-27)
• Moderate growth and random walk on finite groups
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• On the maximum degree in a random tree
• Ramanujan graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(7)

• The smallest eigenvalue for reversible Markov chains
• A probabilistic approach to Carne's bound
• Constructing optimal transition matrix for Markov chain Monte Carlo
• Cheeger inequalities for absorbing Markov chains
• A note on geometric bounds for eigenvalues
• Exact and asymptotic results on coarse Ricci curvature of graphs
• Comparison theorems for reversible Markov chains

This page was built for publication: Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296583)