A Non-Markovian Coupling Technique

Thomas P. Hayes; Eric Vigoda. 25 February, 2003.
Communicated by Eric Vigoda.


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 are available on this technical report.