Premium
Perfect sampling from spatial mixing
Author(s) -
Feng Weiming,
Guo Heng,
Yin Yitong
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21079
Subject(s) - mixing (physics) , gibbs sampling , sampling (signal processing) , mathematics , set (abstract data type) , combinatorics , algorithm , computer science , statistical physics , discrete mathematics , statistics , physics , bayesian probability , filter (signal processing) , quantum mechanics , computer vision , programming language
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.