Premium
Variable length path coupling
Author(s) -
Hayes Thomas P.,
Vigoda Eric
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20166
Subject(s) - path (computing) , markov chain , coupling (piping) , glauber , mathematics , generalization , variable (mathematics) , markov chain mixing time , upper and lower bounds , markov process , random variable , statistical physics , combinatorics , discrete mathematics , markov property , physics , computer science , markov model , mathematical analysis , quantum mechanics , statistics , mechanical engineering , scattering , engineering , programming language
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