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

The purpose of this paper is to present an improved coupling technique for analyzing the mixing time of Markov chains. The main contributions of the proposed coupling method are summarized as follows: (a) It can be used to simplify and to extend previous results for sampling colorings and independent sets. (b) The proposed coupling technique is using properties of the stationary distribution to avoid worst-case configurations which arise in the traditional approach. As direct consequences of the newly defined complying method, (c) the Glauber dynamics on \(k\)-colorings of a graph on \(n\) vertices, with maximum degree \(\Delta = \Omega(\log n)\), converges in \(O(n \log n)\) steps, provided that the graph is triangle-free. Previously, girth \(\geq 5\) was needed. (d) A polynomial-time algorithm is given for sampling weighted independent sets from the Gibbs distribution of the hard-core lattice gas model, on a regular graph with \(n\) vertices of degree \(\Omega(\log n)\) and girth \(\geq 6\).