Preliminary list of abstracts

Note: We are using the fantastic MathJax JavaScript library to typeset the mathematics on this web page. You can right-click on a formula to zoom in or to select the rendering engine you like (all under 'Settings'). Under Firefox the default renderer turns out to be MathML (which is quick), but you might prefer the HTML-CSS renderer for more faithful LaTeX rendering. If you encounter any problems with this setup: then please email us!

Click here to go back to the list of abstracts.

Swendsen-Wang beats heat-bath
Keywords: Swendsen-Wang; Rapid mixing; Ising model
Wed, 09:00--09:25
  • Ullrich, Mario (Mathematical Institute, FSU Jena, Germany)

Let $G=(V,E)$ be a graph with finite vertex set $V$ and edge set $E\subseteq\binom{V}{2}$, where $\binom{V}{2}$ is the set of all subsets of $V$ with 2 elements, $N:=\vert{V}\vert$. The Ising model is defined as the set of possible configurations $\Omega_{\rm IS}=\{-1,1\}^V$, together with the probability measure \[ \pi_\beta(\sigma) \;:=\; \pi^{G}_\beta(\sigma) \;=\; \frac1{Z_\beta}\, \exp\biggl\{\beta\sum_{\{u,v\}\in E} \boldsymbol{1}_{\{\sigma(u)=\sigma(v)\}}\biggr\}, \] where $u\leftrightarrow v$ means that $u$ and $v$ are neighbors in $G$, $Z$ is the normalization constant and $\beta\ge0$ is called the inverse temperature.

The goal is to generate an (approximate) sample with respect to $\pi_\beta$ in time that is polynomial in the number of vertices $N$. This is possible with "local" Markov chains (like the Metropolis algorithm) if $\beta$ is below some critical value, i.e. $\beta\le\beta_c$, but impossible for larger values.

We prove that the mixing time of the Swendsen-Wang algorithm cannot be much slower than the mixing time of any local Markov chain if the maximum degree of the underlying graph is bounded. I.e. if the maximal degree of $G$ is $\Delta$, then \[ \lambda(P_{\rm SW}) \;\ge\; c^\Delta\,\lambda(P_{\rm L}), \] where $P_{\rm SW}$ (resp. $P_{\rm L}$) is the transition matrix of the Swendsen-Wang (resp. any local) Markov chain, $\lambda(\cdot)$ denotes the spectral gap and $c$ is some constant that depends only on the temperature. As a consequence we get rapid mixing of the Swendsen-Wang algorithm for the two-dimensional Ising model at high temperatures.

Furthermore we present a modified version of the Swendsen-Wang chain that is applicable for planar graphs $G$ and prove that it is rapidly mixing at all temperatures. This seems to be the first Markov chain for the Ising model that is proved to mix in polynomial time for all temperatures.

[1] C. Borgs, J. T. Chayes, and P. Tetali. Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point. ArXiv e-prints, November 2010.
[2] M. Ullrich. Rapid Mixing of a Modified Swendsen-Wang Algorithm for the Ising Model. in preparation.