Intersection conductance and canonical alternating paths, methods for general finite Markov chains
arXiv:math/0611585 · doi:10.1017/S096354831400025X
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.
18 pages