Cluster algorithm

A cluster algorithm for Monte Carlo method simulation updates a correlated group of variables together. Near a critical point, large correlated regions can make single-variable updates mix slowly; collective moves can change those regions more efficiently without changing the intended equilibrium probability distribution.

For a zero-field ferromagnetic Ising model with energy $-J{\sum }_{\{i,j\}}{s}_i{s}_j$, $J>0$, a standard construction independently activates bonds between equal neighboring spins with probability $1-e^{-2\beta J}$. The connected components are then independently assigned spin $+1$ or $-1$ with equal probability. Marginalizing these auxiliary bonds gives the original spin distribution, explaining why the collective update preserves it. The improvement depends on the model and update rule; grouping spins arbitrarily would not establish correct sampling.^[ref]