Local, Cluster, and Global Update Families

Local, conditional, cluster, overrelaxation, multilevel, and global updates are not interchangeable accelerators. Each is exact only under a specific relation between the target action and the proposal: Metropolis corrects a known proposal ratio, a heat bath samples an exact conditional, a cluster move uses a model-specific bond representation, overrelaxation preserves a conditional energy surface, and a global or learned move needs a computable reverse density or another exact correction. The right comparison is therefore “correct for this target, then cost per effective estimate for this observable,” never acceptance rate alone.

Required background. Markov-chain sampling of lattice fields supplies target invariance, detailed balance, support, and ergodicity tests.

Helpful background. Brownian motion, Langevin dynamics, and Fokker–Planck equations supplies the continuous stochastic dynamics that underlies some local and global proposals.

Local proposals and exact conditionals

Let $\phi=(\phi_x,\phi_{\setminus x})$ and $\pi(\phi)\propto e^{-S(\phi)}$. A local Metropolis step proposes only $\phi_x'\sim q_x(\phi_x'\mid\phi)$ and accepts with

$$\alpha(\phi,\phi')=\min\!\left\{1, e^{-[S(\phi')-S(\phi)]} \frac{q_x(\phi_x\mid\phi')}{q_x(\phi_x'\mid\phi)} \right\}.$$

The update is inexpensive and broadly applicable, but information propagates only through repeated local steps. A heat-bath step instead draws exactly from

$$\phi_x'\sim \pi(d\phi_x\mid\phi_{\setminus x}).$$

The reverse-density factor in the first rule is the general Metropolis–Hastings correction Hastings 1970, pp. 97–109.

Its accepted transition has no rejection. Conditional factorization proves invariance: integrating the old $\phi_x$ against $\pi(d\phi_x\mid\phi_{\setminus x})$ and drawing the new one from the same distribution leaves the joint target unchanged. Zero rejection does not make a heat bath independent sampling; neighboring variables remain fixed during the step.

Local regulator and convention card. Discrete formulas use the periodic ferromagnetic Ising action $S=-K\sum_{\langle xy\rangle}s_xs_y$ with $K\ge0$ and each undirected bond counted once. The exact comparison uses the four-site ring of the preceding page. Scalar overrelaxation uses a real field whose one-site conditional action is $S_x=\frac{A_x}{2}(\phi_x-h_x)^2+\text{constant}$ with $A_x>0$ and $h_x$ fixed by the neighboring sites. One sweep means one attempted update per site on average; a cluster step is also reported in flipped sites so work is comparable.

For the four-spin ring, the local field at site $i$ is $H_i=K(s_{i-1}+s_{i+1})$. The exact conditional probability is

