From Matrix Powers to Distance from Equilibrium
For a finite Markov chain, the distribution after \(n\) steps is obtained by multiplying the initial distribution by the \(n\)-step transition matrix. To quantify how close that distribution is to a stationary distribution, we use total variation distance. Exact calculations in small chains reveal both the size of the distance at a given time and the geometric factor controlling its decay.
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The entries are nonnegative and each row sums to \(1\). Distributions are row vectors: if \(X_0\) has distribution \(\mu_0\), then \(X_n\) has distribution \(\mu_n=\mu_0P^n\). A stationary distribution is a probability row vector \(\pi\) satisfying \(\pi P=\pi\). For probability vectors \(\mu,\nu\) on \(S\), their total variation distance is
For a finite state space, this also equals the largest difference \(|\mu(A)-\nu(A)|\) over subsets \(A\subseteq S\). The factor \(1/2\) ensures the distance lies between \(0\) and \(1\). In the calculations below, we compare \(\mu_0P^n\) with a stationary distribution \(\pi\); we do not assume that the chain starts in equilibrium.
Proof. Since \(a,b>0\), each state can move to the other, so the chain is irreducible. Also \(1-a>0\) and \(1-b>0\), so each state has a positive probability of returning in one step; its period is \(1\), and the chain is aperiodic. The proposed vector \(\pi\) has nonnegative entries summing to \(1\). Its first coordinate after multiplication by \(P\) is \(\frac{b}{a+b}(1-a)+\frac{a}{a+b}b=\frac{b}{a+b}\); the second coordinate is \(1-\frac{b}{a+b}=\frac{a}{a+b}\). Thus \(\pi P=\pi\). To prove the power formula, let \(x_n\) be the probability of state \(1\) at time \(n\). If \(x_n\) is the current probability, then \(x_{n+1}=x_n(1-a)+(1-x_n)b=b+(1-a-b)x_n\). The stationary probability \(x_*=\frac{b}{a+b}\) satisfies \(x_*=b+\lambda x_*\), so subtraction gives \(x_{n+1}-x_*=\lambda(x_n-x_*)\). Iterating this equality yields \(x_n-x_*=\lambda^n(x_0-x_*)\). Since each two-coordinate probability vector has second coordinate equal to one minus its first, the vector identity follows. Taking absolute values in both coordinates and applying the definition of total variation proves the distance formula. \(\square\)
The assumptions \(0<a,b<1\) also give \(-1<\lambda<1\), so the formula implies convergence to \(\pi\) from every initial distribution. The factor \(|\lambda|\) gives the exact per-step decay factor whenever the initial distribution differs from \(\pi\). If \(\lambda=0\), the distribution reaches \(\pi\) after one step.
Worked Example: A Symmetric Two-State Chain
Consider \(S=\{1,2\}\) and \(P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac14&\tfrac34\end{bmatrix}\). Each row sums to \(\tfrac34+\tfrac14=1\), and all entries are positive, so the chain is irreducible and aperiodic. Symmetry, or the two-state formula with \(a=b=\tfrac14\), gives \(\pi=(\tfrac12,\tfrac12)\). Starting at state \(1\), compute the exact distance at times \(n=0,1,2\), and its general form.
Here \(\lambda=1-\tfrac14-\tfrac14=\tfrac12\). The two-state result gives \(\delta_1P^n-\pi=(\tfrac12)^n(\delta_1-\pi)\), where \(\delta_1=(1,0)\). Thus the distribution at time \(n\) is \((\tfrac12+\tfrac12(\tfrac12)^n,\ \tfrac12-\tfrac12(\tfrac12)^n)\). At \(n=0\), this is \((1,0)\), and the distance is \(\frac12(|1-\frac12|+|0-\frac12|)=\frac12\). At \(n=1\), it is \((\frac34,\frac14)\), and the distance is \(\frac12(\frac14+\frac14)=\frac14\). At \(n=2\), it is \((\frac58,\frac38)\), and the distance is \(\frac12(\frac18+\frac18)=\frac18\). In general the distance is \(\frac12(\frac12)^n\).
Check: Directly multiplying \((\frac34,\frac14)P\) gives \((\frac{9}{16}+\frac{1}{16},\frac{3}{16}+\frac{3}{16})=(\frac58,\frac38)\), the stated time-two distribution. Also \(\pi P=(\frac12,\frac12)\), confirming stationarity.
An Asymmetric Two-State Calculation
The stationary distribution need not be uniform, and the distances from different starting states need not have the same initial size. The two-state formula separates this starting-state effect from the common geometric decay factor.
Worked Example: Unequal Transition Probabilities
Take \(S=\{1,2\}\) and \(P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac12&\tfrac12\end{bmatrix}\). Both rows sum to \(1\), and every entry is positive, so the chain is irreducible and aperiodic. Find \(\pi\), calculate \(P^2\), and compare the total variation distances from the two possible initial states.
Here \(a=\tfrac14\) and \(b=\tfrac12\), so \(a+b=\tfrac34\) and \(\lambda=1-a-b=\tfrac14\). The stationary distribution is \(\pi=(\frac{1/2}{3/4},\frac{1/4}{3/4})=(\frac23,\frac13)\). For the matrix square, each entry is computed by row-column multiplication:
The first row sums to \(\frac{11}{16}+\frac{5}{16}=1\), and the second sums to \(\frac58+\frac38=1\). From state \(1\), the initial distance is \(\|\delta_1-\pi\|_{\mathrm{TV}}=\frac12(|1-\frac23|+|0-\frac13|)=\frac13\). After one step the distribution is \((\frac34,\frac14)\), giving distance \(\frac12(\frac1{12}+\frac1{12})=\frac1{12}\). After two steps the distribution is \((\frac{11}{16},\frac5{16})\), giving distance \(\frac12(\frac1{48}+\frac1{48})=\frac1{48}\). From state \(2\), the initial distance is \(\frac12(|0-\frac23|+|1-\frac13|)=\frac23\). The general formula therefore gives distances \(\frac23\), \(\frac16\), and \(\frac1{24}\) at times \(0,1,2\), respectively.
Check: Multiplication confirms \(\pi P=(\frac23\cdot\frac34+\frac13\cdot\frac12,\frac23\cdot\frac14+\frac13\cdot\frac12)=(\frac23,\frac13)\). The time-two distances are also one quarter of the time-one distances, matching \(|\lambda|=\frac14\).
A Three-State Chain with Exact Powers
For a three-state example, a useful calculation is to separate the uniform distribution from deviations whose coordinates sum to zero. This is a direct matrix calculation, not an appeal to a general convergence theorem.
Worked Example: A Symmetric Three-State Chain
Let \(S=\{1,2,3\}\) and \(P=\begin{bmatrix}\tfrac12&\tfrac14&\tfrac14\\\tfrac14&\tfrac12&\tfrac14\\\tfrac14&\tfrac14&\tfrac12\end{bmatrix}\). Each row sums to \(\frac12+\frac14+\frac14=1\), and every entry is positive; hence the chain is irreducible and aperiodic. The uniform distribution \(\pi=(\frac13,\frac13,\frac13)\) is stationary because every column also sums to \(1\).
Let \(J\) be the \(3\) by \(3\) matrix whose entries are all \(1\), and let \(I\) be the identity matrix. Entry by entry, \(P=\frac13J+\frac14(I-\frac13J)\): a diagonal entry is \(\frac13+\frac14\cdot\frac23=\frac12\), and an off-diagonal entry is \(\frac13-\frac14\cdot\frac13=\frac14\). Put \(A=\frac13J\). Direct multiplication gives \(A^2=A\), since every entry of \(J^2\) is \(3\), and therefore \((I-A)^2=I-A\) and \(A(I-A)=(I-A)A=0\). Expanding powers using these identities gives \(P^n=A+(\frac14)^n(I-A)\) for every integer \(n\ge0\). Indeed it holds at \(n=0\), when \(A+(I-A)=I\); multiplying the formula by \(P=A+\frac14(I-A)\) gives the same formula with \(n\) replaced by \(n+1\).
For a chain starting at state \(1\), the distribution is consequently \((\frac13+\frac23(\frac14)^n,\frac13-\frac13(\frac14)^n,\frac13-\frac13(\frac14)^n)\). At \(n=1\), this is \((\frac12,\frac14,\frac14)\), and its distance to \(\pi\) is \(\frac12(\frac16+\frac1{12}+\frac1{12})=\frac16\). At \(n=2\), it is \((\frac38,\frac5{16},\frac5{16})\), and the distance is \(\frac12(\frac1{24}+\frac1{48}+\frac1{48})=\frac1{24}\). In general, the first coordinate differs from \(\frac13\) by \(\frac23(\frac14)^n\), while each other coordinate differs by \(-\frac13(\frac14)^n\). Hence \(\|\delta_1P^n-\pi\|_{\mathrm{TV}}=\frac23(\frac14)^n\).
Check: Squaring the displayed matrix gives diagonal entries \(\frac14+\frac1{16}+\frac1{16}=\frac38\) and off-diagonal entries \(\frac18+\frac18+\frac1{16}=\frac5{16}\). Each row of \(P^2\) sums to \(\frac38+\frac5{16}+\frac5{16}=1\), agreeing with the time-two distribution above.
Comparing Rates and Avoiding a Common Error
The examples show two distinct parts of a distance calculation: an initial constant determined by the starting distribution, and a per-step factor determined by the chain. The symmetric two-state chain has factor \(\frac12\); the asymmetric two-state chain has factor \(\frac14\); and the symmetric three-state chain has factor \(\frac14\). Thus, for these examples, the two chains with factor \(\frac14\) reduce their distances faster per step than the chain with factor \(\frac12\). Initial distances still matter: for example, the three-state distance from a point mass is \(\frac23(\frac14)^n\), whereas the asymmetric two-state distance from state \(2\) is \(\frac23(\frac14)^n\), but from state \(1\) it is only \(\frac13(\frac14)^n\).
These formulas establish convergence for the chains considered: their distances tend to zero because the absolute value of each geometric factor is less than \(1\). Aperiodicity matters to this conclusion in general. For example, the two-state matrix \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\) is irreducible but periodic, with stationary distribution \((\frac12,\frac12)\). Starting at state \(1\), the distributions alternate between \((1,0)\) and \((0,1)\), each at distance \(\frac12\) from stationarity. They do not converge. A stationary distribution is an invariant distribution; starting in that distribution keeps the marginal distribution stationary at every time, but this does not by itself imply convergence from other initial distributions.
Common mistake: omitting the factor \(\frac12\). For the time-one distribution \((\frac34,\frac14)\) in the asymmetric example, summing absolute differences gives \(|\frac34-\frac23|+|\frac14-\frac13|=\frac1{12}+\frac1{12}=\frac16\). That is twice the total variation distance, not the distance itself. The correct calculation divides by \(2\), giving \(\frac1{12}\).
For each exact calculation, check the stochastic matrix rows before multiplying, verify any proposed stationary distribution by computing \(\pi P\), and use the same definition of total variation at every time. These checks catch errors in matrix multiplication, normalization, and distance calculations before a rate comparison is made.
Check Your Understanding
Use the row-vector convention and the total variation definition to work through these questions.
- For \(P=\begin{bmatrix}\frac45&\frac15\\\frac25&\frac35\end{bmatrix}\), check the row sums and find the stationary distribution and the factor \(\lambda\).
- For the chain in question 1, calculate the total variation distance from state \(1\) after one step.
- For the three-state chain in the worked example, calculate the distance from state \(1\) at time \(n=3\).
- Explain why a positive diagonal entry at each state ensures period \(1\), and why this alone does not give a numerical convergence rate.
- For the alternating two-state chain, calculate the distance from stationarity at times \(n=0\) and \(n=1\). Does the sequence of distributions converge?