Convergence to Equilibrium via Coupling

Intuition Beginner

A Markov chain that is irreducible and aperiodic settles down. No matter where you start it, after enough steps the chance of finding it in any given state stops depending on the starting point and locks onto a single fixed pattern — the equilibrium distribution. Start the weather chain in a sunny state or a rainy state, and a month later the odds of sun are the same either way. The starting point is forgotten. This unit explains why that forgetting happens, using one strikingly visual idea called coupling.

Here is the picture. Run two copies of the same chain side by side. The first starts wherever you like; the second starts already in equilibrium, so it stays in equilibrium at every step. Let the two move independently until the first moment they land on the same state at the same time. Call that the meeting. From the meeting onward, make them move together in lockstep, sharing every future step. Because the second copy was always in equilibrium, the first is now in equilibrium too, since after meeting they are identical.

Why must they meet? Because we ran two independent copies of a well-mixing chain, the pair itself behaves like a single bigger chain that is sure to revisit the diagonal where the two coordinates agree. Aperiodicity is exactly what stops the two copies from forever marching out of step, like two people circling a track who never quite line up. With aperiodicity the lockstep is possible, the meeting is certain, and once it happens the starting point is erased.

The distance between where the chain actually is and where equilibrium says it should be can only shrink, and it shrinks at least as fast as the chance that the two copies have not yet met. So the whole convergence is controlled by one quantity: how long it takes the two copies to meet. That single quantity is also the seed of mixing time, the count of steps a shuffled deck or a randomized algorithm needs before it is "random enough."

The takeaway: an irreducible aperiodic chain forgets its start because you can couple it to a copy already at equilibrium; the two are sure to meet, after which they agree forever, and the speed of forgetting is the speed of meeting.

Visual Beginner

Picture two walkers on the same set of states, moving independently until they collide and then sticking together.

Top and bottom: walker $X$ starts at your chosen state; walker $Y$ starts already in equilibrium. They step independently — separate random choices — so their paths wander apart and together. At the starred column they land on the same state at the same time: the meeting. After the star they share every move, so they are identical forever. Right: the gauge measuring how far the actual chain is from equilibrium can never exceed the chance the walkers have not yet met, so as meeting becomes near-certain the gauge falls to zero.

Worked example Beginner

Take the two-state chain on $\{0,1\}$ that, from either state, stays put with probability $\frac{1}{2}$ and switches with probability $\frac{1}{2}$. This chain is irreducible (you can get from each state to the other) and aperiodic (the self-stay gives a length-one return, so the beat is one). Its equilibrium is the fair coin: each state has probability $\frac{1}{2}$ in the long run. We start the chain at state $0$ and watch it forget.

Step 1. Write the one-step odds from the start. Starting at $0$, after one step the chain is at $0$ with probability $\frac{1}{2}$ and at $1$ with probability $\frac{1}{2}$. Already after a single step the distribution is exactly the fair coin — for this very symmetric chain, one step suffices.

Step 2. Set up the coupling. Run a second copy $Y$ started from the fair coin, and let $X$ start at $0$. At each step flip the two copies independently. The meeting happens the first time $X$ and $Y$ sit on the same state.

Step 3. Find the chance they have not met after one step. $X$ starts at $0$; $Y$ starts at $0$ or $1$ each with probability $\frac{1}{2}$. Work out the probability that after one independent step the two are on different states. A direct count of the four equally likely combinations of the two independent moves gives a probability $\frac{1}{2}$ that they differ after one step, and the chance of still differing keeps halving: after $n$ steps it is $(\frac{1}{2}{)}^n$.

Step 4. Read off the convergence speed. The distance from equilibrium is at most the chance of not having met, which is $(\frac{1}{2}{)}^n$. So the gap between the actual distribution and the fair coin shrinks by a factor of two every step, vanishing quickly.

What this tells us: even before computing the exact distribution, the coupling gives a clean upper bound on how far the chain is from equilibrium — here $(\frac{1}{2}{)}^n$ — purely by tracking when two independent copies first agree. The starting state $0$ is forgotten geometrically fast, and the rate is set entirely by the meeting time.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $(X_n{)}_{n\ge 0}$ is a time-homogeneous Markov chain on a countable state space $I$ with stochastic transition matrix $P=(p_{ij})$ and $n$-step matrix $P^n=(p_{ij}^{(n)})$, in the sense of 37.05.01; communication, irreducibility, and period are as in 37.05.02, and the strong Markov property and first-return time $T_i:=\inf \{n\ge 1:X_n=i\}$ are as in 37.05.04. We write ${\mathbb{P}}_{\lambda }$ for the law of the chain with initial distribution $\lambda$, and $\lambda P^n$ for the row-vector $(\lambda P^n{)}_j={\sum }_i{\lambda }_i{p}_{ij}^{(n)}$, the distribution of $X_n$ under ${\mathbb{P}}_{\lambda }$. The invariant distribution $\pi$ (the unique probability vector with $\pi P=\pi$, given by ${\pi }_j=1/{\mathbb{E}}_j[T_j]$ on a positive-recurrent irreducible chain) is constructed in the co-produced unit on stationary distributions; here $\pi$ is taken as given and the question is whether $\lambda P^n\to \pi$.

Definition (total-variation distance). For probability distributions $\mu ,\nu$ on the countable set $I$, the total-variation distance is $$\Vert \mu -\nu {\Vert }_{\mathrm{TV}}:=\underset{A\subseteq I}{\sup }|\mu (A)-\nu (A)|=\frac{1}{2}\sum _{i\in I}|{\mu }_i-{\nu }_i|.$$ The supremum is attained at $A=\{i:{\mu }_i\ge {\nu }_i\}$. Total variation lies in $[0,1]$, equals $0$ iff $\mu =\nu$, and equals $1$ iff $\mu ,\nu$ have disjoint supports.

Definition (coupling). A coupling of $\mu$ and $\nu$ is a pair of random variables $(X,Y)$ on a common probability space with $X\sim \mu$ and $Y\sim \nu$ (the joint law is unconstrained beyond its marginals). A coupling of two Markov chains with the same matrix $P$ is a process $(X_n,Y_n{)}_{n\ge 0}$ on $I\times I$ such that each coordinate, viewed alone, is a Markov chain with matrix $P$ (possibly from different initial laws).

Definition (coupling time / coalescence). Given a coupling $(X_n,Y_n)$, the coupling time is $$T_{\mathrm{couple}}:=\inf \{n\ge 0:X_n=Y_n\}.$$ The coupling is coalescent (or sticky) if $X_n=Y_n$ for all $n\ge T_{\mathrm{couple}}$: once the coordinates agree they stay equal forever.

Definition (the independent coupling and the coalescent modification). The independent coupling runs $X$ and $Y$ as two independent chains with matrix $P$; its law on $I\times I$ is that of the product chain with transition matrix $(P\otimes P{)}_{(i,k),(j,l)}=p_{ij}{p}_{kl}$. The associated coalescent coupling follows the product chain until $T_{\mathrm{couple}}$ and thereafter sets $Y_n:=X_n$; each coordinate is still a $P$-chain, and the coupling is coalescent.

Definition (convergence to equilibrium). The chain converges to equilibrium if $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\to 0$ as $n\to \infty$ for every initial distribution $\lambda$; equivalently $p_{ij}^{(n)}\to {\pi }_j$ for all $i,j$.

Counterexamples to common slips Intermediate+

• Aperiodicity is needed, not just irreducibility. The two-cycle $0\leftrightarrow 1$ deterministically (period $2$) is irreducible and positive recurrent with $\pi =(\frac{1}{2},\frac{1}{2})$, yet $p_{00}^{(n)}$ alternates between $1$ and $0$ and never converges. The independent product chain stays forever on the off-diagonal when the two copies start out of phase: they never meet. Aperiodicity is exactly what makes the product chain irreducible and the meeting certain.

• The reference copy must start in equilibrium, not at a convenient state. Coupling a chain to a copy started at a fixed state bounds the distance between two runs of the chain, not the distance to $\pi$. To bound $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}$ one coordinate must be $\pi$-distributed throughout, which requires $\pi P=\pi$.

• The coupling inequality is an inequality, not an identity, for an arbitrary coupling. Only the maximal coupling achieves $\Vert \mu -\nu {\Vert }_{\mathrm{TV}}=\mathbb{P}(X\ne Y)$. Any coupling gives $\Vert \mu -\nu {\Vert }_{\mathrm{TV}}\le \mathbb{P}(X\ne Y)$; a clever coupling makes the bound small, but a poor one need not be tight.