$$P(s_i'=\sigma\mid s_{\setminus i}) =\frac{e^{\sigma H_i}}{2\cosh H_i}, \qquad \sigma=\pm1.$$

This gives an exactly enumerable heat-bath transition matrix. It must satisfy the same sixteen-state stationarity residual and closed-form bond correlation as the single-spin Metropolis chain, although its spectrum and autocorrelations differ.

The figure below shows what remains common when the proposal changes. Follow any local, conditional, cluster, or global branch through its own exactness argument before comparing coverage or speed.

Update families differ in the identity that establishes stationarity: a reverse proposal ratio, an exact conditional, a cluster representation, or a corrected global density. Their efficiency is comparable only after that identity and support coverage pass. Original schematic, not to scale.

The canonical sampler correctness and performance matrix states the proposal, correction, coverage, failure, and cost fields side by side.

Collective clusters from a bond representation

For a ferromagnetic Ising bond, the identity

$$e^{Ks_xs_y}=e^K\big[(1-p)+p\,\delta_{s_x,s_y}\big], \qquad p=1-e^{-2K},$$

introduces an auxiliary occupied bond only between like spins. Conditional on the spins, occupy each like-spin bond independently with probability $p$; conditional on the resulting bond clusters, assign each cluster a common sign with equal probability. Alternating these two exact conditionals is the Swendsen–Wang update of Swendsen and Wang 1987, pp. 86–88.

The Wolff variant chooses a seed, grows one connected cluster using the same bond probability, and flips it. Its detailed-balance proof can be seen directly at the boundary. Suppose $s'$ is obtained by flipping a cluster $C$. Internal activated-bond probabilities agree in the forward and reverse constructions. Only boundary bonds with one end in $C$ can change their aligned status. Each aligned boundary bond that must remain inactive supplies $1-p=e^{-2K}$. Consequently the ratio of forward and reverse cluster-growth probabilities is

$$\frac{P(s\to s')}{P(s'\to s)} =e^{-2K(N_+-N_-)} =e^{-[S(s')-S(s)]} =\frac{\pi(s')}{\pi(s)},$$

where $N_+$ and $N_-$ count aligned boundary bonds before and after the flip. Thus the rejection-free cluster move obeys detailed balance. This construction and its applicability to $O(n)$ reflections are developed in Wolff 1989, pp. 361–364.

The assumption $K\ge0$ is structural. Using $p=1-e^{-2K}$ for an antiferromagnetic bond makes $p<0$; applying the ferromagnetic connectivity rule unchanged to frustration or to an action without the required positive random-cluster representation is not an approximation—it is not a probability kernel.

Overrelaxation, composites, and global moves

For the quadratic one-site conditional above, the deterministic reflection

$$\phi_x'=2h_x-\phi_x$$

leaves $(\phi_x-h_x)^2$ and the unit Jacobian invariant. It is an involution, so it obeys detailed balance with respect to the conditional measure. But repeated reflections can be periodic and cannot by themselves refresh the radial or energy-like degree of freedom. A practical kernel composes overrelaxation with a stochastic heat-bath or Metropolis step. If $K_1$ and $K_2$ each preserve $\pi$, then their ordered composition does too:

$$\pi K_1K_2=(\pi K_1)K_2=\pi K_2=\pi.$$

The composition need not itself be reversible, which illustrates again that invariance is the essential condition.

A global proposal can update every field variable at once. If it has a tractable density $q(\phi'\mid\phi)$ and adequate support, the full Metropolis–Hastings ratio makes it exact. Hybrid Monte Carlo is a particularly important global construction and is derived on the next page. Tempering and exactly corrected learned proposals appear only after slow-mode diagnostics on the acceleration page.

Multilevel methods serve a different purpose. When locality permits an observable or conditional expectation to factor across subdomains with fixed boundaries, nested conditional averages can reduce variance exponentially for suitable long-distance observables, as demonstrated by Lüscher and Weisz 2001, §§2–4. This does not create a universal global transition for arbitrary actions or fermion determinants. The frozen boundary fields, conditional independence statement, and recombination formula are part of the method contract.

Exactly checking update families on the same target

The four-spin ring provides a fair correctness fixture.

1. Enumerate all sixteen target weights and exact observables $\langle m\rangle=0$ and $C_1=4\sinh(4K)/Z_4$.
2. Construct separate $16\times16$ matrices for random-site Metropolis, random-site heat bath, and one-cluster Wolff updates. For the cluster matrix, sum over seed and bond-growth randomness rather than replacing it by sampled frequencies.
3. Check row normalization, $\pi K-\pi$, and pairwise balance. Confirm that the three matrices have different subleading eigenvalues even though the invariant vector agrees.
4. In longer runs, report work in proposed or flipped sites, not merely “updates.” Compare the variance of $C_1$ times the measured work per configuration. For a critical-size study, repeat over $L$ at matched $K$ or matched $\xi/L$ and identify the slow observable before fitting a scaling law.

The physical expectation is conditional: cluster moves can dramatically reduce magnetization-like critical slowing for ferromagnetic spin models, while a local method may remain competitive away from criticality or for observables whose slow mode does not overlap strongly with the cluster dynamics. An exact four-spin success establishes implementation correctness, not large-volume superiority.

Adversarial failures

A missing periodic bond. Construct clusters on bonds $(1,2),(2,3),(3,4)$ but evaluate the target with the additional bond $(4,1)$. The growth probability no longer accounts for every action term changed by the flip. Exact stationarity fails even though configurations still look plausible.

A cluster rule outside its representation. Reuse the ferromagnetic Ising activation probability in a frustrated model. A negative or ad hoc-clipped bond probability invalidates the conditional derivation; a high flip rate cannot restore it.

Overrelaxation without refreshment. Run only $\phi_x\mapsto2h_x-\phi_x$ on a quadratic target. Energy-like invariants and periodic orbits remain. Combine it with a stochastic kernel and verify communication rather than assuming that large moves imply ergodicity.

An unfair performance comparison. Count one Wolff cluster as one unit of work even when it flips $O(V)$ spins, but count a local sweep as $V$ units. The resulting speedup is a unit-conversion artifact. Report field visits, force or action evaluations, and cost per effective observable estimate under matched targets and hardware.

Observable-level validation checklist

• State the algebraic representation that licenses the update: proposal ratio, exact conditional, positive cluster bonds, invariant reflection, or subdomain factorization.
• Include every boundary and interaction term in both target and update; test periodic and open fixtures separately.
• Verify invariance and support on an exactly enumerable lattice, then compare at least two observables with different symmetry and slow-mode overlap.
• Combine deterministic or sector-preserving moves with a proven communication mechanism, and test deliberately separated starts.
• Inject a missing bond, wrong cluster probability, or removed refresh step and require an exact residual or cross-start comparison to detect it.
• Compare performance only after correctness passes, using matched targets, volumes, observable definitions, work units, and uncertainty procedures.

Learning outcomes

After completing this page, you should be able to:

• derive why one local update and one collective update preserve a specified lattice target, including the assumptions that limit their applicability; and
• compare update families by cost per effective estimate and failure behavior rather than by raw acceptance, update count, or wall time alone.

Exercises

1. Derive the heat bath. For the four-spin ring, show that the stated conditional distribution of $s_i$ is normalized and obeys detailed balance when the updated site is chosen uniformly.

Solution

At fixed neighbors, the only $s_i$-dependent Boltzmann factor is $e^{K s_i(s_{i-1}+s_{i+1})}=e^{s_iH_i}$. Summing over $s_i=\pm1$ gives $2\cosh H_i$. For configurations $s,s'$ differing only at $i$, uniform site selection cancels in the ratio, and $\pi(s)P(s_i'\mid s_{\setminus i})=\pi(s_{\setminus i})P(s_i\mid s_{\setminus i})P(s_i'\mid s_{\setminus i})$, which is symmetric in $s_i,s_i'$.

2. Test the overrelaxation composite. Let $K_R$ be the deterministic conditional reflection and $K_H$ an exact heat bath. Prove that $K_RK_H$ is invariant, and explain why it need not satisfy detailed balance.

Solution

Both kernels separately preserve $\pi$, so $\pi K_RK_H=(\pi K_R)K_H=\pi$. Reversibility would require the adjoint relation $(K_RK_H)^*=K_RK_H$. Because each factor is self-adjoint but $(K_RK_H)^*=K_HK_R$, detailed balance holds only if the two kernels commute. Ordered site updates generally do not.

References

• Hastings, W. K. (1970). “Monte Carlo sampling methods using Markov chains and their applications.” Biometrika 57(1), 97–109. doi:10.1093/biomet/57.1.97.
• Lüscher, M., and Weisz, P. (2001). “Locality and exponential error reduction in numerical lattice gauge theory.” Journal of High Energy Physics 09, 010. doi:10.1088/1126-6708/2001/09/010; Open PDF.
• Swendsen, R. H., and Wang, J.-S. (1987). “Nonuniversal critical dynamics in Monte Carlo simulations.” Physical Review Letters 58(2), 86–88. doi:10.1103/PhysRevLett.58.86.
• Wolff, U. (1989). “Collective Monte Carlo updating for spin systems.” Physical Review Letters 62(4), 361–364. doi:10.1103/PhysRevLett.62.361.