DIMACS TR: 95-41
A semidefinite bound for mixing rates of Markov chains
Author: Nabil Kahale
We study the method of bounding the spectral gap of a reversible Markov chain
by establishing canonical paths between the states. We provide examples
where improved bounds can be obtained by allowing variable length functions
on the edges. We give a simple heuristic for computing good length functions.
Further generalization using multicommodity flow yields a bound which is an
invariant of the Markov chain, and which can be computed at an arbitrary
precision in polynomial time via semidefinite programming. We show that, for
any reversible Markov chain on n states, this bound is off by a factor of at
most O(log^2), and that this is tight.
Paper available at:
DIMACS Home Page