Swendsen–Wang algorithm: Difference between revisions

Revision as of 22:40, 24 April 2021

Revision as of 13:22, 12 June 2022

Line 8:

== Description ==

{{Main|Random cluster model}}

The algorithm is non-local in the sense that a single sweep updates a collection of spin variables based on the [[Random cluster model|Fortuin-KasteleynFortuin–Kasteleyn representation]]. The update is done on a "cluster" of spin variables connected by open bond variables that are generated through a [[Percolation theory|percolation]] process, based on the interaction states of the spins.

Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction.

Line 55:

It can be shown that this algorithm leads to equilibrium configurations. To show this, we interpret the algorithm as a [[Markov chain]], and show that the chain is both [[Ergodicity|ergodic]] (when used together with other algorithms) and satisfies [[detailed balance]], such that the equilibrium [[Boltzmann distribution]] is equal to the [[stationary distribution]] of the chain.

Ergodicity means that it is possible to transit from any initial state to any final state with a finite number of updates. It has been shown that the SW algorithm is not ergodic in general (in the thermodynamic limit).<ref>{{Cite journal|last1=Gore|first1=Vivek K.|last2=Jerrum|first2=Mark R.|date=1999-10-01|title=The Swendsen–Wang Process Does Not Always Mix Rapidly|url=https://doi.org/10.1023/A:1004610900745|journal=Journal of Statistical Physics|language=en|volume=97|issue=1|pages=67–86|doi=10.1023/A:1004610900745|bibcode=1999JSP....97...67G|s2cid=189821827|issn=1572-9613}}</ref> Thus in practice, the SW algorithm is usually used in conjunction with single spin-flip algorithms such as the Metropolis-HastingsMetropolis–Hastings algorithm to achieve ergodicity.

The SW algorithm does however satisfy detailed-balance. To show this, we note that every transition between two Ising spin states must pass through some bond configuration in the percolation representation. Let's fix a particular bond configuration: what matters in comparing the probabilities related to it is the number of factors <math>q=e^{-2\beta J}</math> for each missing bond between neighboring spins with the same value; the probability of going to a certain Ising configuration compatible with a given bond configuration is uniform (say <math>p</math>). So the ratio of the transition probabilities of going from one state to another is