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

MaRDI QIDQ4608019zbMATH OpenFDO

Authors Reza Gheissari, Eyal Lubetzky, Yuval Peres

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1702.05797, http://dl.acm.org/citation.cfm?id=3175434

Mathematics Subject Classification ID

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

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$.

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

Cited in

(22)

• The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
• The Swendsen-Wang process does not always mix rapidly
• Tunneling behavior of Ising and Potts models in the low-temperature regime
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions
• Cutoff for the Swendsen-Wang dynamics on the lattice
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• Swendsen-Wang algorithm on the mean-field Potts model
• Mixing times of critical two-dimensional Potts models
• scientific article; zbMATH DE number 1916677 (Why is no real title available?)
• Swendsen-Wang is faster than single-bond dynamics
• Hardness of identity testing for restricted Boltzmann machines and Potts models
• Swendsen-Wang algorithm on the mean-field Potts model
• scientific article; zbMATH DE number 7650134 (Why is no real title available?)
• Sampling Algorithms for Discrete Markov Random Fields and Related Graphical Models
• The critical mean-field Chayes–Machta dynamics
• Metastability of the Potts ferromagnet on random regular graphs
• Mean-field Potts and random-cluster dynamics from high-entropy initializations
• Rapid mixing of global Markov chains via spectral independence: the unbounded degree case
• On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics

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)