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

DOI10.1214/23-AAP1939zbMATH Open1530.05168arXiv2107.10246OpenAlexW3186061378MaRDI QIDQ6180362FDOQ6180362

Reza Gheissari, Antonio Blanca

Publication date: 19 January 2024

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

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.

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)

Cites Work

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

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)