Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains

DOI10.1017/S096354831400025XzbMATH Open1315.60085arXivmath/0611585OpenAlexW2949430827MaRDI QIDQ5495677FDOQ5495677

Ravi Montenegro

Publication date: 6 August 2014

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

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.

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)

Cites Work

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

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)