Sampling Algorithms for Lattice Fields

Choose a lattice-field sampler by proving its invariant measure and support coverage first, then comparing its cost for the observable that is actually slow. Local Metropolis and heat-bath steps are broad baselines; cluster updates can remove collective slowing when an exact bond representation exists; HMC makes reversible global proposals and relies on a Metropolis correction; pseudofermions represent positive determinant factors but add solver and approximation controls; tempering and learned proposals require their own exact corrections and matched cost studies. None of these names certifies an implementation.

This chapter develops sampling as finite-regulator Markov-kernel design. It ends at generator correctness, immutable ensemble identity, and conditional performance evidence. The next chapter begins with realized production chains and handles equilibration, autocorrelation estimation, covariance, drift, and uncertainty. General Markov-process theory remains in Volume 1; complex or sign-indefinite measures belong to Chapter 8; physical Hamiltonian evolution belongs to Chapter 9; mutable performance belongs to Research.

Enter this chapter

There is no single prerequisite gate. Choose the entry that matches the claim you need to establish.

Can you distinguish invariant from ergodic?

• Ready: start with Markov-chain sampling and test a transition matrix on the four-spin Ising target.
• Unsure: ask whether a global-spin-flip chain preserves the Boltzmann weights and whether it reaches all sixteen configurations. The answers are “yes” and “no.”
• Repair: review Markov generators, ergodicity, and sampling error.

Can you write the reverse probability of an update?

• Ready: compare local, conditional, cluster, and global families.
• Unsure: derive the Hastings ratio for an asymmetric proposal and the bond probability $1-e^{-2K}$ for a ferromagnetic Ising cluster.
• Repair: begin with the stationarity derivation on the Markov-chain page, then return to the update whose applicability you need.

Can you test a deterministic trajectory as a proposal?

• Ready: enter at hybrid Monte Carlo.
• Unsure: check whether the map is reversible after momentum flip and whether its Jacobian is one before using $e^{-\Delta H}$.
• Repair: review Hamiltonian phase space and reproduce the one-step Gaussian leapfrog fixture.

Does the target contain a fermion determinant?

• Ready: first establish its sign on determinants, Pfaffians, and positivity, then use pseudofermions and solver controls.
• Unsure: decide whether the desired weight is $\det M$, $|\det M|$, $\det(M^\dagger M)$, or a fractional power before writing a Gaussian integral.
• Repair: return to Grassmann integration and the determinant page; a positive pseudofermion representation cannot reconstruct a discarded phase.

Do you already have production configurations?

• Generator not yet certified: use algorithm validation and ensemble provenance.
• Certified configurations, uncertain errors: continue to statistical inference and error budgets.
• Correct but slow generator: identify the slow observable on critical slowing, topological freezing, and acceleration before choosing a remedy.

Choose a route

Goal	Suggested route	Result you should be able to demonstrate
First graduate encounter	Target and kernel → update families → certification	Prove invariance, test communication, and enumerate a finite transition matrix
Implement an exact scalar HMC baseline	Update families → HMC → certification	Verify force, unit Jacobian, reversibility, $\Delta H$, acceptance, and exact scalar moments
Simulate two positive fermion flavors	Determinant positivity → HMC → pseudofermions	Derive the Gaussian determinant identity and exclude rational, solver, and reversal bias
Compare local and cluster methods	Update families → slow modes	State the cluster representation, name the slow observable, and report matched cost per effective estimate
Certify an ensemble before analysis	Markov conditions → certification and provenance	Pass exact, independent, and injected-defect tests and bind files to an immutable generation record
Diagnose topological or multimodal trapping	Certification → slow modes and acceleration	Distinguish a correct slow kernel from a support failure and preserve the target under tempering or exact learned correction
Analyze a realized chain	Certification → Chapter 6	Carry immutable ensemble identity into equilibration, autocorrelation, covariance, and uncertainty analysis

The logic of a sampler claim

Five questions must remain separate.

1. What is the target? The finite action, measure, constraints, boundary conditions, determinant factors, and support define the distribution. An update cannot be judged before this is frozen.
2. Why is it invariant? Detailed balance, exact conditional sampling, or a direct stationarity identity supplies the proof. HMC additionally needs the implemented trajectory’s reverse map and phase-space volume.
3. Can it explore? Invariance does not rule out disconnected sectors, periodic orbits, or proposal support holes. Ergodicity or a suitably qualified communication statement is separate.
4. Are numerical approximations corrected? Force discretization, determinant rationalization, and iterative solves may affect only efficiency when an exact endpoint correction remains valid; otherwise they change the stationary target.
5. How efficiently does the slow observable decorrelate? Only after the first four questions pass do autocorrelation, scaling, training, and cost support an algorithm comparison.

The chapter’s central counterexample is the deterministic global flip of a symmetric Ising target. It preserves the target and satisfies detailed balance, yet it visits only two configurations. Its stationary proof is correct, its coverage is false, and any efficiency measured within its orbit is irrelevant to the full target.

Guide to the six pages

