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/\Delta >1.764$, the Glauber dynamics on $k$-colorings of a graph on $n$ vertices with maximum degree $\Delta$ converges in $O(n\log n)$ steps, assuming $\Delta =\Omega (\log n)$ and that the graph is triangle-free. Previously, girth $\ge 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 $\lambda <(1-\epsilon )e/\Delta$, on a regular graph $G$ on $n$ vertices of degree $\Delta =\Omega (\log n)$ and girth $\ge 6$. The best known algorithm for general graphs currently assumes $\lambda <2/(\Delta -2)$.

Published at http://dx.doi.org/10.1214/105051606000000330 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (9)

• Exact thresholds for Ising-Gibbs samplers on general graphs
• Spatial mixing and approximation algorithms for graphs with bounded connective constant
• Randomly coloring planar graphs with fewer colors than the maximum degree
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
• Spatial mixing and approximate counting for Potts model on graphs with bounded average degree
• Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
• Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth