4. Markov chains and Metropolis–Hastings balance
Position in the course: Lesson 4 of 10. Complete the preceding derivation and use the explained exercises to check understanding.
Prerequisites: Conditional probability; importance sampling
Learning goal: explain the mathematical steps, reproduce the analytical examples, and state the conditions under which the conclusions hold.
1. Build a transition kernel including rejection
A Markov chain draws its next state using the present state. Write a row-stochastic matrix \(P_{xy}\), with \(\sum_yP_{xy}=1\). Stationarity is the global-balance condition \(\pi_y=\sum_x\pi_xP_{xy}\). Detailed balance, \(\pi_xP_{xy}=\pi_yP_{yx}\), is stronger: sum it over \(x\) to recover stationarity. A stationary directed cycle can violate detailed balance, so reversibility is a convenient construction rather than a universal necessity.
2. Derive Metropolis–Hastings
From \(x\) propose \(y\sim q(y|x)\) and accept with \(\alpha(x,y)\). For distinct states, \(P(x,dy)=q(y|x)\alpha(x,y)dy\). Remaining probability belongs to staying at \(x\). Set
Multiplication gives forward equilibrium flow \(\min[\pi(x)q(y|x),\pi(y)q(x|y)]\), identical to reverse flow. At points with one-way proposals the corresponding acceptance may be zero; check support explicitly. In a canonical target the normalizing partition function cancels, leaving \(r=e^{-\beta\Delta U}q(x|y)/q(y|x)\). The familiar energy-only formula assumes a symmetric proposal. A downhill move is not guaranteed acceptance with an asymmetric proposal.
3. Worked asymmetric example
Take \(\pi(A)=0.8\), \(\pi(B)=0.2\), \(q(B|A)=0.5\), \(q(A|B)=1\). Then \(r(A,B)=0.5\), so accepted transition probabilities are \(P_{AB}=0.25\) and \(P_{BA}=1\). Self-transition probabilities are \(0.75\) and zero. Both equilibrium cross flows equal \(0.2\). Omitting the proposal ratio would instead give \(P_{AB}=0.125\), with forward flow \(0.1\); the resulting stationary probability of \(B\) is \(1/9\), not \(1/5\).
4. A correct collection protocol
Propose, accept or reject, then record the current state at a fixed cadence. Rejections are repeated states, encoding residence time. Saving only accepted moves generally changes the distribution; the jump chain requires explicit residence-time reweighting. Evaluate log acceptance \(\log r=-\beta\Delta U+\log q(x|y)-\log q(y|x)\) and compare \(\log u\) with \(\min(0,\log r)\) to avoid exponential overflow. Acceptance alone says little about exploration: tiny moves can be almost always accepted yet travel slowly.
Boundary handling is part of the proposal. Rejecting a displacement outside a box may preserve the original symmetry. Repeatedly redrawing until it lies inside conditions the proposal on an allowed region whose volume depends on the starting point, potentially making it asymmetric. Periodic wrapping and reflection are other constructions requiring their own checks. Small-looking moves are not automatically symmetric.
5. Exercises and caveats
Exercise: A three-state deterministic directed cycle has uniform stationary distribution. Does it satisfy detailed balance or converge from a fixed state?
Solution
It is stationary for an initially uniform ensemble but has no reverse flow and is periodic. A point initial condition cycles forever. Adding a nonzero holding probability removes this periodicity; it does not make the directed chain reversible.
Exercise: Does detailed balance imply every state is reachable?
Solution
No. The identity matrix satisfies detailed balance for any distribution but never moves. Connectivity and convergence require separate analysis in the next lesson.
Original teaching schematic of the mathematics or algorithm; it is not simulation or experimental data.
6. Sources and connections
Related theory: Molecular dynamics · Quantum Monte Carlo
Software connection: CP2K · Quantum ESPRESSO
These software courses provide related background on energies, orbitals, or convergence management; they do not imply that the Monte Carlo or QMC examples on this page were executed there.
7. Related theory and practice
Molecular dynamics · Quantum Monte Carlo · RASPA3