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

• 成果类型: Article
• 署名作者: Hayes, Thomas P.; Vigoda, Eric
• 署名单位: University of California System; University of California Berkeley; University System of Georgia; Georgia Institute of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051606000000330
• 发表日期: 2006
• 页码: 1297-1318
• 关键词: random-walks; algorithm; bounds; time

摘要

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 >= 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 >= 6. The best known algorithm for general graphs currently assumes lambda < 2/(Delta-2).