Details

Autor(en) / Beteiligte

• Hayes, Thomas P.
• Vigoda, Eric

Titel

Variable length path coupling

Ist Teil von

• Random structures & algorithms, 2007-10, Vol.31 (3), p.251-272

Ort / Verlag

Hoboken: Wiley Subscription Services, Inc., A Wiley Company

Erscheinungsjahr

2007

Link zum Volltext

Quelle

Wiley Online Library All Journals

Beschreibungen/Notizen

• 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 multistep (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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007