Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
type: Item
instance of: scholarly article
title: Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
zbMATH Open document ID: 1250.60034
author: Prasad Tetali
author: Christian Borgs
author: Jennifer T. Chayes
publication date: 2012-04-26T00:00:00Z
full work available at URL: https://arxiv.org/abs/1011.3058
review text: The authors study the mixing properties of the Swendsen-Wang and heat-bath stochastic algorithms for the \(q\)-state Potts model on \(\mathbb{Z}^{d}, d\geq 2\), providing upper and lower bounds for the variational mixing time of such processes when the system is confined in a box of size \(L\) with periodic boundary conditions. In particular, estimating the inverse gap of the generators of these Markov processes, they prove that, in both cases, the upper bound of the variational mixing time is exponential in \(\beta L^{d-1}\), for any positive \(\beta\). Providing an upper bound for the conductance of such Markov chains, for \(L\) and \(q\) sufficiently large, the authors prove the lower bound of the variational mixing time for the heat-bath dynamics to be also exponential in \(\beta L^{d-1}\), for any positive \(\beta\) larger than or equal to the critical inverse temperature of the model, while, in the case of Swendsen-Wang dynamics, they prove the same bound to hold at criticality. To compute such lower bounds, the authors make use of the FK representation to describe of the configuration space of the system in terms of contours and therefore of Pirogov-Sinai theory.
reviewed by: Michele Gianfelice
Mathematics Subject Classification ID: 60J22
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 68Q87
zbMATH DE Number: 6028170
zbMATH Keywords: Pirogov-Sinai theory
zbMATH Keywords: contour representation
zbMATH Keywords: heat-bath
zbMATH Keywords: Swendsen-Wang
zbMATH Keywords: partition width
MaRDI profile type: Publication
OpenAlex ID: W2152708178
arXiv ID: 1011.3058
cites work: Discontinuity of the magnetization in one-dimensional \(1/| x-y| ^ 2\) Ising and Potts models.
cites work: Q4222745
cites work: On the mixing time of a simple random walk on the super critical percolation cluster
cites work: Glauber dynamics on trees and hyperbolic graphs
cites work: Edge-isoperimetric inequalities in the grid
cites work: A unified approach to phase diagrams in field theory and statistical mechanics
cites work: Q3961493
cites work: Q3809004
cites work: Relaxation to equilibrium for two dimensional disordered Ising systems in the Griffiths phase
cites work: Lifting Markov chains to speed up mixing
cites work: Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
cites work: Q4704792
cites work: On Counting Independent Sets in Sparse Graphs
cites work: Faster mixing and small bottlenecks
cites work: The Swendsen-Wang process does not always mix rapidly
cites work: Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
cites work: Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
cites work: Q4941948
cites work: Mathematical Aspects of Mixing Times in Markov Chains
cites work: Approximate counting, uniform generation and rapidly mixing Markov chains
cites work: Bound on the mass gap for finite volume stochastic Ising models at low temperature
DOI: 10.1007/S00440-010-0329-0
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
description: scientific article