SAMPLING FROM POTTS ON RANDOM GRAPHS OF UNBOUNDED DEGREE VIA RANDOM-CLUSTER DYNAMICS

• 成果类型: Article
• 署名作者: Blanca, Antonio; Gheissari, Reza
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; University of California System; University of California Berkeley; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP1939
• 发表日期: 2023
• 页码: 4997-5049
• 关键词: swendsen-wang; glauber dynamics; MODEL; algorithms; TREE

摘要

We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability p is an element of (0,1) and a cluster weight q > 0. We establish that for every q >= 1, the random-cluster Glauber dynamics mixes in optimal Theta(n log n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching gamma throughout the full high-temperature uniqueness regime p < pu(q, gamma).The family of random graph models we consider includes the Erd & odblac;s-R & eacute;nyi random graph G(n, gamma/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erd & odblac;s-R & eacute;nyi random graphs for the full tree uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the largest degree) for the Potts Glauber dynamics, in the same settings where our Theta(n log n) bounds for the random-cluster Glauber dynamics apply. This reveals a novel and significant computational advantage of random-cluster based algorithms for sampling from the Potts model at high temperatures.