Entropy decay in the Swendsen-Wang dynamics on Z^d

DOI10.1214/21-AAP1702zbMATH Open1487.60131arXiv2007.06931OpenAlexW4225114523MaRDI QIDQ2134289FDOQ2134289

Authors: Antonio Blanca, Daniel Parisi, Alistair Sinclair, Eric Vigoda, Pietro Caputo 

Publication date: 6 May 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models on the integer lattice ${mathbbZ}^d$. This dynamics is a widely used Markov chain that has largely resisted sharp analysis because it is non-local, i.e., it changes the entire configuration in one step. We prove that, whenever Strong Spatial Mixing (SSM) holds, the mixing time on any $n$-vertex cube in ${mathbbZ}^d$ is $O(logn)$, and we prove this is tight by establishing a matching lower bound on the mixing time. The previous best known bound was $O(n)$. SSM is a standard condition corresponding to exponential decay of correlations with distance between spins on the lattice and is known to hold in $d=2$ dimensions throughout the high-temperature (single phase) region. Our result follows from a Modified Log-Sobolev Inequality, which expresses the fact that the dynamics contracts relative entropy at a constant rate at each step. The proof of this fact utilizes a new factorization of the entropy in the joint probability space over spins and edges that underlies the Swendsen-Wang dynamics, which extends to general bipartite graphs of bounded degree. This factorization leads to several additional results, including mixing time bounds for a number of natural local and non-local Markov chains on the joint space, as well as for the standard random-cluster dynamics.

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

Recommendations

• Entropy decay in the Swendsen–Wang dynamics on ℤ^d
• Entropy and decay of correlations for real analytic semi-flows
• Decay of correlations and mixing properties in a dynamical system with zero K–S entropy
• Entropy decay of discretized Fokker-Planck equations. I: Temporal semidiscretization
• On uniform decay of the entropy for reaction-diffusion systems
• scientific article; zbMATH DE number 458931
• Entropy decay for interacting systems via the Bochner-Bakry-Émery approach
• Entropy dissipation estimates in a zero-range dynamics
• Entropy in uniformly quasiregular dynamics
• On the density of directional entropy in lattice dynamical systems

zbMATH Keywords

mixing timePotts modelSwendsen-Wanglog-Sobolev

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• The self-dual point of the two-dimensional random-cluster model is critical for \(q \geqslant 1\)
• The Random-Cluster Model
• On logarithmic Sobolev inequalities. With a preface of Dominique Bakry and Michel Ledoux
• Modified logarithmic Sobolev inequalities in discrete settings
• Logarithmic Sobolev inequalities for finite Markov chains
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• 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
• Approach to equilibrium of Glauber dynamics in the one phase region. II: The general case
• Title not available (Why is that?)
• The Swendsen-Wang process does not always mix rapidly
• On log-Sobolev inequalities for infinite lattice systems
• Title not available (Why is that?)
• Dobrushin Conditions and Systematic Scan
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Mixing in time and space for lattice spin systems: A combinatorial view
• On the mixing time of the 2D stochastic Ising model with ``Plus boundary conditions at low temperature
• Quasi-polynomial mixing of the 2D stochastic Ising model with ``plus boundary up to criticality
• On weak mixing in lattice models
• Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields
• For 2-D lattice spin systems weak mixing implies strong mixing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gibbs sampling, exponential families and orthogonal polynomials
• Matrix norms and rapid mixing for spin systems
• Approximate tensorization of entropy at high temperature
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Title not available (Why is that?)
• Sharp phase transition for the random-cluster and Potts models via decision trees
• Book review of: D. A. Levin et al., Markov chains and mixing times. 2nd edition
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Logarithmic Sobolev inequalities in discrete product spaces
• A general lower bound for mixing of single-site dynamics on graphs
• On the Swendsen-Wang dynamics. I: Exponential convergence to equilibrium
• Title not available (Why is that?)
• Dynamical analysis of low-temperature Monte Carlo cluster algorithms
• Random cluster dynamics for the Ising model is rapidly mixing
• Swendsen-Wang algorithm on the mean-field Potts model
• Modified log-Sobolev inequalities for strongly log-concave distributions
• Dynamics for the mean-field random-cluster model
• Random-cluster dynamics in \(\mathbb {Z}^2\)
• A version of Aldous' spectral-gap conjecture for the zero range process
• Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• Block factorization of the relative entropy via spatial mixing
• Spatial mixing and nonlocal Markov chains
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Cutoff for the Swendsen-Wang dynamics on the lattice
• A bounding chain for Swendsen-Wang
• Dynamical coupling between Ising and FK percolation

Cited In (8)

• The Swendsen–Wang dynamics on trees
• Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
• On mixing of Markov chains: coupling, spectral independence, and entropy factorization
• On mixing of Markov chains: coupling, spectral independence, and entropy factorization
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• Mixing in time and space for lattice spin systems: A combinatorial view
• Spatial mixing and nonlocal Markov chains
• Spatial mixing and non-local Markov chains

This page was built for publication: Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\)

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