Perfect sampling from spatial mixing

Weiming Feng; Heng Guo; Yitong Yin

doi:10.1002/rsa.21079

Perfect sampling from spatial mixing

Weiming Feng^*, Heng Guo, Yitong Yin

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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 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 language	English
Pages (from-to)	678-709
Number of pages	32
Journal	Random Structures and Algorithms
Volume	61
Issue number	4
Early online date	18 Feb 2022
DOIs	https://doi.org/10.1002/rsa.21079
Publication status	Published - 1 Dec 2022

Keywords / Materials (for Non-textual outputs)

perfect sampling
Gibbs distribution
spatial mixing

Access to Document

10.1002/rsa.21079Licence: Creative Commons: Attribution Non-Commercial (CC-BY-NC)

perfect-coloringAccepted author manuscript, 264 KBLicence: All Rights Reserved
Perfect Sampling_FENG_DOA17122021_VOR_CC-BY-NCFinal published version, 1.57 MBLicence: Creative Commons: Attribution Non-Commercial (CC-BY-NC)

https://onlinelibrary.wiley.com/doi/full/10.1002/rsa.21079Licence: Creative Commons: Attribution Non-Commercial (CC-BY-NC)

New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

@article{d42825e064384b50abfeb96659172e12,

title = "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 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.",

keywords = "perfect sampling, Gibbs distribution, spatial mixing",

author = "Weiming Feng and Heng Guo and Yitong Yin",

note = "Funding Information: information European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, 947778We thank Jingcheng Liu for helpful comments. Heng Guo and Yitong Yin want to thank the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley, where part of the work was done. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778). Funding Information: European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, 947778 Funding information Funding Information: We thank Jingcheng Liu for helpful comments. Heng Guo and Yitong Yin want to thank the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley, where part of the work was done. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778). Publisher Copyright: {\textcopyright} 2022 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.",

year = "2022",

month = dec,

day = "1",

doi = "10.1002/rsa.21079",

language = "English",

volume = "61",

pages = "678--709",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "4",

}

TY - JOUR

T1 - Perfect sampling from spatial mixing

AU - Feng, Weiming

AU - Guo, Heng

AU - Yin, Yitong

N1 - Funding Information: information European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, 947778We thank Jingcheng Liu for helpful comments. Heng Guo and Yitong Yin want to thank the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley, where part of the work was done. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778). Funding Information: European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, 947778 Funding information Funding Information: We thank Jingcheng Liu for helpful comments. Heng Guo and Yitong Yin want to thank the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley, where part of the work was done. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778). Publisher Copyright: © 2022 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.

PY - 2022/12/1

Y1 - 2022/12/1

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

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

KW - perfect sampling

KW - Gibbs distribution

KW - spatial mixing

U2 - 10.1002/rsa.21079

DO - 10.1002/rsa.21079

M3 - Article

SN - 1042-9832

VL - 61

SP - 678

EP - 709

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

Perfect sampling from spatial mixing

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this