Coupling with the stationary distribution and improved sampling for colorings and independent sets

ABSTRACT

We present an improved coupling technique for analyzing the mixing time of Markov chains. Using our technique, we simplify and extend previous results for sampling colorings and independent sets. Our approach uses properties of the stationary distribution to avoid worst-case configurations which arise in the traditional approach.As an application, we show that for k/Δ > 1.764, the Glauber dynamics on k-colorings of a graph on n vertices with maximum degree Δ converges in O(n log n) steps, assuming Δ = Ω(log n) and that the graph is triangle-free. Previously, girth ≥ 5 was needed.As a second application, we give a polynomial-time algorithm for sampling weighted independent sets from the Gibbs distribution of the hard-core lattice gas model at fugacity λ < (1 - ε)e/Δ, on a regular graph G on n vertices of degree Δ = Ω(log n) and girth ≥ 6. The best known algorithm for general graphs currently assumes λ < 2/(Δ - 2).

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 J. E. Steif, Percolation and the hard-core lattice gas model, Stochastic Processes and their Applications 49(2):179--197, 1994.
• 3: G. R. Brightwell and P. Winkler, Random colorings of a Cayley tree. Contemporary combinatorics, 10:247--276, 2002.
• 4: 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
• 5: W. Doeblin, Exposé de la théorie des chaînes simples constantes de Markov à un nombre fini d'états, Revue Mathématique de l'Union Interbalkanique, 2:77--105, 1938.
• 6: M. Dyer, A. Frieze. Randomly colouring graphs with lower bounds on girth and maximum degree. Random Structures and Algorithms, 23 (2):167--179, 2003.
• 7: Martin Dyer , Alan Frieze , Thomas P. Hayes , Eric Vigoda, Randomly Coloring Constant Degree Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.582-589, October 17-19, 2004 [doi>10.1109/FOCS.2004.57]
• 8: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 9: Martin Dyer , Alistair Sinclair , Eric Vigoda , Dror Weitz, Mixing in time and space for lattice spin systems: A combinatorial view, Random Structures & Algorithms, v.24 n.4, p.461-479, July 2004 [doi>10.1002/rsa.v24:4]
• 10: Leslie Ann Goldberg , Russell Martin , Mike Paterson, Strong Spatial Mixing for Lattice Graphs with Fewer Colours, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.562-571, October 17-19, 2004 [doi>10.1109/FOCS.2004.63]
• 11: 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]
• 12: 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
• 13: 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]
• 14: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
• 15: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 16: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 17: T. Lindvall, Lectures on the coupling method, Dover Publications Inc., New York, 2002.
• 18: F. Martinelli, Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997), 93--191, Lecture Notes in Math., 1717, Springer, Berlin, 1999.
• 19: 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]
• 20: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 21: E. Vigoda, Improved bounds for sampling colorings, Journal of Mathematical Physics 41(3): 1555--1569, 2000.
• 22: E. Vigoda, A note on the Glauber dynamics for sampling independent sets. Electron. J. Combin. 8(1), 2001, Research paper 8, 8 pp.