Perfect sampling from spatial mixing

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 [Formula: see text] , our algorithm achieves l...

Descripción completa

Detalles Bibliográficos
Autores principales: Feng, Weiming, Guo, Heng, Yin, Yitong
Formato: Online Artículo Texto
Lenguaje:English
Publicado: John Wiley & Sons, Inc. 2022
Materias:
Research Articles
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9790483/
https://www.ncbi.nlm.nih.gov/pubmed/36589253
http://dx.doi.org/10.1002/rsa.21079
_version_ 1784859187338018816
author Feng, Weiming
Guo, Heng
Yin, Yitong
author_facet Feng, Weiming
Guo, Heng
Yin, Yitong
author_sort Feng, Weiming
collection PubMed
description 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 [Formula: see text] , 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.
format Online
Article
Text
id pubmed-9790483
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher John Wiley & Sons, Inc.
record_format MEDLINE/PubMed
spelling pubmed-97904832022-12-28 Perfect sampling from spatial mixing Feng, Weiming Guo, Heng Yin, Yitong Random Struct Algorithms Research Articles 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 [Formula: see text] , 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. John Wiley & Sons, Inc. 2022-02-18 2022-12 /pmc/articles/PMC9790483/ /pubmed/36589253 http://dx.doi.org/10.1002/rsa.21079 Text en © 2022 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC. https://creativecommons.org/licenses/by-nc/4.0/This is an open access article under the terms of the http://creativecommons.org/licenses/by-nc/4.0/ (https://creativecommons.org/licenses/by-nc/4.0/) License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited and is not used for commercial purposes.
spellingShingle Research Articles
Feng, Weiming
Guo, Heng
Yin, Yitong
Perfect sampling from spatial mixing
title Perfect sampling from spatial mixing
title_full Perfect sampling from spatial mixing
title_fullStr Perfect sampling from spatial mixing
title_full_unstemmed Perfect sampling from spatial mixing
title_short Perfect sampling from spatial mixing
title_sort perfect sampling from spatial mixing
topic Research Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9790483/
https://www.ncbi.nlm.nih.gov/pubmed/36589253
http://dx.doi.org/10.1002/rsa.21079
work_keys_str_mv AT fengweiming perfectsamplingfromspatialmixing
AT guoheng perfectsamplingfromspatialmixing
AT yinyitong perfectsamplingfromspatialmixing

Ejemplares similares