Perfect sampling from spatial mixing
Authors:
Open Access
- 18 February 2022
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 61 (4) , 678-709
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 subexponential neighborhood growth like , 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.
Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- Exact thresholds for Ising–Gibbs samplers on general graphsThe Annals of Probability, 2013
- Perfect sampling using bounding chainsThe Annals of Applied Probability, 2004
- Mixing in time and space for lattice spin systems: A combinatorial viewRandom Structures & Algorithms, 2004
- Mixing properties and exponential decay for lattice systems in finite volumesThe Annals of Probability, 2004
- Randomly coloring graphs with lower bounds on girth and maximum degreeRandom Structures & Algorithms, 2003
- Random sampling for the monomer–dimer model on a latticeJournal of Mathematical Physics, 2000
- Exact sampling from anti‐monotone systemsStatistica Neerlandica, 1998
- On weak mixing in lattice modelsProbability Theory and Related Fields, 1998
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graphRandom Structures & Algorithms, 1995
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986