Markov chains and equilibrium
Section of Markov chains, Gibbs sampling, and Metropolis–Hastings, part of Bayesian statistics
Markov chains and equilibrium
| Type | Section |
| Taught in | Markov chains, Gibbs sampling, and Metropolis–Hastings |
| Part | Bayesian statistics |
Definition 1 (Markov chain) A stochastic process X_0,X_1,\ldots is a Markov chain if \mathbb{P}(X_{t+1}\in A\mid X_t,X_{t-1},\ldots,X_0) =\mathbb{P}(X_{t+1}\in A\mid X_t) for every measurable set A. In a discrete state space, write q(y\mid x) for the transition probability from x to y; in a continuous state space it is a transition density.
Definition 2 (Stationarity and detailed balance) A distribution \pi is stationary if a state distributed as \pi remains distributed as \pi after one transition. The global balance equation is \pi(y)=\sum_x\pi(x)q(y\mid x) \quad\text{or}\quad \pi(y)=\int\pi(x)q(y\mid x)\,\mathrm{d} x. A stronger sufficient condition is detailed balance: \pi(x)q(y\mid x)=\pi(y)q(x\mid y) \quad\text{for all }x,y.
Theorem 1 (Detailed balance implies stationarity) If a transition kernel q satisfies Equation (3) in Markov chains, Gibbs sampling, and Metropolis–Hastings for a probability distribution \pi, then \pi satisfies global balance and is a stationary distribution of the chain.
Proof. Proof. Integrate both sides of Equation (3) in Markov chains, Gibbs sampling, and Metropolis–Hastings in x: \begin{align*} \int\pi(x)q(y\mid x)\,\mathrm{d} x &=\int\pi(y)q(x\mid y)\,\mathrm{d} x\\ &=\pi(y)\int q(x\mid y)\,\mathrm{d} x\\ &=\pi(y). \end{align*} The last equality holds because a transition density integrates to one.
Stationarity alone is not enough for simulation. One also needs conditions such as irreducibility and aperiodicity so that the chain can reach the whole target support and converge to its stationary distribution. These are grouped informally under ergodicity in this chapter.
MCMC is not intrinsically Bayesian. It is a general method for sampling difficult distributions, and it has deep roots in statistical physics as well as major uses in machine learning. Bayesian posterior calculation is one particularly natural application. The practical migration came at about 1990: methods long used in statistical physics, particularly condensed-matter problems involving large interacting systems, were taken up for posterior calculations that had previously been restricted largely to analytically convenient models. The recipe is to construct a chain whose equilibrium distribution is the posterior, then use its dependent output as a Monte Carlo sample.
Used in
See also
Markov chain · Stationarity and detailed balance · Detailed balance implies stationarity · Systematic-scan Gibbs sampler · Warm-up is not a convergence proof · Metropolis–Hastings update · Metropolis–Hastings invariance · Four-state random walk