Rapid mixing of Swendsen-Wang dynamics in two dimensions
From MaRDI portal
Publication:5496948
Markov chain Monte Carlo methodIsing modelPotts modelspectral gaprandom cluster modelrapid mixingSwendsen-Wang dynamics
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)
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.
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
Cites work
- scientific article; zbMATH DE number 5294801 (Why is no real title available?)
- scientific article; zbMATH DE number 4007430 (Why is no real title available?)
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 3574390 (Why is no real title available?)
- scientific article; zbMATH DE number 1305538 (Why is no real title available?)
- scientific article; zbMATH DE number 1559583 (Why is no real title available?)
- scientific article; zbMATH DE number 1369837 (Why is no real title available?)
- scientific article; zbMATH DE number 919621 (Why is no real title available?)
- A graph polynomial for independent sets of bipartite graphs
- 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
- Comparison of Swendsen-Wang and heat-Bath dynamics
- Comparison theorems for reversible Markov chains
- Completely analytical interactions: Constructive description
- Critical Ising on the square lattice mixes in polynomial time
- Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
- Dynamic critical behavior of the Swendsen-Wang algorithm for the three-dimensional Ising model
- Dynamical analysis of low-temperature Monte Carlo cluster algorithms
- Dynamical critical behavior of the Swendson-Wang algorithm: The two-dimensional three-state Potts model revisited
- Error bounds for computing the expectation by Markov chain Monte Carlo
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Explicit error bounds for lazy reversible Markov chain Monte Carlo
- Exponential decay of connectivities in the two-dimensional Ising model
- For 2-D lattice spin systems weak mixing implies strong mixing
- Geometric bounds for eigenvalues of Markov chains
- Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
- Glauber dynamics for the mean-field Potts model
- Glauber dynamics on trees and hyperbolic graphs
- Glauber dynamics on trees: Boundary conditions and mixing time
- Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
- Markov chain comparison
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Mixing in time and space for lattice spin systems: A combinatorial view
- Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
- 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
- On the two-dimensional stochastic Ising model in the phase coexistence region near the critical point
- On weak mixing in lattice models
- Polynomial-Time Approximation Algorithms for the Ising Model
- SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
- Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
- The equivalence of the logarithmic Sobolev inequality and the Dobrushin- Shlosman mixing condition
- The self-dual point of the two-dimensional random-cluster model is critical for q 1
- Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
- Time-Dependent Statistics of the Ising Model
- Tractability of multivariate problems. Volume II: Standard information for functionals.
Cited in
(27)- Random-cluster dynamics in \(\mathbb {Z}^2\)
- Structure and eigenvalues of heat-bath Markov chains
- The Swendsen–Wang dynamics on trees
- Swendsen-Wang is faster than single-bond dynamics
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- 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
- Quantitative spectral gap estimate and Wasserstein contraction of simple slice sampling
- scientific article; zbMATH DE number 1559583 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 7378644 (Why is no real title available?)
- Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
- scientific article; zbMATH DE number 7650134 (Why is no real title available?)
- 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)