• Coalescence must be built in by hand. Two independent copies that happen to be equal at time $n$ can separate at time $n+1$. The coalescent modification (freeze them together after first meeting) is what turns "agree once" into "agree forever," and it is legitimate because the frozen coordinate is still a $P$-chain.

Key theorem with proof Intermediate+

Theorem (convergence to equilibrium via coupling). Let $P$ be irreducible and aperiodic on a countable state space $I$, with invariant distribution $\pi$ (so the chain is positive recurrent). Then for every initial distribution $\lambda$, $$\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\to 0(n\to \infty ),$$ and in particular $p_{ij}^{(n)}\to {\pi }_j$ for all $i,j\in I$. Moreover, for the coalescent coupling started from $(\lambda ,\pi )$ with coupling time $T$, $$\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>n).$$

Proof. Coupling inequality. Let $(X_n,Y_n)$ be any coupling with $X_0\sim \lambda$, $Y_0\sim \pi$, each coordinate a $P$-chain. Then $X_n\sim \lambda P^n$ and $Y_n\sim \pi P^n=\pi$ (invariance). For any $A\subseteq I$, $$\mathbb{P}(X_n\in A)-\mathbb{P}(Y_n\in A)=\mathbb{P}(X_n\in A,X_n\ne Y_n)-\mathbb{P}(Y_n\in A,X_n\ne Y_n)\le \mathbb{P}(X_n\ne Y_n),$$ because on $\{X_n=Y_n\}$ the two events $\{X_n\in A\}$ and $\{Y_n\in A\}$ coincide and cancel. Taking the supremum over $A$ gives $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(X_n\ne Y_n)$.

Coalescent coupling. Run the independent product chain $W_n=(X_n,Y_n)$ on $I\times I$ with matrix $P\otimes P$, started from $X_0\sim \lambda$, $Y_0\sim \pi$ independently, and let $T=\inf \{n:X_n=Y_n\}$ be the first hit of the diagonal $\Delta =\{(i,i)\}$. Define the coalescent coupling $(X_n,{\tilde{Y}}_n)$ by ${\tilde{Y}}_n=Y_n$ for $n<T$ and ${\tilde{Y}}_n=X_n$ for $n\ge T$. By the strong Markov property of 37.05.04 applied to $W$ at the stopping time $T$, swapping the two coordinates after $T$ does not change the marginal law of either coordinate: $\tilde{Y}$ is still a $P$-chain started from $\pi$, hence ${\tilde{Y}}_n\sim \pi$. Since $X_n={\tilde{Y}}_n$ for $n\ge T$, we have $\{X_n\ne {\tilde{Y}}_n\}\subseteq \{T>n\}$, so the coupling inequality upgrades to $$\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(X_n\ne {\tilde{Y}}_n)\le \mathbb{P}(T>n).$$

The product chain is irreducible and recurrent. The product matrix $P\otimes P$ is irreducible on $I\times I$: given $(i,k)$ and $(j,l)$, aperiodicity and irreducibility of $P$ give, by the eventual-positivity lemma of 37.05.02, an $N$ with $p_{ij}^{(n)}>0$ and $p_{kl}^{(n)}>0$ simultaneously for all $n\ge N$, whence $(P\otimes P{)}_{(i,k),(j,l)}^{(n)}=p_{ij}^{(n)}{p}_{kl}^{(n)}>0$. (This is the one step that uses aperiodicity: without it the two coordinates could be forced onto incompatible periodic clocks and never align.) The product chain has invariant distribution $\pi \otimes \pi$ (the product of two invariant distributions is invariant for the product matrix), so by the existence of a stationary distribution it is positive recurrent, hence recurrent. A recurrent irreducible chain hits every state — in particular every diagonal state $(i,i)$ — with probability one, so $\mathbb{P}(T<\infty )=1$.

Conclusion. Since $T<\infty$ almost surely, $\mathbb{P}(T>n)\to 0$ as $n\to \infty$ by monotone convergence (the events $\{T>n\}$ decrease to $\{T=\infty \}$, a null event). Therefore $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>n)\to 0$. Taking $\lambda ={\delta }_i$ and reading off the $j$-coordinate gives $p_{ij}^{(n)}\to {\pi }_j$. $\square$

