Countable-State Convergence Through Coupling

Why Countable State Spaces Need a Different Argument

For a finite irreducible chain, a positive power of the transition matrix can have all entries positive when the chain is aperiodic. On a countable state space, there is no finite matrix power whose entries can all be bounded below by one common positive number: probability may be spread over infinitely many states. A useful alternative is to let two copies of the chain move independently until they reach the same state at the same time, then make them move together. Recurrence supplies repeated opportunities to meet, while aperiodicity allows their time schedules to align.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Each row is a probability distribution: \(\sum_{j\in S}p_{ij}=1\). The chain is irreducible if every state can be reached from every other state with positive probability in some finite number of steps. It is positive recurrent if the expected first return time \(T_i^+=\inf\{n\ge1:X_n=i\}\), when started at \(i\), is finite for every state \(i\). It is aperiodic if the greatest common divisor of the possible return times to a state is \(1\); for an irreducible chain this condition is the same for every state.

The Coupling Convergence Theorem

The key role of aperiodicity is captured by a path-length fact. We give the details because it is what makes the product-chain argument work.

Lemma. If \(P\) is irreducible and aperiodic, then for every \(x,y\in S\) there is an integer \(N_{x,y}\) such that \(p_{xy}^{(n)}>0\) for every \(n\ge N_{x,y}\).

Proof. Fix a state \(a\). Aperiodicity says that the set of possible positive return lengths to \(a\) has greatest common divisor \(1\). Some finite subset \(r_1,\ldots,r_m\) of those lengths already has greatest common divisor \(1\): starting with one length and adding lengths that reduce the current greatest common divisor must eventually reach \(1\). Every nonnegative integer combination of the \(r_k\) is a possible return length, since the corresponding return paths can be concatenated.

We use the following elementary consequence. If positive integers \(r_1,\ldots,r_m\) have greatest common divisor \(1\), their nonnegative integer combinations contain every sufficiently large integer. To see this, take \(r_1\) as a modulus. The residues of the \(r_k\) generate all residues modulo \(r_1\), because their greatest common divisor with \(r_1\) is \(1\). In a finite group, any residue obtainable using integer coefficients is also obtainable using nonnegative coefficients: replace a negative coefficient by a nonnegative one congruent to it modulo the order of the corresponding residue. Thus, for each residue \(s\) modulo \(r_1\), choose a nonnegative combination \(b_s\) with residue \(s\). Every integer \(n\ge\max_s b_s\) has the residue of some \(b_s\), and \(n-b_s\) is then a nonnegative multiple of \(r_1\). Hence \(n\) is a nonnegative combination of the \(r_k\).

By irreducibility, there is a path from \(x\) to \(a\) of some length \(u\), and a path from \(a\) to \(y\) of some length \(v\). Inserting between them a return path at \(a\) gives a path from \(x\) to \(y\) of length \(u+w+v\), for every sufficiently large integer \(w\). Therefore \(p_{xy}^{(n)}>0\) for every sufficiently large \(n\). This proves the lemma. \(\square\)

Proof of the theorem. First choose a stationary distribution \(\pi\). For an irreducible positive recurrent chain such a distribution exists and is unique; moreover, \(\pi_j>0\) for every \(j\in S\). These are standard consequences of the return-time formula for irreducible positive recurrent chains.

Consider two chains that evolve independently, with joint state \((U_n,V_n)\in S\times S\). Their transition probability from \((i,j)\) to \((k,\ell)\) is \(p_{ik}p_{j\ell}\). Its row sums equal \(1\), since \[ \sum_{k,\ell\in S}p_{ik}p_{j\ell} =\left(\sum_{k\in S}p_{ik}\right)\left(\sum_{\ell\in S}p_{j\ell}\right)=1. \] The lemma implies that this product chain is irreducible: for any \((i,j),(k,\ell)\), choose \(n\) large enough that both \(p_{ik}^{(n)}>0\) and \(p_{j\ell}^{(n)}>0\); the product-chain \(n\)-step probability is their positive product.

The distribution \(\pi\otimes\pi\), defined by \((\pi\otimes\pi)(i,j)=\pi_i\pi_j\), is stationary for the independent product chain. Indeed, its mass at \((k,\ell)\) after one step is \[ \sum_{i,j\in S}\pi_i\pi_jp_{ik}p_{j\ell} =\left(\sum_i\pi_i p_{ik}\right)\left(\sum_j\pi_j p_{j\ell}\right) =\pi_k\pi_\ell. \] It is a probability distribution, and it assigns positive mass to every pair. The standard invariant-probability criterion for an irreducible chain now implies that the product chain is positive recurrent. In particular, from any starting pair it hits the pair \((a,a)\) almost surely, for any fixed \(a\in S\).

Now start \(X_0=i\) and start \(Y_0\) with distribution \(\pi\). Until the first time the two chains are equal, let them make independent transitions. After that time, use the same transition draw for both chains at every step. Each coordinate still has transition matrix \(P\), and once equal the chains remain equal. Before they meet, their evolution is that of the independent product chain. That product chain hits \((a,a)\) almost surely, so the coupling time \(T=\inf\{n\ge0:X_n=Y_n\}\) is finite almost surely.

For any coupling of distributions \(\alpha,\beta\), \(\|\alpha-\beta\|_{\mathrm{TV}}\le\mathbb{P}(X\ne Y)\): for each set \(A\), the indicators \(\mathbf{1}_{\{X\in A\}}\) and \(\mathbf{1}_{\{Y\in A\}}\) can differ only if \(X\ne Y\). Applying this at time \(n\), and using that \(Y_n\) has distribution \(\pi\), gives \[ \|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}\le\mathbb{P}(T>n)\longrightarrow0. \] Finally, for any initial distribution \(\mu\), the triangle inequality for sums gives \[ \|\mu P^n-\pi\|_{\mathrm{TV}} \le\sum_{i\in S}\mu_i\|P^n(i,\cdot)-\pi\|_{\mathrm{TV}}. \] Each summand tends to zero and each distance is at most \(1\). To verify convergence without any interchange difficulty, choose a finite set \(F\) with \(\sum_{i\notin F}\mu_i<\varepsilon\). The sum over \(F\) tends to zero, and the sum outside \(F\) is at most \(\varepsilon\). Since \(\varepsilon>0\) is arbitrary, the result follows. \(\square\)

Worked Examples

Interpreting the Argument and Avoiding a Pitfall

The theorem asserts convergence to a stationary distribution, not merely the existence of one. The coupling supplies the extra step: for a fixed initial state and a stationary copy, the probability that the copies have not yet met tends to zero. It does not, on a countable state space, promise a uniform convergence rate over all starting states. The probability of a successful meeting can depend strongly on the starting pair.

Common mistake. A stationary distribution does not force the distributions \(P^n(i,\cdot)\) to converge. In the alternating example, one might calculate \(P^2=I\) and incorrectly infer that repeated application of \(P\) approaches the stationary distribution. But \(P^{2m}(0,\cdot)=\delta_0\) for every \(m\), while \(P^{2m+1}(0,\cdot)=\delta_1\). The correction is to check the chain's period and analyze the full sequence \(P^n\), not just a subsequence of powers. For countable-state convergence, irreducibility, positive recurrence, and aperiodicity work together: recurrence provides a recurrent state, aperiodicity aligns possible path lengths, and coupling turns a simultaneous visit into permanent agreement.