Content deleted Content added
some corrections: the SW algorithm is not ergodic in general. also added some discussions on the Edwards-Sokal represnetation |
m fixed a typo in the ergodicity discussion |
||
Line 53:
== Correctness ==
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|last=Gore|first=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|issn=1572-9613}}</ref>
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
| |||