Bridge. This theorem builds toward the ergodic and mixing-time theory of the whole chapter and appears again in every quantitative bound on how fast a chain randomizes, because it converts the analytic question "does $P^n$ converge?" into the probabilistic question "do two independent copies meet?" — and the answer to the second is forced by recurrence of the product chain. The foundational reason the proof works is that aperiodicity is exactly the condition making $P\otimes P$ irreducible: this is the central insight, that periodicity is a phase obstruction living on the product space, not on a single copy. The coupling inequality $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>n)$ generalises the elementary observation that two processes agreeing after a random time can differ only before it, and it is dual to the spectral picture in which convergence rate is the second-eigenvalue gap; putting these together, the meeting-time tail $\mathbb{P}(T>n)$ is the probabilistic avatar of the spectral gap, and the bridge is that this single tail simultaneously proves convergence and quantifies its speed, which is exactly the quantity refined into mixing time and the cutoff phenomenon of 07.05.08.

Exercises Intermediate+

Advanced results Master

The coupling time is the master quantity: convergence, its rate, the periodic correction, and the mixing-time theory are four readings of the single tail $\mathbb{P}(T>n)$. The coupling inequality makes total variation a meeting-time problem, and every refinement below sharpens the meeting-time estimate.

Theorem 1 (Doeblin's condition and uniform geometric ergodicity). Suppose there exist $m\ge 1$, $\beta >0$, and a probability measure $\phi$ on $I$ with $p_{ij}^{(m)}\ge \beta {\phi }_j$ for all $i,j$ (the Doeblin minorization). Then $P$ has a unique invariant $\pi$ and ${\sup }_{\lambda }\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le (1-\beta {)}^{\lfloor n/m\rfloor }$. The proof is a coupling: at every $m$ steps the two coordinates jointly draw a common state from $\phi$ with probability $\beta$, coalescing then, so $T$ is dominated by $m$ times a geometric random variable of success probability $\beta$. On a finite irreducible aperiodic chain Doeblin's condition always holds with $m=M$ the primitivity exponent of 37.05.02 and $\beta ={\min }_{i,j}{p}_{ij}^{(M)}>0$, yielding uniform geometric convergence with no spectral computation.

Theorem 2 (the periodic case: convergence along the period and Cesàro). Let $P$ be irreducible positive recurrent of period $d\ge 1$ with invariant $\pi$ and cyclic subclasses $C_0,\dots ,C_{d-1}$ of 37.05.02. For $i\in C_r$ and $j\in C_s$, $p_{ij}^{(n)}=0$ unless $n\equiv s-r(\mathrm{mod}d)$, and along the admissible subsequence $p_{ij}^{(nd+(s-r))}\to d{\pi }_j$. Equivalently $P^d$ restricted to each $C_s$ is irreducible aperiodic with invariant $d\pi {|}_{C_s}$, to which Theorem (Key) applies. In every case the Cesàro (time) average converges without a parity restriction: $$\frac{1}{n}\sum _{m=0}^{n-1}{p}_{ij}^{(m)}\to {\pi }_j(n\to \infty ),$$ which is the ergodic-averaging face of convergence and survives periodicity because averaging washes out the rotation through the subclasses.

Theorem 3 (path coupling and contraction on a metric). If $I$ carries a path metric $\rho$ with edge set $E$ and there is a coupling of one step from adjacent states $x\sim y$ with $\mathbb{E}[\rho (X_1,Y_1)]\le e^{-\alpha }\rho (x,y)$ for all edges, then the Bubley-Dyer path-coupling lemma extends the contraction to all pairs, giving $\mathbb{E}[\rho (X_1,Y_1)]\le e^{-\alpha }\rho (x,y)$ for every $x,y$ and hence $\Vert {\delta }_x{P}^n-\pi {\Vert }_{\mathrm{TV}}\le \mathrm{diam}(\rho )e^{-\alpha n}$ via Markov's inequality and the coupling bound. This reduces a global convergence rate to a one-edge computation and is the standard route to mixing bounds for spin systems and card shuffles, where checking contraction on neighbours is tractable.

Theorem 4 (coupling, mixing time, and cutoff). Define the mixing time $t_{\mathrm{mix}}(\epsilon )=\min \{n:{\sup }_{\lambda }\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \epsilon \}$. The coupling bound gives $t_{\mathrm{mix}}(\epsilon )\le \min \{n:\sup \mathbb{P}(T>n)\le \epsilon \}$, so any coupling with a controlled meeting time upper-bounds mixing. For families of chains indexed by a size parameter $N$ (random walks on $S_N$, on $\{0,1{\}}^N$), the meeting-time concentration produces the cutoff phenomenon: total variation stays near $1$ until a sharp time $t_N$ and then plunges to $0$ in a window $o(t_N)$, so $t_{\mathrm{mix}}(\epsilon )/t_N\to 1$ for every $\epsilon$. The finite-group instances — random transpositions, the riffle shuffle, the hypercube walk — are analysed by representation-theoretic upper bounds and matching coupling or strong-stationary-time lower bounds in 07.05.05 and 07.05.08; coupling supplies the robust, eigenvalue-free upper half of every such cutoff theorem.

Synthesis. The foundational reason the entire convergence theory compresses to one number is the coupling inequality: this is exactly the statement that total variation is the cost of disagreement, so $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>n)$ turns an analytic limit into the recurrence of the product chain, and it is dual to the spectral picture where the same rate is read from the second-eigenvalue gap. Putting these together, aperiodicity is the central insight of the proof — the hypothesis that makes $P\otimes P$ irreducible, so the meeting that erases the initial condition is forced — and when it fails the period $d$ is the phase by which the copies miss each other, salvaged by the Cesàro average and by passage to $P^d$. The coupling time generalises from the crude independent meeting to the Doeblin minorization, to path coupling, and to the maximal coupling that attains the inequality; the same tail $\mathbb{P}(T>n)$ that proves $p_{ij}^{(n)}\to {\pi }_j$ is the quantity whose sharp concentration is the cutoff phenomenon of 07.05.08. This convergence appears again in 37.05.05: the ergodic theorem averages the strong-Markov excursions of 37.05.04, while convergence to equilibrium couples them to a stationary copy, two faces of the same positive-recurrence input ${\pi }_j=1/{\mathbb{E}}_j[T_j]$ — the reciprocal mean return time that is at once the long-run visit frequency and the equilibrium mass.

