Coupling with the stationary distribution and improved sampling for colorings and independent sets
Coupling with the stationary distribution and improved sampling for colorings and independent sets
复制标题
DOI：
10.1214/105051606000000330
复制
发表时间：
2005-01
期刊：
影响因子：
--
通讯作者：
Thomas P. Hayes;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Thomas P. Hayes;Eric Vigoda
本文提出了一种改进的耦合技术来分析马尔可夫链的混合时间。使用我们的技术，我们简化和扩展以前的结果采样着色和独立集。作为应用，我们证明了当k/Δ > 1.764时，当Δ = Ω（log n）且图是无三角形图时，最大度为Δ的n阶图的k-着色的Glauber动力学收敛时间为O（nlog n）步.作为第二个应用，我们给出了在n阶正则图G上从逸度为λ e/Δ的硬核格子气模型的Gibbs分布中抽取加权独立集的多项式时间算法，G的度为Δ = Ω（log n），围长≥ 6.一般图的最著名算法目前假设λ < 2/（Δ - 2）。
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 λ 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).