Rapid mixing of Swendsen-Wang dynamics in two dimensions

DOI10.4064/DM502-0-1zbMATH Open1315.60113arXiv1212.4908OpenAlexW3098007057MaRDI QIDQ5496948FDOQ5496948

Authors: Mario Ullrich 

Publication date: 29 January 2015

Published in: Dissertationes Mathematicae (Search for Journal in Brave)

Abstract: We prove comparison results for the Swendsen-Wang (SW) dynamics, the heat-bath (HB) dynamics for the Potts model and the single-bond (SB) dynamics for the random-cluster model on arbitrary graphs. In particular, we prove that rapid mixing of HB implies rapid mixing of SW on graphs with bounded maximum degree and that rapid mixing of SW and rapid mixing of SB are equivalent. Additionally, the spectral gap of SW and SB on planar graphs is bounded from above and from below by the spectral gap of these dynamics on the corresponding dual graph with suitably changed temperature. As a consequence we obtain rapid mixing of the Swendsen-Wang dynamics for the Potts model on the two-dimensional square lattice at all non-critical temperatures as well as rapid mixing for the two-dimensional Ising model at all temperatures. Furthermore, we obtain new results for general graphs at high or low enough temperatures.

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

Recommendations

• Comparison of Swendsen-Wang and heat-Bath dynamics
• Swendsen-Wang is faster than single-bond dynamics
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
• Random cluster dynamics for the Ising model is rapidly mixing
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point

zbMATH Keywords

Markov chain Monte Carlo methodIsing modelPotts modelspectral gaprandom cluster modelrapid mixingSwendsen-Wang dynamics

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Dynamical critical behavior of the Swendson-Wang algorithm: The two-dimensional three-state Potts model revisited
• Title not available (Why is that?)
• The self-dual point of the two-dimensional random-cluster model is critical for \(q \geqslant 1\)
• Time-Dependent Statistics of the Ising Model
• Geometric bounds for eigenvalues of Markov chains
• A graph polynomial for independent sets of bipartite graphs
• Polynomial-Time Approximation Algorithms for the Ising Model
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Exponential decay of connectivities in the two-dimensional Ising model
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Comparison theorems for reversible Markov chains
• Title not available (Why is that?)
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Error bounds for computing the expectation by Markov chain Monte Carlo
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• The equivalence of the logarithmic Sobolev inequality and the Dobrushin- Shlosman mixing condition
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• Approach to equilibrium of Glauber dynamics in the one phase region. II: The general case
• Glauber dynamics on trees and hyperbolic graphs
• Completely analytical interactions: Constructive description
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
• Glauber dynamics for the mean-field Potts model
• Markov chain comparison
• Glauber dynamics on trees: Boundary conditions and mixing time
• Mixing in time and space for lattice spin systems: A combinatorial view
• On weak mixing in lattice models
• Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
• Title not available (Why is that?)
• On the two-dimensional stochastic Ising model in the phase coexistence region near the critical point
• For 2-D lattice spin systems weak mixing implies strong mixing
• Title not available (Why is that?)
• Critical Ising on the square lattice mixes in polynomial time
• Dynamic critical behavior of the Swendsen-Wang algorithm for the three-dimensional Ising model
• Comparison of Swendsen-Wang and heat-Bath dynamics
• Title not available (Why is that?)
• Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• On the Swendsen-Wang dynamics. I: Exponential convergence to equilibrium
• On the Swendsen-Wang dynamics. II: Critical droplets and homogeneous nucleation at low temperature for the two-dimensional Ising model
• Dynamical analysis of low-temperature Monte Carlo cluster algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (27)

• Random-cluster dynamics in \(\mathbb {Z}^2\)
• The Swendsen–Wang dynamics on trees
• Structure and eigenvalues of heat-bath Markov chains
• Swendsen-Wang is faster than single-bond dynamics
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
• Comparison of hit-and-run, slice sampler and random walk Metropolis
• Rapid mixing and Markov bases
• The hit-and-run version of top-to-random
• Title not available (Why is that?)
• Quantitative spectral gap estimate and Wasserstein contraction of simple slice sampling
• Comparison of Swendsen-Wang and heat-Bath dynamics
• Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\)
• Cutoff for the Swendsen-Wang dynamics on the lattice
• On mixing of Markov chains: coupling, spectral independence, and entropy factorization
• Swendsen-Wang algorithm on the mean-field Potts model
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• 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
• The worm process for the Ising model is rapidly mixing
• Algorithmic Pirogov-Sinai theory
• Random cluster dynamics for the Ising model is rapidly mixing
• Random cluster dynamics for the Ising model is rapidly mixing

This page was built for publication: Rapid mixing of Swendsen-Wang dynamics in two dimensions

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