Perfect sampling from spatial mixing

Weiming Feng*, Heng Guo, Yitong Yin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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 Z𝑑, 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.
Original languageEnglish
Pages (from-to)678-709
Number of pages32
JournalRandom Structures and Algorithms
Issue number4
Early online date18 Feb 2022
Publication statusPublished - 1 Dec 2022


  • perfect sampling
  • Gibbs distribution
  • spatial mixing


Dive into the research topics of 'Perfect sampling from spatial mixing'. Together they form a unique fingerprint.

Cite this