The pages appear in navigation order and form one validation sequence.

1. Markov-Chain Sampling of Lattice Fields defines the positive finite-regulator target, stationarity, detailed balance as a sufficient condition, support, ergodicity, initialization bias, and correlated estimators. It derives Metropolis–Hastings and supplies the exactly enumerable periodic four-spin Ising target. General probability remains in Volume 1; sign problems wait until Chapter 8; uncertainty estimation waits until Chapter 6.
2. Local, Cluster, and Global Update Families derives local Metropolis and exact heat bath, the ferromagnetic random-cluster identity, Wolff boundary balance, overrelaxation composites, and the limited role of multilevel factorization. It states which action structure licenses each update and hands global trajectory proposals to HMC.
3. Hybrid Monte Carlo and Symplectic Molecular Dynamics augments the target with Gaussian momenta and derives the acceptance ratio from an involutive, unit-Jacobian map. A rational one-step Gaussian fixture tests the leapfrog exactly; an interacting scalar fixture tests forces, reversal, energy error, and endpoint correction. Physical Hamiltonian QFT is deliberately separate.
4. Pseudofermions, Determinant Ratios, and Solver Bias derives the positive complex-Gaussian determinant identity, force, Hasenbusch splitting, fractional powers, rational intervals, and residual bounds. It cannot establish determinant positivity and does not address a complex measure; those questions remain in Chapters 4 and 8.
5. Algorithm Validation and Ensemble Provenance combines target, proposal, correction, reversibility, Jacobian, solver, and support checks in one certification procedure. It supplies the governed correctness/performance diagram and semantic matrix, exact discrete and continuous fixtures, six injected defects, and the immutable generation record. Realized-chain inference begins only after this page.
6. Critical Slowing Down, Topological Freezing, and Algorithmic Acceleration diagnoses observable-dependent slow modes and derives exact tempering and learned-proposal corrections. It distinguishes a changed boundary regulator from a kernel acceleration, charges training and replicas to cost, and routes changing production-scale claims to Research.

Conventions and translation checks

The site’s Euclidean sign, measure, Fourier, and lattice conventions are fixed in the global conventions. The following checks are specific to translating sampling literature and implementations.

• A target density is always relative to a stated reference measure. A “Jacobian-free” statement is meaningless until the coordinates and measure are fixed.
• This chapter uses row kernels, $\pi K=\pi$. A source using column probabilities writes $K\pi=\pi$; transpose both transition and balance formulas together.
• The Boltzmann weight is $e^{-S}$. If a source uses energy $E$ and inverse temperature $\beta$, translate $S=\beta E$ before comparing acceptance exponents.
• HMC trajectory time is fictitious algorithm time. It neither estimates Minkowski evolution nor inherits physical initial data.
• The autocorrelation convention is $\tau_{\mathrm{int}}=\frac12+\sum_{t\ge1}\rho(t)$, so $\operatorname{Var}(\bar O)\sim2\tau_{\mathrm{int}}\Gamma(0)/N$. Some sources absorb the factor of two into their definition.
• One “update” is not a portable work unit. A local attempt, full sweep, cluster flip, HMC trajectory, tempering cycle, and flow draw touch different numbers of variables and invoke different target computations.
• “Exact algorithm” means exact invariant target under its numerical contract; it does not mean independent samples, exact arithmetic, zero integration error, or a continuum result.

Every leaf adds a local regulator card immediately before its formulas. Keep those finite-volume and algorithm conventions with any exported benchmark.

The recurring computational test

A useful computational baseline keeps two fixtures deliberately distinct:

• a periodic four-spin Ising model supports exact enumeration of the target and Metropolis or cluster transition kernels;
• a Gaussian HMC system supports rational-arithmetic leapfrog, reversibility, Jacobian, $\Delta H$, and acceptance checks.

The stage then adds an interacting scalar comparison with independent exact or high-precision references and injected failures. It does not merge the discrete cluster fixture with the continuous HMC fixture, and it does not treat one as evidence for the other.

Learned acceleration belongs to a later frontier stage. Every learned-model control, panel, and result is absent from the baseline rather than silently disabled or inferred. This prevents a durable exact-kernel exercise from acquiring a mutable machine-learning performance claim. Dated cross-method assessments belong in Research.

Chapter synthesis

The Metropolis construction works because the accepted probability current is the symmetric minimum of forward and reverse weighted proposals Hastings 1970, pp. 97–109. Heat bath and cluster methods instead use exact conditional representations; the latter can strongly change critical dynamics for suitable spin systems Swendsen and Wang 1987, pp. 86–88, but their applicability is an algebraic property of the action, not a generic license for collective moves.

HMC makes the same correctness structure geometric. A symmetric splitting yields a reversible volume-preserving proposal, and the endpoint Metropolis test corrects finite step-size energy error Duane et al. 1987, pp. 216–222. Solver approximations and pseudofermion forces are safe only to the extent that this implemented reverse-map and endpoint-target contract remains true.

