skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics
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 ∈ (0,1) and a cluster weight q > 0. We establish that for every q ≥ 1, the random-cluster Glauber dynamics mixes in optimal Θ(nlog n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching γ throughout the full high-temperature uniqueness regime p < p_u(q,γ). The family of random graph models we consider includes the Erdős-Rényi random graph G(n,γ/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erdős-Ré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 Θ(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.  more » « less
Award ID(s):
2143762
PAR ID:
10592158
Author(s) / Creator(s):
;
Editor(s):
Chakrabarti, Amit; Swamy, Chaitanya
Publisher / Repository:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Date Published:
Volume:
245
ISSN:
1868-8969
ISBN:
978-3-95977-249-5
Page Range / eLocation ID:
24:1-24:15
Subject(s) / Keyword(s):
Potts model random-cluster model random graphs Markov chains mixing time tree uniqueness Theory of computation → Random walks and Markov chains Theory of computation → Generating random combinatorial structures Theory of computation → Random network models Mathematics of computing → Probabilistic algorithms Mathematics of computing → Markov processes
Format(s):
Medium: X Size: 15 pages; 826553 bytes Other: application/pdf
Size(s):
15 pages 826553 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; (, Communications in Mathematical Physics)
    Abstract We study the performance of Markov chains for theq-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of “phases” (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the two relevant phases for theq-state Potts model on thed-regular random graph for all integers$$q,d\ge 3$$ q , d ≥ 3 , and establish that for an interval of temperatures, delineated by the uniqueness and a broadcasting threshold on thed-regular tree, the two phases coexist (as possible metastable states). The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for largeqand$$d\ge 5$$ d ≥ 5 . Based on our new structural understanding of the model, our second contribution is to obtain metastability results for two classical Markov chains for the Potts model. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, by showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local and more elaborate Swendsen–Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph “planting” argument combined with delicate bounds on random-graph percolation. 
    more » « less
  2. ; ; ; (, International Colloquium on Automata, Languages, and Programming (ICALP))
    Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L_p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS’13). The non-linearity of L_p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L_p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n, d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime. 
    more » « less
  3. ; ; ; (, ICALP 2022)
    Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L^p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of L^p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L^p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n,d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime. 
    more » « less
  4. ; ; ; (, ACM Transactions on Algorithms)
    Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimalO(nlogn)sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on usingLp-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS’13). The non-linearity ofLp-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture theLp-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graphG (n, d/n), where the previously known algorithms run in timenO(logd) or applied only to larged. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constantd, throughout the uniqueness regime. 
    more » « less
  5. ; ; ; ; ; (, Random Structures & Algorithms)
    Efficient algorithms for approximate counting and sampling in spin systems typically apply in the so‐called high‐temperature regime, where the interaction between neighboring spins is “weak.” Instead, recent work of Jenssen, Keevash, and Perkins yields polynomial‐time algorithms in the low‐temperature regime on bounded‐degree (bipartite) expander graphs using polymer models and the cluster expansion. In order to speed up these algorithms (so the exponent in the run time does not depend on the degree bound) we present a Markov chain for polymer models and show that it is rapidly mixing under exponential decay of polymer weights. This yields, for example, an‐time sampling algorithm for the low‐temperature ferromagnetic Potts model on bounded‐degree expander graphs. Combining our results for the hard‐core and Potts models with Markov chain comparison tools, we obtain polynomial mixing time for Glauber dynamics restricted to appropriate portions of the state space. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email