Perfect sampling from spatial mixing. Issue 4 (18th February 2022)

• Record Type: Journal Article
• Authors: Feng, Weiming; Guo, Heng; Yin, Yitong
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 678
• Page End: 709
• Publication Date: 2022-02-18
• Subjects: Gibbs distribution -- perfect sampling -- spatial mixing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21079
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ℤ 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.