95-41 A semidefinite bound for mixing rates of Markov chains

DIMACS TR: 95-41

A semidefinite bound for mixing rates of Markov chains

Author: Nabil Kahale

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-41.ps.gz

DIMACS Home Page