Variable length path coupling

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.

REFERENCES

• 1: D. J. Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Séminaire de Probabilities XVII, 243--297. Springer-Verlag, 1983. Lecture Notes in Mathematics 986.
• 2: J. van den Berg and R. Brouwer. Random sampling for the monomer-dimer model on a lattice. J. Math. Phys. 41(3):1585--1597, 2000.
• 3: R. Bubley , M. Dyer, Path coupling: A technique for proving rapid mixing in Markov chains, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.223, October 19-22, 1997
• 4: Russ Bubley , Martin Dyer , Mark Jerrum, An elementary analysis of a procedure for sampling points in a convex body, Random Structures & Algorithms, v.12 n.3, p.213-235, May 1998 [doi>10.1002/(SICI)1098-2418(199805)12:3<213::AID-RSA1>3.0.CO;2-Y]
• 5: Artur Czumaj , Miroslaw Kutylowski, Delayed path coupling and generating random permutations, Random Structures & Algorithms, v.17 n.3-4, p.238-259, Oct. 2000
• 6: W. Doeblin. Exposé de la theorie des chaînes simples constantes de Markov à un nombre fini d'états. Rev. Math. Union Interbalkanique, 2:77--105, 1938.
• 7: A. Frieze, Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.579, October 14-17, 2001
• 8: Martin Dyer , Leslie Ann Goldberg , Catherine Greenhill , Mark Jerrum , Michael Mitzenmacher, An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings, SIAM Journal on Computing, v.30 n.6, p.1962-1975, 2001 [doi>10.1137/S0097539700372708]
• 9: Martin Dyer , Catherine Greenhill , Mike Molloy, Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs, Random Structures & Algorithms, v.20 n.1, p.98-114, January 2002 [doi>10.1002/rsa.10020]
• 10: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
• 11: D. Griffeath, A maximal coupling for Markov chains, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 31:95--106, 1974/75.
• 12: Thomas P. Hayes, Randomly coloring graphs of girth at least five, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780584]
• 13: Thomas P. Hayes , Eric Vigoda, A Non-Markovian Coupling for Randomly Sampling Colorings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.618, October 11-14, 2003
• 14: V. S. Anil Kumar , H. Ramesh, Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.241, October 17-18, 1999
• 15: Mark Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures & Algorithms, v.7 n.2, p.157-165, September 1995 [doi>10.1002/rsa.3240070205]
• 16: Michael Molloy, The Glauber dynamics on colourings of a graph with high girth and maximum degree, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509924]
• 17: Eric Vigoda, Improved Bounds for Sampling Coloring, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.51, October 17-18, 1999