Full proof set Master

Proposition 1 (coupling inequality). For any coupling $(X,Y)$ of distributions $\mu ,\nu$ on countable $I$, $\Vert \mu -\nu {\Vert }_{\mathrm{TV}}\le \mathbb{P}(X\ne Y)$, with equality for the maximal coupling.

Proof. For $A\subseteq I$, $\mu (A)-\nu (A)=\mathbb{P}(X\in A)-\mathbb{P}(Y\in A)$. The contributions from $\{X=Y\}$ cancel since there $1_{X\in A}=1_{Y\in A}$, leaving $\mu (A)-\nu (A)=\mathbb{P}(X\in A,X\ne Y)-\mathbb{P}(Y\in A,X\ne Y)\le \mathbb{P}(X\ne Y)$; symmetrically for $\nu (A)-\mu (A)$. Sup over $A$ gives the inequality. The maximal coupling of Exercise 8 sets $\mathbb{P}(X\ne Y)=1-{\sum }_i\min ({\mu }_i,{\nu }_i)=\Vert \mu -\nu {\Vert }_{\mathrm{TV}}$, attaining equality, so $\Vert \mu -\nu {\Vert }_{\mathrm{TV}}={\inf }_{\text{couplings}}\mathbb{P}(X\ne Y)$. $\square$

Proposition 2 (the independent product chain is irreducible under aperiodicity). If $P$ is irreducible and aperiodic on $I$, then $P\otimes P$ is irreducible on $I\times I$.

Proof. Fix $(i,k)$ and $(j,l)$. By the eventual-positivity lemma for irreducible aperiodic chains of 37.05.02 (proved there from addition-closure of the return set and the numerical-semigroup lemma), there exist $N_1,N_2$ with $p_{ij}^{(n)}>0$ for $n\ge N_1$ and $p_{kl}^{(n)}>0$ for $n\ge N_2$. For $n\ge \max (N_1,N_2)$, $(P\otimes P{)}_{(i,k),(j,l)}^{(n)}=p_{ij}^{(n)}{p}_{kl}^{(n)}>0$, so $(i,k)\to (j,l)$ in the product chain. As the pair was arbitrary, $P\otimes P$ is irreducible. $\square$

