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