• 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 multi-step (non-Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings.

Versions available:

Journal version: Random Structures & Algorithms	hayes-vigoda-VLPC.pdf
Extended version dated January 2005	Available by request
SODA Proceedings version, Oct. 5, 2003, 8pp.	Available by request.
Previous release, July 3, 2003, 11pp.	Available by request.