Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics

DOI10.1214/23-AAP1939MaRDI QIDQ6180362zbMATH OpenOpenAlexFDO

Authors Antonio Blanca, Reza Gheissari

Publication date 19 January 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.10246

zbMATH Keywords

Markov chainsPotts modelrandom graphsrandom-cluster model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Time-dependent percolation in statistical mechanics (82C43)

Abstract: 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 $pin(0,1)$ and a cluster weight $q>0$. We establish that for every $qge1$, the random-cluster Glauber dynamics mixes in optimal $Theta(nlogn)$ steps on $n$-vertex random graphs having a prescribed degree sequence with bounded average branching $gamma$ throughout the full high-temperature uniqueness regime $p<p_u(q,gamma)$. The family of random graph models we consider includes the ErdH{o}s--R'enyi random graph $G(n,gamma/n)$, and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on ErdH{o}s--R'enyi 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(nlogn)$ 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.

Recommendations

• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• Gibbs rapidly samples colorings of \(G(n, d/n)\)

Cites work

• scientific article; zbMATH DE number 4088961 (Why is no real title available?)
• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• scientific article; zbMATH DE number 2023357 (Why is no real title available?)
• scientific article; zbMATH DE number 2042287 (Why is no real title available?)
• scientific article; zbMATH DE number 7768392 (Why is no real title available?)
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Book review of: D. A. Levin et al., Markov chains and mixing times. 2nd edition
• Can extra updates delay mixing?
• Dobrushin Conditions and Systematic Scan
• Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Fast mixing via polymers for random graphs with unbounded degree
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Finitary codings for the random-cluster model and other infinite-range monotone models
• Gibbs measures and phase transitions.
• Glauber dynamics for the mean-field Potts model
• Information percolation and cutoff for the random-cluster model
• Introduction to Random Graphs
• Learning, Local Interaction, and Coordination
• Logarithmic Sobolev inequalities for finite Markov chains
• Matrix norms and rapid mixing for spin systems
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Mixing times of critical two-dimensional Potts models
• Near-optimal fully-dynamic graph connectivity
• On logarithmic Sobolev inequalities. With a preface of Dominique Bakry and Michel Ledoux
• Poisson Cloning Model for Random Graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Quasi-polynomial mixing of critical two-dimensional random cluster models
• Random cluster dynamics for the Ising model is rapidly mixing
• Random-cluster dynamics in \(\mathbb {Z}^2\)
• Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Swendsen-Wang is faster than single-bond dynamics
• The Ising model and percolation on trees and tree-like graphs
• The Swendsen-Wang Dynamics on Trees
• The probability that a random multigraph is simple
• The random cluster model on a general graph and a phase transition characterization of nonamenability
• The random-cluster model on a homogeneous tree
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point

Cited in

(3)

• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs

This page was built for publication: Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180362)