Comparison of Swendsen-Wang and heat-Bath dynamics

DOI10.1002/RSA.20431zbMATH Open1272.82009arXiv1105.3665OpenAlexW3122801050MaRDI QIDQ2841682FDOQ2841682

Authors: Mario Ullrich 

Publication date: 26 July 2013

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

Abstract: We prove that the spectral gap of the Swendsen-Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single-spin dynamics. This implies rapid mixing of the Swendsen-Wang process for the two-dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen-Wang algorithm for planar graphs and prove rapid mixing for the two-dimensional Potts models at all non-critical temperatures.

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

Recommendations

• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Swendsen-Wang is faster than single-bond dynamics
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point

zbMATH Keywords

Ising/Potts modelspectral gapSwendsen-Wangheat-bath

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Critical phenomena in equilibrium statistical mechanics (82B27)

Cites Work

• Probability on graphs. Random processes on graphs and lattices.
• Logarithmic Sobolev inequalities for finite Markov chains
• Comparison theorems for reversible Markov chains
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• Glauber dynamics on trees and hyperbolic graphs
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
• On the mixing time of the 2D stochastic Ising model with ``Plus boundary conditions at low temperature
• On weak mixing in lattice models
• For 2-D lattice spin systems weak mixing implies strong mixing
• Critical Ising on the square lattice mixes in polynomial time
• Title not available (Why is that?)
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Dynamical analysis of low-temperature Monte Carlo cluster algorithms
• A bounding chain for Swendsen-Wang
• Title not available (Why is that?)

Cited In (17)

• Random-cluster dynamics in \(\mathbb {Z}^2\)
• Hit-and-run for numerical integration
• Swendsen-Wang is faster than single-bond dynamics
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
• Tunneling behavior of Ising and Potts models in the low-temperature regime
• Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Cutoff for the Swendsen-Wang dynamics on the lattice
• Title not available (Why is that?)
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions
• Sampling Algorithms for Discrete Markov Random Fields and Related Graphical Models
• The worm process for the Ising model is rapidly mixing
• Random cluster dynamics for the Ising model is rapidly mixing

This page was built for publication: Comparison of Swendsen-Wang and heat-Bath dynamics

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