Rapid mixing of Gibbs sampling on graphs that are sparse on average

DOI10.1002/rsa.20276zbMath1216.60054arXiv0704.3603OpenAlexW3083665005MaRDI QIDQ3055775

Elchanan Mossel, Allan Sly

Publication date: 9 November 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Ising modelmixing timerandom graphGibbs sampling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Related Items

Spatial mixing and the connective constant: optimal bounds, Exact thresholds for Ising-Gibbs samplers on general graphs, Approximating partition functions of the two-state spin system, Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics, Unnamed Item, Metastability of the Ising model on random regular graphs at zero temperature, Uniqueness for the 3-state antiferromagnetic Potts model on the tree, Gibbs rapidly samples colorings of \(G(n, d/n)\), Random-cluster dynamics on random regular graphs in tree uniqueness, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, Deterministic counting of graph colourings using sequences of subgraphs, Unnamed Item

Cites Work

• Unnamed Item
• The logarithmic Sobolev inequality for discrete spin systems on a lattice
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• A note on the Glauber dynamics for sampling independent sets
• Glauber dynamics on trees: Boundary conditions and mixing time
• Robust phase transitions for Heisenberg and other models on general trees
• The Ising model and percolation on trees and tree-like graphs
• On log-Sobolev inequalities for infinite lattice systems
• Randomly coloring constant degree graphs
• Counting independent sets up to the tree threshold
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Polynomial-Time Approximation Algorithms for the Ising Model
• On Counting Independent Sets in Sparse Graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Mixing in time and space for lattice spin systems: A combinatorial view
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• On Markov Chains for Independent Sets
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs