Perfect sampling from spatial mixing

2019/07/13 by Feng, Weiming, Guo, Heng, Yin, Yitong · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1907.06033

Abstract

We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with sub-exponential neighborhood growth like ℤ^d, our algorithm achieves linear running time as long as Gibbs sampling is rapidly mixing. As concrete applications, we obtain the currently best perfect samplers for colorings and for monomer-dimer models in such graphs.

Cited by

• Tight Bounds for Sampling q-Colorings via Coupling from the Past

Related

• Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing
• Gibbs Rapidly Samples Colorings of G(n,d/n)
• Rapid Mixing of Gibbs Sampling on Graphs that are Sparse on Average
• Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast
• A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics