Markov chain

Definition taught in Markov chains, Gibbs sampling, and Metropolis–Hastings, part of Bayesian statistics

Markov chain

Type Definition
Taught in Markov chains, Gibbs sampling, and Metropolis–Hastings
Part Bayesian statistics
Properties 2
Worked examples 3
Questions using it 11

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.

Properties

Detailed balance implies stationarity

Main article: 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.

Metropolis–Hastings invariance

Main article: Metropolis–Hastings invariance

The Metropolis–Hastings transition defined by Equation (5) in Markov chains, Gibbs sampling, and Metropolis–Hastings satisfies detailed balance with respect to \pi. Consequently, \pi is stationary.

Examples

Four-state random walk

Worked example from Markov chains, Gibbs sampling, and Metropolis–Hastings

Question. Consider states 1,2,3,4 arranged in a line. At every state the chain stays put with probability 1/2. From an endpoint it moves to the only neighbour with probability 1/2; from an interior state it moves left or right with probability 1/4 each. With columns indexing the current state and rows the next state, construct the transition matrix and find the stationary distribution.

Solution. The transition matrix is

{\color{blue}\boldsymbol{Q}}= \begin{pmatrix} 1/2&1/4&0&0\\ 1/2&1/2&1/4&0\\ 0&1/4&1/2&1/2\\ 0&0&1/4&1/2 \end{pmatrix}.

Detailed balance between states 1 and 2 requires

\pi_1\frac12=\pi_2\frac14 \quad\Longrightarrow\quad \pi_2=2\pi_1.

Similarly,

\pi_2\frac14=\pi_3\frac14 \Longrightarrow\pi_3=\pi_2, \qquad \pi_3\frac14=\pi_4\frac12 \Longrightarrow\pi_3=2\pi_4.

Hence

{\boldsymbol{\pi}}=(\pi_1,\pi_2,\pi_3,\pi_4)^{\mathsf T} \propto(1,2,2,1)^{\mathsf T}.

Normalising by 1+2+2+1=6 gives

\boxed{{\boldsymbol{\pi}}=(1/6,2/6,2/6,1/6)^{\mathsf T}}.

Q18. Equilibrium and independence

Question page: Q18. Equilibrium and independence

[4 marks]

A Gibbs sampler targets a bivariate posterior in which the two parameters are strongly correlated. Its initial state is drawn exactly from the target posterior. A student states:

“The chain starts at equilibrium, so its successive sampled pairs can be treated as independent posterior observations.”

Explain what starting at equilibrium guarantees. Does independence follow? Justify your answer by referring to how Gibbs updates are generated.

Definitions. An invariant or equilibrium distribution is preserved by the chain’s transition. Starting from it makes the chain stationary: every iteration has the same marginal target distribution. This is weaker than independence across iterations. Here one Gibbs sweep updates each coordinate once from its exact full conditional, using the newest available conditioning value.

To see invariance directly, start with a pair having density p(\theta_1,\theta_2\mid{\boldsymbol{x}}). Updating \theta_1 while leaving \theta_2 unchanged gives density p(\theta_2\mid{\boldsymbol{x}})\, p(\theta_1'\mid\theta_2,{\boldsymbol{x}}) =p(\theta_1',\theta_2\mid{\boldsymbol{x}}). The second conditional update reconstructs the same joint density in the same way. Therefore the full sweep preserves the target. Starting at equilibrium guarantees stationarity. If (\theta_1^{(0)},\theta_2^{(0)}) \sim p(\theta_1,\theta_2\mid{\boldsymbol{x}}), then \boxed{ (\theta_1^{(t)},\theta_2^{(t)}) \sim p(\theta_1,\theta_2\mid{\boldsymbol{x}}) \quad\text{for every }t\geq0. } Thus no convergence from an incorrectly distributed initial state is needed.

Independence does not follow. A systematic Gibbs update has the form \theta_1^{(t+1)} \sim p(\theta_1\mid\theta_2^{(t)},{\boldsymbol{x}}), followed by \theta_2^{(t+1)} \sim p(\theta_2\mid\theta_1^{(t+1)},{\boldsymbol{x}}). The new pair is generated using components of the current pair, so successive states are generally serially dependent. This dependence can be particularly strong when the target parameters are strongly correlated. Starting at equilibrium gives the correct marginal distribution at every iteration, but it does not turn the Markov chain into independent posterior draws.

C12. Markov property and invariance

Question page: C12. Markov property and invariance

What is the Markov property? What does it mean for a distribution to be invariant for a chain?

Definitions/notation. The Markov property says that the conditional distribution of the next state, given the whole past, depends only on the current state. A distribution \pi is invariant if one transition preserves it: X^{(t)}\sim\pi implies X^{(t+1)}\sim\pi; this alone does not establish convergence from every initial state.

Used in

See also

Conjugacy is optional · Three easy confusions · 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

Glossary and index