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

Reza Gheissari, Eyal Lubetzky, Yuval Peres

Research output: Contribution to journalArticle

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 (J. Stat. Phys. 97 (1999) 67.86) found that this dynamics may in fact exhibit slow mixing: they showed that, for the Potts model with q ≥ 3 colors on the complete graph on n vertices at the critical point βc(q), Swendsen. Wang dynamics has tMIX ≥ exp(c √ n). Galanis et al. (In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015) (2015) 815.828) showed that tMIX ≥ exp(cn1/3) throughout the critical window (βsS) around βc, and Blanca and Sinclair (In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015) (2015) 528.543) established that tMIX ≥ exp(c √ n) in the critical window for the corresponding mean-field FK model, which implied the same bound for Swendsen. Wang via known comparison estimates. In both cases, an upper bound of tMIX ≤ exp(c′ n) was known. Here we show that the mixing time is truly exponential in n: namely, tMIX ≥ exp(cn) for Swendsen-Wang dynamics when q ≥ 3 and β ∈ (βsS), and the same bound holds for the related MCMC samplers for the mean-field FK model when q > 2.

Original languageEnglish (US)
Pages (from-to)68-86
Number of pages19
JournalAnnales de l'institut Henri Poincare (B) Probability and Statistics
Volume56
Issue number1
DOIs
StatePublished - 2020

Keywords

  • FK model
  • Mixing time
  • Potts model
  • Random graphs
  • Swendsen-Wang

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Exponentially slow mixing in the mean-field Swendsen-Wang dynamics'. Together they form a unique fingerprint.

  • Cite this