Proposition 3 (the meeting time is almost surely finite). With $P$ irreducible aperiodic positive recurrent and invariant $\pi$, the independent product chain started from any law on $I\times I$ hits the diagonal in finite time a.s.

Proof. By Proposition 2, $P\otimes P$ is irreducible. The product measure $\pi \otimes \pi$ satisfies $(\pi \otimes \pi )(P\otimes P)=(\pi P)\otimes (\pi P)=\pi \otimes \pi$, so it is invariant for the product chain; an irreducible chain with an invariant probability distribution is positive recurrent, hence recurrent 37.05.04. A recurrent irreducible chain visits every state with probability one, so in particular it hits some diagonal state $(i,i)$; thus $T=\inf \{n:X_n=Y_n\}<\infty$ a.s. $\square$

Proposition 4 (convergence and the rate bound). Under the hypotheses of Proposition 3, for every initial law $\lambda$, $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>n)\to 0$, and $p_{ij}^{(n)}\to {\pi }_j$.

Proof. Form the coalescent coupling from the independent product chain started at $(\lambda ,\pi )$ by freezing the second coordinate onto the first after $T$; by the strong Markov property at $T$ 37.05.04 the frozen coordinate remains a $P$-chain started from $\pi$, hence $\pi$-distributed at every time, while the first is $\lambda P^n$-distributed. Proposition 1 gives $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(X_n\ne {\tilde{Y}}_n)\le \mathbb{P}(T>n)$. Proposition 3 gives $\mathbb{P}(T<\infty )=1$, so $\mathbb{P}(T>n)\downarrow \mathbb{P}(T=\infty )=0$. Specializing $\lambda ={\delta }_i$ yields $p_{ij}^{(n)}=({\delta }_i{P}^n{)}_j\to {\pi }_j$. $\square$

Proposition 5 (total variation contracts under $P$; monotone convergence). For all $\mu ,\nu$, $\Vert \mu P-\nu P{\Vert }_{\mathrm{TV}}\le \Vert \mu -\nu {\Vert }_{\mathrm{TV}}$; hence $n\mapsto \Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}$ decreases to its limit.

Proof. With $\rho =\mu -\nu$, ${\sum }_j|(\rho P{)}_j|\le {\sum }_j{\sum }_i|{\rho }_i|p_{ij}={\sum }_i|{\rho }_i|{\sum }_j{p}_{ij}={\sum }_i|{\rho }_i|$ by the triangle inequality and row-stochasticity. Halving gives the contraction. Setting $\mu =\lambda P^n$, $\nu =\pi =\pi P$ shows $\Vert \lambda P^{n+1}-\pi {\Vert }_{\mathrm{TV}}\le \Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}$; the bounded monotone sequence converges, and Proposition 4 identifies its limit as $0$. $\square$

Proposition 6 (periodic case: Cesàro convergence). Let $P$ be irreducible positive recurrent of period $d$ with invariant $\pi$. Then $\frac{1}{n}{\sum }_{m=0}^{n-1}{p}_{ij}^{(m)}\to {\pi }_j$ for all $i,j$, and for $i\in C_r$, $j\in C_s$ the subsequence $p_{ij}^{(nd+(s-r)\mathrm{mod}d)}\to d{\pi }_j$.

Proof. The diagonal-block matrix $P^d$ leaves each cyclic subclass $C_s$ invariant and restricts there to an irreducible aperiodic stochastic matrix 37.05.02, with invariant distribution $d\pi {|}_{C_s}$ (since $\pi$ spreads its mass equally over the $d$ subclasses by the rotation $\pi P=\pi$). Proposition 4 applied to $P^d{|}_{C_s}$ gives $p_{j{j}^{\prime }}^{(nd)}\to d{\pi }_{j^{\prime }}$ for $j,j^{\prime }\in C_s$; composing with a fixed length-$(s-r)$ bridge from $C_r$ to $C_s$ gives the stated subsequence limit. For the Cesàro average, partition $\{0,\dots ,n-1\}$ by residue mod $d$; on each residue class the terms converge to $d{\pi }_j$ when admissible and are $0$ otherwise, and averaging the $d$ classes returns ${\pi }_j$. The bounded-convergence/Cesàro argument removes the parity restriction. $\square$

Connections Master

