Home » Markov chain mixing » The power law for the mixing time of Swendsen-Wang dynamics for the Ising model

The power law for the mixing time of Swendsen-Wang dynamics for the Ising model

Let $G=(V,E)$ be a finite connected graph with $n$ nodes. Recall that the Swendsen-Wang dynamics for the Ising model on $G$ proceeds as follows.

Given a spin configuration $\sigma \in \{-1,1\}^V$ , perform Bernoulli percolation with parameter $p$ in $(0,1)$ , restricted to edges $\{v,w\}$ such that $\sigma(v)=\sigma(w)$ . (All other edges are closed.) Then assign each connected component of the resulting random a graph a new spin.

Guo and Jerrum [1] proved that this dynamics always mixes in polynomial time, as conjectured by Sokal. The exponent obtained in [1] is very large. In the special case of the complete graph [2], it is known that the mixing time is $O(n^{1/4})$ for all temperatures (equivalently, for every fixed parameter $p$ in the description above.) Does the same bound apply in all graphs?

REFERENCES
[1] Guo, Heng, and Mark Jerrum (2018). "Random cluster dynamics for the Ising model is rapidly mixing." Annals of applied probability vol. 28, no. 2, pp. 1292-1313.
[2] Long, Yun, Asaf Nachmias, Weiyang Ning, and Yuval Peres (2014). A power law of order $1/4$ for critical mean field Swendsen-Wang dynamics. Memoirs of the American Mathematical Society. Extended Abstract appeared in the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS '07), pp. 205-214. IEEE, 2007.

The power law for the mixing time of Swendsen-Wang dynamics for the Ising model

Send me questions about this open problem

Contact Me