Markov Chain Theory for MCMC

As we discussed in the chapter introduction, directly computing or sampling from complex, high-dimensional posterior distributions $p(\theta | D)$ is often intractable. MCMC algorithms provide a clever workaround: instead of drawing independent samples directly from $p(\theta | D)$, we construct a Markov chain whose states are parameter values $\theta$ and whose stationary distribution is precisely the target posterior distribution $p(\theta | D)$. By simulating this chain for long enough, the samples we generate will eventually behave as if they were drawn from the target posterior.

But how does this work? Why can we trust that samples from some cleverly constructed random walk will eventually look like samples from our specific posterior? The answer lies in the mathematical properties of Markov chains. Let's examine the essential theory.

What is a Markov Chain?

A Markov chain is a sequence of random variables $\theta^{(0)}, \theta^{(1)}, \theta^{(2)}, \ldots$, where each $\theta^{(t)}$ represents the state of the chain at time step $t$. In our context, a state is typically a specific value (or vector of values) for the model parameters $\theta$. The defining characteristic of a Markov chain is the Markov property: the distribution of the next state $\theta^{(t+1)}$ depends only on the current state $\theta^{(t)}$ and not on any previous states $\theta^{(0)}, \ldots, \theta^{(t-1)}$.

Mathematically, this is expressed as:

$$P(\theta^{(t+1)} | \theta^{(t)}, \theta^{(t-1)}, \ldots, \theta^{(0)}) = P(\theta^{(t+1)} | \theta^{(t)})$$

The mechanism governing the movement between states is the transition kernel (or transition probability), denoted $T(\theta' | \theta)$. This function gives the probability density of moving to state $\theta'$ given that the chain is currently in state $\theta$. MCMC algorithms work by carefully designing this transition kernel $T$.

A simple illustration of a Markov chain with three states ($\theta_1, \theta_2, \theta_3$) and associated transition probabilities between them. The next state depends only on the current state.

The Stationary Distribution

A central concept is the stationary distribution, often denoted by $\pi(\theta)$. A distribution $\pi(\theta)$ is stationary for a Markov chain with transition kernel $T(\theta' | \theta)$ if, once the chain's state distribution reaches $\pi(\theta)$, it stays there. In other words, if the probability of being in state $\theta$ at time $t$ is given by $\pi(\theta)$, then the probability of being in state $\theta'$ at time $t+1$ is also given by $\pi(\theta')$.

Formally, $\pi$ is a stationary distribution if it satisfies:

$$\pi(\theta') = \int T(\theta' | \theta) \pi(\theta) d\theta$$

For discrete state spaces, this becomes:

$$\pi_j = \sum_i T_{ji} \pi_i$$

where $\pi_i$ is the probability of being in state $i$, and $T_{ji}$ is the probability of transitioning from state $i$ to state $j$.

The goal of MCMC is to design a transition kernel $T$ such that its unique stationary distribution $\pi(\theta)$ is exactly our target posterior distribution $p(\theta | D)$. If we can achieve this, running the chain ensures that the distribution of states eventually converges to $p(\theta | D)$.

Convergence Conditions: Ergodicity

For an MCMC algorithm to be useful, we need guarantees that the chain will actually converge to the desired stationary distribution $\pi(\theta) = p(\theta | D)$, regardless of the starting state $\theta^{(0)}$. This property is called ergodicity. An ergodic Markov chain has a unique stationary distribution, and the distribution of $\theta^{(t)}$ converges to this stationary distribution as $t \to \infty$.

Two conditions are generally sufficient for ergodicity:

1. Irreducibility: The chain must be able to reach any part of the state space (where $\pi(\theta) > 0$) from any other part, eventually. This ensures the chain doesn't get stuck in only a portion of the target distribution. Formally, for any initial state $\theta$ and any region $A$ with $\int_A \pi(\theta') d\theta' > 0$, there must be some $t > 0$ such that $P(\theta^{(t)} \in A | \theta^{(0)} = \theta) > 0$.

2. Aperiodicity: The chain should not be restricted to visiting states in a fixed cycle. For example, it shouldn't only be possible to return to state $\theta$ after an even number of steps. Aperiodicity helps ensure that convergence isn't hindered by systematic, cyclical behavior. Many standard MCMC algorithms (like Metropolis-Hastings with reasonable proposals, or Gibbs sampling) automatically satisfy this condition because there's usually a non-zero probability of staying in the same state ($T(\theta | \theta) > 0$).

If a chain is irreducible and aperiodic, and possesses a stationary distribution $\pi(\theta)$, then it is ergodic. This means:

$$\lim_{t \to \infty} P(\theta^{(t)} \in A | \theta^{(0)}) = \int_A \pi(\theta') d\theta'$$

for any starting state $\theta^{(0)}$ and any region $A$ in the state space. This limiting behavior is exactly what we need: after a sufficient "burn-in" period, the states $\theta^{(t)}$ behave like samples drawn from $\pi(\theta) = p(\theta | D)$.

Detailed Balance: A Convenient Condition

Designing a transition kernel $T$ and proving directly that $p(\theta | D)$ is its stationary distribution using the integral equation $\pi(\theta') = \int T(\theta' | \theta) \pi(\theta) d\theta$ can be difficult. Fortunately, a simpler, sufficient condition exists: detailed balance (also known as reversibility).

A Markov chain satisfies detailed balance with respect to a distribution $\pi(\theta)$ if the probability flow from state $\theta$ to state $\theta'$ is equal to the probability flow from $\theta'$ back to $\theta$:

$$\pi(\theta) T(\theta' | \theta) = \pi(\theta') T(\theta | \theta')$$

If a transition kernel $T$ satisfies detailed balance with respect to $\pi$, then $\pi$ is a stationary distribution for that kernel. We can see this by integrating both sides over $\theta$:

$$\int \pi(\theta) T(\theta' | \theta) d\theta = \int \pi(\theta') T(\theta | \theta') d\theta$$ $$\int T(\theta' | \theta) \pi(\theta) d\theta = \pi(\theta') \int T(\theta | \theta') d\theta$$

Since $\int T(\theta | \theta') d\theta = 1$ (the total probability of transitioning from $\theta'$ is 1), we get:

$$\int T(\theta' | \theta) \pi(\theta) d\theta = \pi(\theta')$$

This is precisely the condition for $\pi$ being a stationary distribution.

Most common MCMC algorithms, including Metropolis-Hastings and Gibbs sampling, are constructed specifically to satisfy detailed balance with respect to the target posterior $p(\theta | D)$. This provides a practical way to design algorithms that are guaranteed (under irreducibility and aperiodicity) to converge to the correct distribution.

Summary: Why Markov Chain Theory Matters for MCMC

Understanding these core concepts, the Markov property, stationary distributions, ergodicity (via irreducibility and aperiodicity), and detailed balance, is fundamental to MCMC. This theory provides the mathematical justification for why simulating a carefully constructed Markov chain allows us to generate samples that approximate our target posterior distribution $p(\theta | D)$. By ensuring our chosen MCMC algorithm corresponds to an ergodic chain satisfying detailed balance with respect to $p(\theta | D)$, we gain confidence that the samples generated after a burn-in period can be used for Bayesian inference, letting us approximate posterior means, variances, credible intervals, and other quantities of interest. The following sections will build on this theoretical foundation as we explore specific MCMC algorithms like Metropolis-Hastings, Gibbs sampling, and Hamiltonian Monte Carlo.