TR-2003-02
A Non-Markovian Coupling Technique
Thomas P. Hayes; Eric Vigoda. 25 February, 2003.
Communicated by Eric Vigoda.
Abstract
We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce non-Markovian couplings.We use our theorem to reduce the threshold for efficiently sampling colorings of bounded-degree graphs. This appears to be the first use of a non-Markovian coupling to analyze a non-trivial Markov chain.
Original Document
The original document is available in Postscript (uploaded 25 February, 2003 by Eric Vigoda).
Comments
Comments are available on this technical report.