Acceleration then becomes conditional evidence. Topological freezing can dominate one observable while leaving others less affected Schaefer, Sommer, and Virotta 2011, pp. 93–119. Tempering enlarges the target and corrects swaps; open boundaries change the finite regulator; learned proposals either retain an exact density correction or remain approximate and require bias tests. These are different scientific claims.

The durable conclusion is an order of operations: freeze the target, prove stationarity, test support, bound numerical approximation, falsify the implementation with known defects, preserve its immutable identity, and only then compare cost for a named observable. Chapter 6 starts from the configurations that survive that sequence.

Review the chapter

Retrieval — name the independent gates. State target, stationarity, coverage, numerical exactness, and performance in one sentence each. A successful answer gives a distinct failure example for every gate. Repair with the certification matrix.

Derivation — recover two acceptance rules. Derive the Hastings ratio for a state-dependent proposal and the HMC ratio for an involutive unit-Jacobian map. A successful answer shows the symmetric accepted current in both cases and identifies where the proposal density or Jacobian enters.

Representation change — translate a pseudofermion claim. Given “one flavor is simulated by $\det(M^\dagger M)^{1/2}$,” state the positivity, fractional-power, rational-interval, and endpoint-correction assumptions needed before calling the algorithm exact. Repair with pseudofermions.

Failure diagnosis — challenge high acceptance. A learned independence proposal reports 99% acceptance but was trained in one topological sector. Explain why this is compatible with complete failure. A successful answer identifies the support hole and proposes sector-separated starts or direct support probes.

Comparison — local versus cluster. Compare single-spin Metropolis and Wolff updates near an Ising critical point. A successful answer first verifies the common target and cluster representation, then counts comparable work and names the observable whose scaling is measured.

Transfer — certify a fresh global map. A proposal composes a reversible leapfrog trajectory with a learned coordinate rescaling. A successful answer measures the full reverse map and includes the rescaling Jacobian or rejects the standard HMC acceptance formula.

Synthesis — hand an ensemble to Chapter 6. List what is immutable at generation and what may be chosen during analysis. A successful answer preserves target, code, algorithm, randomness, and file hashes while routing equilibration, autocorrelation, resampling, covariance, and fits to the analysis record.

Learning outcomes

You have met the chapter outcomes when you can:

• certify a lattice-field generator against analytic or independently implemented references, including an injected defect that the planned test detects; and
• distinguish invariant-kernel correctness, support and ergodicity, realized-chain equilibration, observable autocorrelation, and total computational cost without using one as evidence for another.

Exercises

1. Construct an exact but inefficient kernel. On the four-spin Ising ring, mix a correct single-site Metropolis step with probability $\varepsilon$ and the identity with probability $1-\varepsilon$. Prove invariance and predict the small-$\varepsilon$ efficiency.

Solution

If $K_M$ preserves $\pi$, then $K_\varepsilon=(1-\varepsilon)I+\varepsilon K_M$ satisfies $\pi K_\varepsilon=(1-\varepsilon)\pi+\varepsilon\pi=\pi$. For $\varepsilon>0$, its communication properties match $K_M$, but every nontrivial eigenvalue $\lambda$ becomes $1-\varepsilon+\varepsilon\lambda$. Relaxation gaps shrink by $\varepsilon$, so autocorrelation times grow approximately as $1/\varepsilon$ for slow modes. Correctness survives while efficiency becomes arbitrarily poor.

2. Locate an HMC Jacobian error. Insert the map $q_1\mapsto c q_1$, $p_1\mapsto p_1$ with $c>0$ into a trajectory. What acceptance factor is missing from standard HMC, and what happens when $c=1$?

Solution

The map has phase-space Jacobian $c$. An involutive construction using the map and its inverse must include this change-of-variables factor in the forward/reverse Metropolis ratio; $e^{-\Delta H}$ alone is insufficient. At $c=1$, the factor is one and this particular obstruction disappears, although reversibility and the rest of the trajectory still require testing.

3. Design a fair learned-proposal comparison. Give the minimum cost and correctness fields needed to compare a flow proposal with HMC on a multimodal scalar target.

Solution

Match action, volume, boundaries, parameters, observables, precision, and hardware. For both methods report exact-reference agreement, sector coverage, failures, target evaluations, and cost per effective estimate. HMC additionally reports force calls, reversal, $\Delta H$, and acceptance. The flow reports training data and target calls, tuning trials, model and Jacobian evaluation, exact-correction acceptance or reweighting tails, inference cost, and an amortization horizon. A speed claim is conditional on all correctness fields passing.

References

• Duane, S., Kennedy, A. D., Pendleton, B. J., and Roweth, D. (1987). “Hybrid Monte Carlo.” Physics Letters B 195(2), 216–222. doi:10.1016/0370-2693(87)91197-X.
• 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.
• Schaefer, S., Sommer, R., and Virotta, F. (2011). “Critical slowing down and error analysis in lattice QCD simulations.” Nuclear Physics B 845(1), 93–119. doi:10.1016/j.nuclphysb.2010.11.020; 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.