Perfect sampling from spatial mixing

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 ${\mathbb{Z}}^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.

References in corpus (5)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Perfect Sampling Using Bounding Chains
• Approximately counting bases of bicircular matroids
• Perfect simulation of the Hard Disks Model by Partial Rejection Sampling
• The Randomness Recycler: A new technique for perfect sampling

Cited by in corpus (2)

• Fundamentals of Partial Rejection Sampling
• Fewer colors for perfect simulation of proper colorings