Why a Positive Power Matters
A finite irreducible chain can move between every pair of states, but this does not by itself ensure that its distributions settle down: a periodic chain can keep oscillating. Aperiodicity rules out that obstruction. Together, irreducibility and aperiodicity imply that after some fixed number of steps, every state can reach every other state with positive probability. On a finite state space, the smallest of those probabilities gives a uniform minorization, which in turn forces distributions to contract geometrically toward stationarity.
Throughout, let \((X_n)_{n\ge0}\) be a Markov chain on a finite state space \(S\), with transition matrix \(P=(p_{ij})\) and row-vector distributions. Thus \(\mu_n=\mu_0P^n\), and every row of \(P\) sums to \(1\). A chain is irreducible if every pair \(i,j\in S\) communicates: there is a path of positive-probability transitions from \(i\) to \(j\). The period of \(i\) is the greatest common divisor of its positive return times \(\{n\ge1:p_{ii}^{(n)}>0\}\); the chain is aperiodic if this period is \(1\). In an irreducible chain all states have the same period, a standard fact from the earlier material on aperiodicity.
Return-Time Arithmetic Gives a Positive Power
We first prove the path-length assertion. Fix a reference state \(r\). Irreducibility gives paths from each \(i\) to \(r\), and from \(r\) to each \(j\). Aperiodicity says that the lengths of the positive-probability return paths from \(r\) have greatest common divisor \(1\). The key arithmetic fact is that combinations of these return lengths can produce every sufficiently large integer.
Proof. Let \(L\) be the set of positive lengths of return paths from \(r\) to \(r\). Since the greatest common divisor of \(L\) is \(1\), some finite subset \(a_1,\ldots,a_k\) of \(L\) also has greatest common divisor \(1\): successively taking greatest common divisors with elements of \(L\) gives a decreasing sequence of positive integers, which must eventually reach the greatest common divisor of the whole set. Set \(a=a_1\). Consider residues modulo \(a\). The residues of \(a_2,\ldots,a_k\) generate all residues modulo \(a\), because \(\gcd(a,a_2,\ldots,a_k)=1\). Each generated residue can be expressed using nonnegative, rather than signed, numbers of these residues: in the finite group of residues modulo \(a\), the additive inverse of a residue \(x\) is \((a-1)x\). Therefore, for every residue \(s\) modulo \(a\), there is a nonnegative integer combination \(b_s\) of \(a_2,\ldots,a_k\) whose residue is \(s\). Let \(B=\max_s b_s\). If \(t\ge B\) has residue \(s\), then \(t=b_s+qa\) for an integer \(q\ge0\). Consequently \(t\) is a nonnegative combination of return lengths in \(L\), and concatenating the corresponding return paths gives a positive-probability return path of length \(t\) (when the combination is empty, it is the length-zero path).
For each \(i\), choose a positive-probability path from \(i\) to \(r\) of length \(\alpha_i\); for each \(j\), choose one from \(r\) to \(j\) of length \(\beta_j\). Length zero is allowed when the starting and ending state are both \(r\). Let \(m=\max_{i,j}(\alpha_i+\beta_j+B)\), increasing it to \(1\) if necessary. For every \(n\ge m\), the integer \(n-\alpha_i-\beta_j\) is at least \(B\). The arithmetic argument supplies a return path at \(r\) of that length. Concatenating the path from \(i\) to \(r\), this return path, and the path from \(r\) to \(j\) gives a positive-probability path of length \(n\) from \(i\) to \(j\). Since \(P^n(i,j)\) is the sum of the probabilities of all such paths, \(P^n(i,j)>0\). In particular, \(P^m\) has every entry positive. \(\square\)
From Positivity to Minorization and Convergence
Write \(d=|S|\), let \(a=\min_{i,j}P^m(i,j)>0\), and let \(\nu\) be the uniform distribution on \(S\), so \(\nu_j=1/d\). The choice \(\varepsilon=\min\{\tfrac12,da\}\) is strictly between \(0\) and \(1\), and \(P^m(i,j)\ge\varepsilon/d=\varepsilon\nu_j\) for every \(i,j\). This is a minorization: every row of \(P^m\) contains the same probability component \(\varepsilon\nu\).
Proof of the convergence assertion. Define a matrix \(R\) by $$ R(i,j)=\frac{P^m(i,j)-\varepsilon\nu_j}{1-\varepsilon}. $$ Every entry is nonnegative by minorization, and for each \(i\), \(\sum_jR(i,j)=(1-\varepsilon)/(1-\varepsilon)=1\). Hence \(R\) is a transition matrix and \(P^m(i,\cdot)=\varepsilon\nu+(1-\varepsilon)R(i,\cdot)\). For any two probability distributions \(\alpha,\beta\), this decomposition gives \(\alpha P^m-\beta P^m=(1-\varepsilon)(\alpha R-\beta R)\). A transition matrix cannot increase total variation: indeed, \(\sum_j|\sum_i(\alpha_i-\beta_i)R(i,j)|\le\sum_i|\alpha_i-\beta_i|\sum_jR(i,j)=\sum_i|\alpha_i-\beta_i|\). Thus \(\|\alpha P^m-\beta P^m\|_{\mathrm{TV}}\le(1-\varepsilon)\|\alpha-\beta\|_{\mathrm{TV}}\).
A stationary distribution exists for every finite transition matrix. To see this, start from any distribution \(\eta\) and form \(\bar\eta_N=N^{-1}\sum_{k=0}^{N-1}\eta P^k\). The probability simplex is compact, so a subsequence converges to a probability distribution \(\pi\). Also \(\bar\eta_NP-\bar\eta_N=(\eta P^N-\eta)/N\), whose total variation tends to zero because the distance between two probability distributions is at most \(1\). Taking the subsequential limit gives \(\pi P=\pi\). If \(\pi'\) is another stationary distribution, then both are stationary for \(P^m\), and the contraction just proved gives \(\|\pi-\pi'\|_{\mathrm{TV}}\le(1-\varepsilon)\|\pi-\pi'\|_{\mathrm{TV}}\). Since \(\varepsilon>0\), this forces \(\pi=\pi'\).
Finally, write \(n=qm+s\), where \(q=\lfloor n/m\rfloor\) and \(0\le s<m\). Applying the contraction \(q\) times to \(\mu\) and \(\pi\) gives \(\|\mu P^{qm}-\pi\|_{\mathrm{TV}}\le(1-\varepsilon)^q\|\mu-\pi\|_{\mathrm{TV}}\le(1-\varepsilon)^q\). Multiplication by \(P^s\) cannot increase total variation, and \(\pi P^s=\pi\); hence \(\|\mu P^n-\pi\|_{\mathrm{TV}}\le(1-\varepsilon)^{\lfloor n/m\rfloor}\), as claimed. \(\square\)
The bound is geometric in blocks of \(m\) steps. It need not be sharp: the chosen positive power and the smallest entry of that power may give a conservative rate. Its importance is that it proves convergence uniformly over all initial distributions, and supplies an explicit bound once \(m\) and the entries of \(P^m\) are known.
Worked Example: Finding and Using a Positive Power
Consider \(S=\{1,2,3\}\) and $$ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$ The row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+\tfrac12+\tfrac12=1\). From state \(1\) one can move to \(2\); from \(2\) to \(1\) or \(3\); and from \(3\) to \(2\) or \(3\), so every state communicates with every other. State \(3\) has a one-step return, so its period is \(1\); irreducibility then makes the chain aperiodic.
Multiplying rows by \(P\) gives $$ P^2=\begin{bmatrix} \tfrac12&0&\tfrac12\\ 0&\tfrac34&\tfrac14\\ \tfrac14&\tfrac14&\tfrac12 \end{bmatrix},\qquad P^3=\begin{bmatrix} 0&\tfrac34&\tfrac14\\ \tfrac38&\tfrac18&\tfrac12\\ \tfrac18&\tfrac12&\tfrac38 \end{bmatrix}. $$ For instance, the first row of \(P^3\) is the second row of \(P^2\), because the first row of \(P\) sends the chain to state \(2\) with probability \(1\). Thus \(P^3\) still has a zero entry. Multiplying once more gives $$ P^4=\begin{bmatrix} \tfrac38&\tfrac18&\tfrac12\\ \tfrac1{16}&\tfrac58&\tfrac5{16}\\ \tfrac14&\tfrac5{16}&\tfrac7{16} \end{bmatrix}. $$ Its rows sum respectively to \(\tfrac38+\tfrac18+\tfrac12=1\), \(\tfrac1{16}+\tfrac{10}{16}+\tfrac5{16}=1\), and \(\tfrac4{16}+\tfrac5{16}+\tfrac7{16}=1\). The minimum entry is \(a=\tfrac1{16}\), so with \(m=4\), \(d=3\), and \(\nu\) uniform, the specified choice is \(\varepsilon=\min\{\tfrac12,3\cdot\tfrac1{16}\}=\tfrac3{16}\).
To check the stationary distribution, solve \(\pi P=\pi\). The equations include \(\pi_1=\tfrac12\pi_2\), \(\pi_3=\tfrac12\pi_2+\tfrac12\pi_3\), and \(\pi_1+\pi_2+\pi_3=1\). The second gives \(\pi_3=\pi_2\), and then the first gives \(\pi_1=\tfrac12\pi_2\). Normalizing yields \(\pi_2=\tfrac25\), \(\pi_1=\tfrac15\), and \(\pi_3=\tfrac25\). Substitution checks all coordinates: \((\pi P)_1=\tfrac12\cdot\tfrac25=\tfrac15\), \((\pi P)_2=\tfrac15+\tfrac12\cdot\tfrac25=\tfrac25\), and \((\pi P)_3=\tfrac12\cdot\tfrac25+\tfrac12\cdot\tfrac25=\tfrac25\). The theorem therefore gives \(\|\mu P^n-\pi\|_{\mathrm{TV}}\le(\tfrac{13}{16})^{\lfloor n/4\rfloor}\).
Worked Example: A Lazy Cycle
On \(S=\{0,1,2\}\), consider a chain that stays in place with probability \(\tfrac12\) and otherwise moves one step around the three-state cycle. Its transition matrix is $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac12&0&\tfrac12 \end{bmatrix}. $$ Each row sums to \(1\). The cycle transitions make the chain irreducible, and each state has a positive one-step self-transition, so it is aperiodic. Direct multiplication gives $$ P^2=\begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac14&\tfrac14&\tfrac12\\ \tfrac12&\tfrac14&\tfrac14 \end{bmatrix}. $$ Every row sums to \(1\), and every entry is positive. Here \(a=\tfrac14\), \(d=3\), \(m=2\), and \(\varepsilon=\min\{\tfrac12,3\cdot\tfrac14\}=\tfrac12\). Each column of \(P\) also sums to \(1\), so the uniform distribution \(\pi=(\tfrac13,\tfrac13,\tfrac13)\) satisfies \(\pi P=\pi\). The theorem gives \(\|\mu P^n-\pi\|_{\mathrm{TV}}\le(\tfrac12)^{\lfloor n/2\rfloor}\). As a direct check of the positive power, each entry of \(P^2\) is either \(\tfrac14\) or \(\tfrac12\), and each of its rows sums to \(\tfrac14+\tfrac12+\tfrac14=1\).
What Fails Without Aperiodicity
Worked Example: A Periodic Chain Does Not Converge
On \(S=\{1,2\}\), let $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Both rows sum to \(1\), and the chain is irreducible, but every return takes an even number of steps, so its period is \(2\). Its powers alternate: \(P^{2k}=I\) and \(P^{2k+1}=P\) for every integer \(k\ge0\). No power has all entries positive. The distribution \(\pi=(\tfrac12,\tfrac12)\) is stationary, as \(\pi P=(\tfrac12,\tfrac12)\), but from initial distribution \(\mu=(1,0)\), the distributions alternate between \((1,0)\) and \((0,1)\). Thus having a stationary distribution is not the same as convergence to it. The missing aperiodicity hypothesis is essential.
Common mistake. A zero entry in \(P^3\) does not show that the theorem fails, and a computation of a power must be checked by multiplying the rows correctly. In the first example, the first row of \(P\) selects the second row of \(P^2\), so the first row of \(P^3\) is \((0,\tfrac34,\tfrac14)\), not a mixture of the rows of \(P^2\). That zero is why \(P^3\) is not the required power; the verified \(P^4\) has all entries positive. More generally, the theorem guarantees existence of some positive power, not that the first power one tries will work.
Check Your Understanding
Use the path-length argument and minorization proof to justify your answers.
- Why does aperiodicity at one reference state provide return-path lengths with greatest common divisor \(1\)?
- In the first worked example, what is the minimum entry of \(P^4\), and what value of \(\varepsilon\) follows from the stated choice?
- Explain why the matrix \(R\) in the minorization proof has nonnegative entries and row sums equal to \(1\).
- Why does a transition matrix not increase total variation distance between two distributions?
- For the two-state alternating chain, state its stationary distribution and explain why the distribution from \((1,0)\) does not converge.