Questions: Convergence of Markov Chains

Question 1

A Markov chain on five states has a unique stationary distribution π and is irreducible, but every state returns to itself only at even time steps. What happens as n → ∞?

• A. P(X_n = j) → π(j) for all j, because a unique stationary distribution guarantees convergence
• B. The chain oscillates and P^n does not converge, even though π is the unique stationary distribution
• C. The chain converges because irreducibility is sufficient to guarantee convergence
• D. The chain converges to π only if it starts in π

Answer: (B)

A periodic chain fails to converge even when a unique stationary distribution exists and the chain is irreducible. In this example the chain is bipartite — it alternates between two groups of states every step — so the distribution oscillates between two patterns rather than settling to π. Convergence to π requires both irreducibility AND aperiodicity. A unique stationary distribution guarantees there is a target to converge to, but without aperiodicity the chain never stops oscillating around that target.

Question 2

Chain A has a spectral gap of 0.9 and chain B has a spectral gap of 0.05. Both are irreducible and aperiodic. What do these spectral gaps tell you about their practical behavior?

• A. Chain A reaches stationarity much faster than chain B; chain B may require exponentially more steps to mix
• B. Both chains converge at the same rate because both satisfy the convergence conditions
• C. Chain B converges faster because a smaller spectral gap means more eigenvalues are contributing to the dynamics
• D. The spectral gap only matters for continuous-time chains, not discrete-time

Answer: (A)

The spectral gap — the difference between the largest eigenvalue (1) and the second-largest in absolute value — directly controls the mixing time. Chain A's gap of 0.9 means the non-stationary components of the distribution decay by factor 0.1 per step, so the chain mixes in O(1/0.9) ≈ 1 steps relative to the gap scale. Chain B's gap of 0.05 means those components decay by 0.95 per step, requiring O(1/0.05) = 20 steps per e-fold of decay — mixing can take orders of magnitude longer. In MCMC practice, a near-zero spectral gap (slow mixing) is the main practical obstacle.

Question 3

If a Markov chain has a unique stationary distribution, it will converge to that distribution from any starting state.

• T. True
• F. False

Answer: False

False. Having a unique stationary distribution is necessary but not sufficient for convergence. A periodic chain has a unique stationary distribution but oscillates rather than converging (e.g., a chain that alternates A→B→A→B cycles has a unique stationary distribution but never settles). Similarly, a reducible chain may have multiple stationary distributions but even one that is unique won't guarantee convergence from all starts if the chain can get trapped in a subset of states. Both irreducibility and aperiodicity are required.

Question 4

The burn-in period discarded at the start of an MCMC run corresponds to the time needed for the chain's distribution to approach stationarity from its arbitrary starting state.

• T. True
• F. False

Answer: True

True. MCMC constructs a chain whose stationary distribution equals the target distribution, but if the chain starts far from stationarity, early samples are drawn from a distribution that still reflects the starting state rather than the target. Burn-in discards these early samples, keeping only those collected after the chain has had enough steps (relative to the mixing time) to forget its starting point. The required burn-in length depends on the spectral gap: chains with near-zero spectral gaps need very long burn-ins, which is a major practical challenge in Bayesian computation.

Question 5

Why is aperiodicity required for a Markov chain to converge to its stationary distribution, even when the chain is irreducible and has a unique stationary distribution?

Model answer: A periodic chain cycles through groups of states with a fixed period. Even if the long-run averages match π, the instantaneous distribution at time n oscillates depending on n mod d (where d is the period). The chain never 'settles' — at any given time step, only certain states are accessible. Aperiodicity breaks this cycling structure so that after enough steps, every state can be reached at every time, allowing the distribution to converge rather than oscillate.

Consider a two-state chain with transitions A→B and B→A only. This is irreducible (both states are reachable) and has a unique stationary distribution (0.5, 0.5). But starting in state A, at even times you're in A and at odd times you're in B — the distribution oscillates between (1,0) and (0,1) and never converges to (0.5, 0.5). Adding a small self-loop probability (lazy chain) immediately restores aperiodicity and convergence.