When you look at the original paper of Swendsen and Wang in 1987: "Nonuniversal critical dynamics in Monte Carlo simulations" it is somewhat mentioned that the proposed algorithm uses percolation theory and the autocorrelation time is significantly reduced:

In this paper, we present an unusal type of dynamics, which violates dynamic universality, and greatly reduces relaxation times in the computer simulation of large systems. Large clusters are changed in a single move, so that the profcess is not local in the usual sense, allowing z to be less than the lower bound...

After proving the necessary condition of detailed balance, they spread some words about the origin of this behavior,

The percolation clusters behave as Fisher droplets and contain a great deal of information".

but only from the publication I cannot understand why this is working. I followed some sources, but obviously not the right one.

My question: Can someone outline how percolation theory comes into play? That the algorithm is working due to the detailed balance condition is not a surprise, but that its autocorrelation time is reduced like this seems curious to me.

the next question would be: What are the main differences between the Wolff and the Swendsen-Wang algorithm? As far as I see it Wolff uses a good choice of the probability so that there are no rejections, is this true?

  • 1
    $\begingroup$ If you want to understand the relation between the Swendsen-Wang algorithm and percolation, relevant keywords are Fortuin-Kasteleyn's random cluster representation and Edwards-Sokal coupling. There exist several mathematical analyses of relaxation properties of this dynamics. See for example Mario Ullrich's PhD thesis and references therein; the latter can be found on his homepage. $\endgroup$ – Yvan Velenik Jul 6 '14 at 17:15
  • $\begingroup$ A quick comment on your very last question: It is true that the Wolff algorithm does not require an additional step to accept/reject the flip of a cluster. The way clusters are built is already perfect, so that it is never necessary to reject a flip. This is completely different from the famous Metropolis algorithm, where proposing what to flip is relatively simple but you need an additional accept/reject step to get the overall correct transition probabilities. $\endgroup$ – Robert Rüger Jul 7 '14 at 0:23

For the ferromagnetic type order-disorder phase transition, the correlation length $\xi$ diverge to infinity as the temperature approach the critical point. What happens physically is that there are fractal clusters of the same spin with size of order $\xi$ that grow to infinity as the temperature approach the critical point.

The SW algorithm is based on this fact to exploit the flipping of percolation clusters in each step to jump to a very distinct state, yet the state is still likely a fractal of spins with the same percolation length scale. It can therefore reduce the autocorrelation time significant. The method is clearly described as:

Beginning with an arbitrary configuration of Potts states, create bonds with a probability $p = 1 - \exp(-K)$ between neighboring states with the same spin.

It is obviously a bond percolation problem with probability $p$ on a network of same spin.

Wolff algorithm can be somehow considered as a generalization of Swendsen-Wang algorithm. Wolff algorithm works in a general case of $O(n)$ model by defining a spin flip operators for the case $n>1$ with continuous spin state such as X-Y model and Heisenberg model. In contrast, Swendsen-Wang algorithm can only work in the case with discrete spin states, i.e. Potts model. Note that Wolff's paper does not describe how it work in the case with no opposite spin (e.g. Potts model). So they works in different cases except Ising model ($n=1$), but the idea is exactly the same by using percolation clusters near phase transition to accelerate the sampling.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.