Markov-Chain Monte Carlo

Markov-chain Monte Carlo (MCMC) samples a target distribution through transitions that preserve it. The unknown normalization often cancels from acceptance ratios. The central practical difficulty is that invariance does not imply rapid exploration: a mathematically correct chain can remain trapped for the entire available computation.

Required background. Monte Carlo estimators defines the target expectation and sampling variance.

Metropolis–Hastings transitions

Let $\pi(x)\propto w(x)\geq0$ be the target and $q(y|x)$ a proposal density. Accept a proposal $y$ from state $x$ with probability

$$a(x,y)=\min\left(1,\frac{w(y)q(x|y)}{w(x)q(y|x)}\right).$$

The accepted flux is symmetric:

$$\pi(x)q(y|x)a(x,y) =\min[\pi(x)q(y|x),\pi(y)q(x|y)].$$

This establishes detailed balance for the off-diagonal transitions; rejection completes the diagonal and preserves stationarity. Detailed balance is sufficient, not necessary, for stationarity. Irreducibility and suitable aperiodicity are additional conditions for convergence from general starts.

Start from an allowed configuration with $w(x)>0$ and reject proposals with zero target weight. Compute positive-weight ratios as log weights when exponentials would overflow. Accept if $\log u<\min(0,\log w(y)-\log w(x)+\log q(x|y)-\log q(y|x))$, with $u$ uniform on $(0,1)$. A proposal with zero reverse probability is also rejected; handle that branch explicitly instead of producing an undefined logarithmic ratio.

Rejections are part of the sample

If a move is rejected, retain the current state and record it at the scheduled observation time. Recording only accepted configurations changes the stationary weighting: configurations with a small probability of leaving are undercounted.

For a symmetric proposal the $q$ factors cancel. For a drifted Gaussian or state-dependent proposal width they do not. Omitting the reverse proposal density changes the target, even if the acceptance rate looks reasonable.

An exactly solvable two-state chain

Let the target be $\pi=(3/4,1/4)$ and always propose flipping the state. Then $a(0,1)=1/3$ and $a(1,0)=1$, giving

$$P= \begin{pmatrix} 2/3&1/3\\ 1&0 \end{pmatrix}.$$

Direct multiplication gives $\pi P=\pi$. The second eigenvalue is $-1/3$, so centered observables have alternating correlations proportional to $(-1/3)^t$. The chain is aperiodic because state zero has a self-loop.

If only accepted moves are recorded, the states alternate exactly and the apparent distribution becomes $(1/2,1/2)$. This test catches an error that longer runs cannot repair.

Equilibration and mixing checks

Start multiple chains from meaningfully different configurations. Compare traces of energy, order parameters, conserved-sector labels, and other slow variables. Discard an initial transient only after checking that its length is insensitive to initialization. Agreement of one fast observable does not establish exploration of all modes.

Local moves can preserve an unintended topological or particle-number sector. If that sector is physical, declare the ensemble; otherwise add moves that connect it. At first-order transitions or in a multimodal target, crossing between modes may be far slower than within-mode fluctuations. A tiny within-mode error bar then understates uncertainty.

Tune proposal scales during a separate pilot period. Acceptance rate alone is not an objective: nearly certain tiny moves can mix worse than less frequently accepted large moves. Compare cost per effective independent sample for the actual observables.

Production uncertainty

Estimate integrated autocorrelation times and block observations before ratio or nonlinear error analysis. Report update units explicitly: an attempted single-site move, a sweep, and a full cluster update are not interchangeable time measures.

Exercises

For the displayed chain, what is the integrated autocorrelation time $\tau_{\rm int}=1/2+\sum_{t\geq1}\rho(t)$?

Solution

Using $\rho(t)=(-1/3)^t$, the geometric sum is $-1/4$, hence $\tau_{\rm int}=1/4$. The variance factor $2\tau_{\rm int}=1/2$ is below one because successive observations are anticorrelated. Effective sample size can exceed the raw count for such a particular observable; it is not literally a count of independent stored configurations.

References

• Hastings, W. K., “Monte Carlo sampling methods using Markov chains and their applications,” Biometrika 57, 97–109 (1970), doi:10.1093/biomet/57.1.97 — stationary sampling and proposal correction.