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

DOI10.1214/21-AAP1702MaRDI QIDQ2134289zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(8)

• Spatial mixing and non-local Markov chains
• 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

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)