Intersection conductance and canonical alternating paths: methods for general finite Markov chains

DOI10.1017/S096354831400025XzbMATH Open1315.60085OpenAlexW2949430827MaRDI QIDQ5495677FDOQ5495677

Authors Ravi Montenegro 

Publication date 6 August 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0611585

zbMATH Keywords

Cayley graphconductancecanonical paths methodevolving sets methodgeneral finite Markov chainsmax-degree walknon-reversible non-lazy walk

Mathematics Subject Classification ID

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

Abstract: We extend the conductance and canonical paths methods to the setting of general finite Markov chains, including non-reversible non-lazy walks. The new path method is used to show that a known bound for mixing time of a lazy walk on a Cayley graph with symmetric generating set also applies to the non-lazy non-symmetric case, often even when there is no holding probability.

Recommendations

• scientific article; zbMATH DE number 18982
• Faster mixing and small bottlenecks
• Intersection and mixing times for reversible chains
• Evolving sets, mixing and heat kernel bounds
• On some mixing times for nonreversible finite Markov chains

Cites Work

• Blocking Conductance and Mixing in Random Walks
• Comparison theorems for reversible Markov chains
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Evolving sets, mixing and heat kernel bounds
• Geometric bounds for eigenvalues of Markov chains
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Markov chain comparison
• Strong stationary times via a new form of duality

Cited In (1)

• On the Validity of the Markov Interpretation of Path Diagrams of Gaussian Structural Equations Systems with Correlated Errors

This page was built for publication: Intersection conductance and canonical alternating paths: methods for general finite Markov chains

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