Markov Chains

A Markov chain is a stochastic process whose current state contains all information that its transition rule uses. The state may be a weather label, a queue length, an entire parameter vector, or a neural sampler configuration. The Markov property is conditional independence, not “randomness without memory”: the current state can itself encode an arbitrarily long history.

A kernel specifies the next-state law #

For a discrete-time chain $X_0,X_1,\ldots$,

$$\Pr(X_{t+1}=j\mid X_t=i,X_{t-1},\ldots,X_0) =\Pr(X_{t+1}=j\mid X_t=i)=P_{ij}.$$

The transition matrix $P$ has nonnegative entries and rows summing to one. If a row-vector distribution is $\mu_t$, then

$$\mu_{t+1}=\mu_tP,\qquad \mu_t=\mu_0P^t.$$

On a general state space, a transition kernel $K(x,A)$ gives the probability of moving from state $x$ into measurable set $A$. This notation covers continuous MCMC algorithms as well as finite matrices.

For example,

$$P=\begin{bmatrix}0.8&0.2\\0.3&0.7\end{bmatrix}$$

describes persistence with occasional switching between two states. Starting from state 1, the next distribution is $(0.8,0.2)$; after another step it is $(0.70,0.30)$. The uncertainty evolves deterministically even though individual paths are random.

Stationarity is a distribution-level fixed point #

A distribution $\pi$ is stationary or invariant when

$$\pi=\pi P$$

or, for a kernel, $\pi(A)=\int K(x,A)\,\pi(dx)$. If $X_t\sim\pi$, then $X_{t+1}\sim\pi$. For the two-state example, solving $\pi=pi P$ and $\pi_1+\pi_2=1$ gives $\pi=(0.6,0.4)$.

This equation makes no claim about a particular initialized chain. The identity kernel leaves every distribution invariant but never moves. A sampler can preserve the desired target and still explore it uselessly slowly.

Detailed balance is the stronger pairwise condition

$$\pi_iP_{ij}=\pi_jP_{ji}.$$

Summing over $i$ proves stationarity. A chain satisfying detailed balance is reversible in equilibrium. Detailed balance is sufficient, not necessary: nonreversible chains may also preserve $\pi$ and can sometimes mix faster.

Connectivity and timing determine convergence #

For finite chains:

• States communicate when each can reach the other with positive probability in some number of steps.
• A chain is irreducible when every state communicates with every other.
• A state's period is the greatest common divisor of possible return times; period one is aperiodic.
• A state is recurrent if it returns with probability one, and positive recurrent if its expected return time is finite.

A finite irreducible chain has a unique stationary distribution. Adding aperiodicity gives convergence to it from every initial distribution. Without aperiodicity, distributions can oscillate even though a stationary distribution exists. On infinite state spaces, irreducibility and recurrence need more careful measure-theoretic forms; finite-state intuition cannot simply be copied.

Mixing is about finite-time error #

The total-variation distance

$$\lVert \mu_t-\pi\rVert_{\mathrm{TV}} =\sup_A|\mu_t(A)-\pi(A)|$$

measures the largest probability discrepancy over events. A mixing time asks how many transitions are needed before this error is below a tolerance from specified starts.

Slow mixing has observable causes: high self-transition probability, narrow bridges between modes, strongly correlated coordinates, poor proposal scale, or a state representation that makes important moves unlikely. Trace plots that look locally noisy can still be trapped in one mode.

Autocorrelation means $N$ states do not generally carry the information of $N$ independent draws. For an estimand with lag correlations $\rho_k$, the asymptotic effective sample size is motivated by

$$N_{\mathrm{eff}}\approx \frac{N}{1+2\sum_{k=1}^{\infty}\rho_k}.$$

This quantity is estimand-specific: a chain can estimate one average well and another poorly.

Hitting times answer path questions #

The first hitting time of a set $A$ is

$$\tau_A=\inf\{t\ge 0:X_t\in A\}.$$

Hitting and return probabilities describe reliability, queues, randomized algorithms, and sampler mode changes. They are different from stationary occupancy. A rare state can have small stationary probability yet be extremely hard to reach from a particular initial state.

A reasoning checklist #

When a Markov-chain claim appears, separate these questions:

1. What exactly is the state, and is the transition genuinely Markov in that state?
2. Which distribution, if any, is invariant under the kernel?
3. Is detailed balance used, or is stationarity proved another way?
4. Are all relevant states or modes connected?
5. Can periodicity prevent distributional convergence?
6. How is finite-run bias or mixing error assessed?
7. Which estimand's autocorrelation and Monte Carlo error matter?

The transition rule, invariant distribution, and convergence rate are distinct properties. MCMC works only when all three are aligned with the inference task.