Irreducibility, Aperiodicity, and MCMC Convergence

From an Invariant Target to Convergence

For a finite-state MCMC algorithm, it is not enough to verify that the target distribution is invariant. Invariance says that a chain started at the target distribution remains there; it does not say that a chain started elsewhere can reach all relevant states, or that its distribution approaches the target. Two structural checks address these issues: irreducibility asks whether states communicate, and aperiodicity rules out persistent cycles in the step count. For Metropolis–Hastings (MH), both checks can be made from the proposal probabilities and the possibility of rejection.

Let \(S\) be a finite state space, and let \(\pi=(\pi_i)_{i\in S}\) be a target probability distribution with \(\pi_i>0\) for every \(i\in S\). A proposal kernel \(q=(q_{ij})\) is row-stochastic: \(q_{ij}\ge 0\) and \(\sum_{j\in S}q_{ij}=1\) for each \(i\). The MH chain proposes \(j\) from \(i\), and for \(j\ne i\) accepts with probability \(\alpha(i,j)=\min\{1,\pi_jq_{ji}/(\pi_iq_{ij})\}\) when \(q_{ij}>0\). If \(q_{ij}=0\), that move is never proposed. The transition probabilities off the diagonal are \(p_{ij}=q_{ij}\alpha(i,j)\); the diagonal is \(p_{ii}=1-\sum_{j\ne i}p_{ij}\), so it includes rejected proposals and any probability of proposing the current state.

For an MH chain on a strictly positive target, the relevant proposal graph is undirected: join distinct states \(i\) and \(j\) exactly when both \(q_{ij}>0\) and \(q_{ji}>0\). Indeed, if \(q_{ij}>0\), then \(p_{ij}>0\) exactly when \(q_{ji}>0\), since \(\pi_i,\pi_j\) are positive. Consequently, the MH chain is irreducible exactly when this graph is connected. A proposal in only one direction does not create a one-way MH transition: the proposed move is rejected with probability one.

Proof. Write \(m=|S|\). We first show that there is an integer \(r\ge1\) for which every entry of \(P^r\) is positive. Fix a state \(s\). Aperiodicity means that the positive return lengths \(L=\{n\ge1:p_{ss}^{(n)}>0\}\) have greatest common divisor one. Some finite subset \(l_1,\ldots,l_k\) of these lengths also has greatest common divisor one: starting with any length, successively take greatest common divisors with further lengths; these are positive integers that decrease only finitely many times, and their eventual value is the greatest common divisor of \(L\).

Every sufficiently large integer is a nonnegative integer combination of \(l_1,\ldots,l_k\). To verify this, let \(a=l_1\). The residues of the \(l_i\) generate all residues modulo \(a\), because their greatest common divisor together with \(a\) is one. In the finite additive group of residues modulo \(a\), every residue can be expressed as a nonnegative combination of the \(l_i\): a negative multiple of a residue can be replaced by a nonnegative multiple, since that residue has finite order. For each residue \(u\) choose one such combination \(c_u\). If \(n\ge\max_u c_u\) has residue \(u\), then \(n=c_u+ha\) for some integer \(h\ge0\). Thus \(n\) is a nonnegative combination of return lengths. Concatenating the corresponding return paths shows \(p_{ss}^{(n)}>0\) for every sufficiently large \(n\).

For any \(i,j\), irreducibility supplies a path from \(i\) to \(s\) of some length \(a_i\ge0\), and a path from \(s\) to \(j\) of some length \(b_j\ge0\). Inserting a return path at \(s\) shows \(p_{ij}^{(a_i+n+b_j)}>0\) for every sufficiently large \(n\). Since there are finitely many pairs \(i,j\), one sufficiently large common integer \(r\) makes every entry of \(P^r\) positive.

Set \(R=P^r\) and \(\varepsilon=\min_{i,j}R_{ij}>0\). Row sums give \(m\varepsilon\le1\). If \(m\varepsilon=1\), every entry of every row of \(R\) equals \(1/m\), so \(\mu R=\nu R\) for any distributions \(\mu,\nu\). Otherwise, define \(\widetilde R_{ij}=(R_{ij}-\varepsilon)/(1-m\varepsilon)\). This is a row-stochastic matrix, and \(R_{ij}=\varepsilon+(1-m\varepsilon)\widetilde R_{ij}\). For distributions \(\mu,\nu\), the constant \(\varepsilon\) part cancels in their difference. Also, for any row-stochastic matrix \(K\), the triangle inequality gives \(\sum_j|(\mu K)_j-(\nu K)_j|\le\sum_i|\mu_i-\nu_i|\sum_jK_{ij}=\sum_i|\mu_i-\nu_i|\). Therefore \(\|\mu R-\nu R\|_{\mathrm{TV}}\le(1-m\varepsilon)\|\mu-\nu\|_{\mathrm{TV}}\), where \(\|\mu-\nu\|_{\mathrm{TV}}=\tfrac12\sum_i|\mu_i-\nu_i|\).

Since \(\pi R=\pi\), iteration gives \(\|\mu R^k-\pi\|_{\mathrm{TV}}\le(1-m\varepsilon)^k\|\mu-\pi\|_{\mathrm{TV}}\), with immediate equality to zero after one block in the case \(m\varepsilon=1\). Write \(n=kr+u\), where \(0\le u<r\). Multiplication by \(P^u\) cannot increase total variation by the same row-stochastic-matrix inequality, and \(\pi P^u=\pi\). Hence \(\|\mu P^n-\pi\|_{\mathrm{TV}}\le\|\mu R^k-\pi\|_{\mathrm{TV}}\to0\). If \(\nu\) were another stationary distribution, the same convergence applied with \(\mu=\nu\) would give \(\nu=\pi\). This proves convergence and uniqueness. \(\square\)

Checking the Conditions in Practice

The theorem separates the tasks. First check that the target has positive mass on the state space being sampled and that every proposal row sums to one. Then build the mutual-proposal graph to assess irreducibility. Finally, look for a source of self-transitions. In an irreducible chain, a positive self-transition at even one state gives a return in one step there, so that state has period one; irreducibility then makes the chain aperiodic. In MH, a rejection at a state creates a positive diagonal transition. A proposal that can remain at the current state can do so as well.

Common Mistakes and Practical Consequences

A common incorrect calculation treats a proposal probability as if it were already an MH transition probability. In the directed-cycle example, one might write \(p_{01}=q_{01}=1\), then conclude that the chain can move from \(0\) to \(1\). The correction is to include the acceptance probability: \(p_{01}=q_{01}\alpha(0,1)=1\cdot0=0\), because \(q_{10}=0\). Always calculate the accepted off-diagonal moves before deciding whether the chain is irreducible.

Another mistake is to equate stationarity with convergence. Stationarity is the equation \(\pi P=\pi\); it is satisfied in all three examples, including the reducible and periodic ones. Convergence requires the additional structural conditions in the theorem. In applications, zero proposal probabilities may be intentional—for example, to enforce constraints—but they must not separate the positive-target states into disconnected components. A practical design check is therefore:

1. List the states with positive target mass that the algorithm is intended to explore.
2. For each distinct pair, record whether both proposal probabilities are positive; test connectivity of this mutual-proposal graph.
3. Check for a positive probability of staying at some state, either from rejection or from proposing the current state. In an irreducible chain, this suffices for aperiodicity.
4. Verify that the MH transition rows sum to one and that the target is stationary before invoking the convergence result.

These conditions are qualitative guarantees, not a measure of how quickly convergence occurs. A chain can be irreducible and aperiodic while still moving between important regions very slowly. Quantitative bounds on that speed require additional analysis.