• The strong Markov property and recurrence/transience dichotomy 37.05.04 is the engine of the proof: the coalescent coupling is legitimized by restarting the product chain at the meeting time $T$ (a stopping time), and the almost-sure finiteness $\mathbb{P}(T<\infty )=1$ is recurrence of the irreducible product chain, the same visit-with-certainty mechanism that there made a recurrent class hit with probability one — convergence to equilibrium is recurrence of $P\otimes P$ read on the diagonal.

• Class structure, irreducibility, and periodicity 37.05.02 supplies the two hypotheses and the one delicate step: irreducibility gives a single class to converge within, and the eventual-positivity lemma ($p_{ij}^{(n)}>0$ for all large $n$ when aperiodic) is exactly what makes $P\otimes P$ irreducible; periodicity is the obstruction handled by the cyclic-subclass decomposition and the Cesàro average, so the period $d$ of that unit is the phase by which two coupled copies fail to meet.

• The stationary-distribution and ergodic theory 37.05.05, co-produced with this unit, supplies the invariant $\pi$ with ${\pi }_j=1/{\mathbb{E}}_j[T_j]$ that the convergence theorem converges to: existence and positivity of $\pi$ are the positive-recurrence input, the reference copy must be started from $\pi$, and the ergodic theorem's time-average $\frac{1}{n}{\sum }_m{1}_{X_m=j}\to {\pi }_j$ is the pathwise twin of the distributional convergence $p_{ij}^{(n)}\to {\pi }_j$ proved here.

• The cutoff phenomenon for random walks on finite groups 07.05.08 is the quantitative endpoint: the coupling bound $\Vert \lambda P^n-\pi {\Vert }_{\mathrm{TV}}\le \mathbb{P}(T>n)$ furnishes the eigenvalue-free upper half of cutoff theorems, and the representation-theoretic upper bound lemma 07.05.05 furnishes the spectral half, the two meeting in the sharp-threshold analysis of shuffles and hypercube walks.

Historical & philosophical context Master

The coupling method originates with Wolfgang Doeblin, whose 1938 memoir on finite Markov chains ^{[Doeblin 1938]} introduced the minorization condition now bearing his name and used the device of running two coupled copies until they agree to prove convergence to equilibrium with an explicit geometric rate. Doeblin's argument replaced the spectral and matrix-analytic methods of Markov, Perron, and Frobenius with a purely probabilistic construction, trading eigenvalue estimates for a meeting-time estimate. The modern systematic development of coupling — the coupling inequality, the maximal coupling attaining it, and the path-coupling refinement — is the subject of Lindvall's monograph ^{[Lindvall 2002]}.

The use of coupling to obtain sharp mixing rates, and the discovery that many natural chains exhibit a sudden transition from un-mixed to mixed, is due to the random-walks-on-groups school. David Aldous's 1983 lecture notes ^{[Aldous 1983]} developed coupling and strong-stationary-time techniques alongside the representation-theoretic upper-bound lemma for rapidly mixing chains, and the cutoff phenomenon was named and established for the riffle shuffle and random transpositions by Aldous, Diaconis, and Shahshahani in the same period. The textbook synthesis defining convergence through total variation and proving it by the coalescent coupling, together with the Cesàro statement in the periodic case, follows Norris ^{[Norris 1997]} and Levin-Peres ^{[Levin-Peres 2017]}.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Doeblin1938,
  author  = {Doeblin, Wolfgang},
  title   = {Expos\'e de la th\'eorie des cha\^ines simples constantes de Markoff \`a un nombre fini d'\'etats},
  journal = {Revue Math\'ematique de l'Union Interbalkanique},
  volume  = {2},
  year    = {1938},
  pages   = {77--105}
}

@book{Lindvall2002,
  author    = {Lindvall, Torgny},
  title     = {Lectures on the Coupling Method},
  edition   = {2},
  publisher = {Dover Publications},
  year      = {2002}
}

@incollection{Aldous1983,
  author    = {Aldous, David},
  title     = {Random walks on finite groups and rapidly mixing Markov chains},
  booktitle = {S\'eminaire de Probabilit\'es XVII},
  series    = {Lecture Notes in Mathematics},
  volume    = {986},
  publisher = {Springer},
  year      = {1983},
  pages     = {243--297}
}

@book{LevinPeres2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {2},
  publisher = {American Mathematical Society},
  year      = {2017}
}