Exponentially slow mixing in the mean-field Swendsen-Wang dynamics

zbMATH Open1403.60063arXiv1702.05797MaRDI QIDQ4608019FDOQ4608019

Authors: Reza Gheissari, Eyal Lubetzky, Yuval Peres 

Publication date: 15 March 2018

Abstract: Swendsen-Wang dynamics for the Potts model was proposed in the late 1980's as an alternative to single-site heat-bath dynamics, in which global updates allow this MCMC sampler to switch between metastable states and ideally mix faster. Gore and Jerrum (1999) found that this dynamics may in fact exhibit slow mixing: they showed that, for the Potts model with $qgeq3$ colors on the complete graph on $n$ vertices at the critical point $$, Swendsen-Wang dynamics has $t_{mathrmmix}geqexp(csqrtn)$. The same lower bound was extended to the critical window $$ around $$ by Galanis et al. (2015), as well as to the corresponding mean-field FK model by Blanca and Sinclair (2015). In both cases, an upper bound of $t_{mathrmmix}leqexp(c^{\prime }n)$ was known. Here we show that the mixing time is truly exponential in $n$: namely, $t_{mathrmmix}geqexp(cn)$ for Swendsen-Wang dynamics when $qgeq3$ and $$, and the same bound holds for the related MCMC samplers for the mean-field FK model when $q>2$.

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

Recommendations

• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• Swendsen-Wang algorithm on the mean-field Potts model
• Swendsen-Wang algorithm on the mean-field Potts model
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cited In (19)

• Swendsen-Wang is faster than single-bond dynamics
• Title not available (Why is that?)
• Tunneling behavior of Ising and Potts models in the low-temperature regime
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Cutoff for the Swendsen-Wang dynamics on the lattice
• Swendsen-Wang algorithm on the mean-field Potts model
• Title not available (Why is that?)
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• 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
• Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions
• Mixing times of critical two-dimensional Potts models
• The critical mean-field Chayes–Machta dynamics
• Sampling Algorithms for Discrete Markov Random Fields and Related Graphical Models
• Swendsen-Wang algorithm on the mean-field Potts model
• The Swendsen-Wang process does not always mix rapidly
• Hardness of identity testing for restricted Boltzmann machines and Potts models
• Metastability of the Potts ferromagnet on random regular graphs

This page was built for publication: Exponentially slow mixing in the mean-field Swendsen-Wang dynamics

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