Student Probability Seminar

---

Critical Slowdown of Swendsen-Wang Dynamics

Speaker: Reza Gheissari

Location: Warren Weaver Hall 905

Date: Monday, February 27, 2017, 11 a.m.

Synopsis:

Consider the \(q\)-state mean-field Potts model, a probability distribution \(\pi\) on \(\{1,...,q\}^{n}\) with \(\pi(\sigma)\propto \exp(\beta H(\sigma))\) where \(H(\sigma)\) counts the number of pairs of vertices in the same state. It is a canonical model of statistical physics generalizing the \(q=2\) case (Ising Curie--Weiss). In this talk, we will introduce the Swendsen--Wang dynamics, introduced in the 1980's, as a Markov chain reversible w.r.t. \(\pi\) that utilizes the Erdos--Renyi random graph \(G(n,p)\) to make global changes and jump over the energy barriers in the Potts landscape. As a result, for some time, physicists believed the Swendsen--Wang algorithm to always be a fast (polynomial time) MCMC sampler of the Ising/Potts model. In 1999, Gore and Jerrum found that when \(q\geq 3\), at the critical temperature \(\beta_c(q)\), the dynamics is in fact slow: \(t_{\mathrm {mix}}\geq \exp(c\sqrt n)\). We present that proof, then with some new random graph estimates, show that in fact, there, \(t_{\mathrm{mix}}\) is truly exponential in \(n\): \(\log t_{\mathrm {mix}} \asymp n\). Joint work with E. Lubetzky and Y. Peres.