Why Average the Distributions?
A finite transition matrix need not have a stationary distribution that is immediately visible from its entries. Moreover, the distributions of a chain at individual times need not settle down: a chain can keep alternating between states. Averaging the distributions over time can remove this oscillation. The key fact is that one more step changes a long-run average by only a small boundary term.
Let \(S=\{1,\ldots,r\}\) be a nonempty finite state space, and let \((X_n)_{n\ge0}\) be a time-homogeneous Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Write \(\mu\) for the initial distribution as a row vector. The distribution at time \(n\) is \(\mu P^n\).
The averaging operation does not assert that the individual distributions \(\mu P^n\) converge. Instead, it produces a sequence \((\nu_N)\) in the finite-dimensional probability simplex. The theorem below shows that some subsequence of these averages converges to a stationary distribution.
Proof. First, finite sums and the definition of \(\nu_N\) give the telescoping identity $$ \nu_NP-\nu_N =\frac{1}{N}\left(\sum_{n=0}^{N-1}\mu P^{n+1}-\sum_{n=0}^{N-1}\mu P^n\right) =\frac{\mu P^N-\mu}{N}. $$ Both \(\mu P^N\) and \(\mu\) are probability vectors, so each of their coordinates lies in \([0,1]\). Thus, for each state \(j\), $$ \left|(\nu_NP-\nu_N)_j\right| =\frac{|(\mu P^N)_j-\mu_j|}{N} \le \frac{1}{N}\longrightarrow 0. $$ Next, every \(\nu_N\) has coordinates in \([0,1]\) whose sum is \(1\). By the Bolzano–Weierstrass theorem in \(\mathbb{R}\), the first coordinates of this sequence have a convergent subsequence. From that subsequence, extract one along which the second coordinates converge, and continue through the finitely many coordinates. The resulting subsequence \((\nu_{N_k})\) converges coordinate by coordinate to a vector \(\pi\). Since there are finitely many coordinates, taking limits in \(\sum_j(\nu_{N_k})_j=1\) gives \(\sum_j\pi_j=1\); taking limits in \((\nu_{N_k})_j\ge0\) gives \(\pi_j\ge0\). Hence \(\pi\) is a probability vector. Matrix multiplication by the fixed finite matrix \(P\) is a finite sum in each coordinate, so \(\nu_{N_k}P\to\pi P\). The telescoping bound also gives \(\nu_{N_k}P-\nu_{N_k}\to0\). Since \(\nu_{N_k}\to\pi\), it follows that \(\pi P-\pi=0\). Therefore \(\pi P=\pi\), as required. \(\square\)
The proof has two distinct ingredients. The telescoping identity ensures that any limit of the averages is invariant. Finite-dimensional compactness supplies at least one convergent subsequence. The result establishes existence; it does not claim that the stationary distribution is unique, or that \(\mu P^n\) itself converges.
Worked Constructions
Worked Example: Averaging a Two-State Cycle
Let \(S=\{1,2\}\), with transition matrix $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Each row sums to \(1\). Start the chain with \(\mu=(1,0)\). It alternates deterministically: \(\mu P^0=(1,0)\), \(\mu P^1=(0,1)\), \(\mu P^2=(1,0)\), and \(\mu P^3=(0,1)\).
Among times \(0,\ldots,N-1\), state \(1\) occurs \(\lceil N/2\rceil\) times and state \(2\) occurs \(\lfloor N/2\rfloor\) times. Therefore $$ \nu_N=\left(\frac{\lceil N/2\rceil}{N},\frac{\lfloor N/2\rfloor}{N}\right). $$ For \(N=2m\), this is \((1/2,1/2)\); for \(N=2m+1\), it is \(((m+1)/(2m+1),m/(2m+1))\). In either case, as \(N\to\infty\), \(\nu_N\to(1/2,1/2)\).
Check: Multiplication gives $$ (1/2,1/2)P=(1/2,1/2), $$ so the limit is stationary. In contrast, the individual distributions alternate between \((1,0)\) and \((0,1)\), and do not converge. This example shows why averaging can succeed even when taking the limit of the distributions at individual times cannot.
Worked Example: A Transient Starting State and Two Absorbing States
Let \(S=\{1,2,3\}\) and $$ P=\begin{bmatrix} 0&\tfrac12&\tfrac12\\ 0&1&0\\ 0&0&1 \end{bmatrix}. $$ The first row sums to \(0+\tfrac12+\tfrac12=1\), the second to \(0+1+0=1\), and the third to \(0+0+1=1\). Start in state \(1\), so \(\mu=(1,0,0)\). After one step the distribution is \((0,\tfrac12,\tfrac12)\), and it remains that distribution at every later time because states \(2\) and \(3\) each stay where they are.
Thus, for each \(N\ge1\), the time-zero distribution contributes \((1,0,0)\), and the other \(N-1\) distributions each contribute \((0,\tfrac12,\tfrac12)\). Consequently, $$ \nu_N=\left(\frac1N,\frac{N-1}{2N},\frac{N-1}{2N}\right) \longrightarrow (0,\tfrac12,\tfrac12). $$ The limiting vector is a probability distribution because its entries are nonnegative and \(0+\tfrac12+\tfrac12=1\).
Check: Multiplying the candidate by \(P\) gives $$ (0,\tfrac12,\tfrac12)P=(0,\tfrac12,\tfrac12), $$ so it is stationary. The calculation also shows that the particular stationary distribution produced by the averaging construction can depend on the initial distribution. The theorem promises existence, not a single choice that works for all initial laws.
Worked Example: An Explicit Nonperiodic Averaging Calculation
Consider \(S=\{1,2\}\) and $$ P=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ The first row sums to \(\tfrac12+\tfrac12=1\), and the second sums to \(\tfrac14+\tfrac34=1\). Start at state \(1\), with \(\mu=(1,0)\). Let \(x_n\) denote the probability of state \(1\) at time \(n\). Given probability \(x_n\) at state \(1\), the next-step probability of state \(1\) is $$ x_{n+1}=\tfrac12x_n+\tfrac14(1-x_n)=\tfrac14+\tfrac14x_n. $$ The fixed value of this recursion solves \(x=\tfrac14+\tfrac14x\), hence \(\tfrac34x=\tfrac14\) and \(x=\tfrac13\). Since \(x_0=1\), subtracting this fixed value gives \(x_n-\tfrac13=\tfrac14(x_{n-1}-\tfrac13)\), so $$ x_n=\tfrac13+\tfrac23\left(\tfrac14\right)^n. $$
The first coordinate of \(\nu_N\) is the average of \(x_0,\ldots,x_{N-1}\). Using the finite geometric sum, $$ (\nu_N)_1 =\frac1N\sum_{n=0}^{N-1}\left(\tfrac13+\tfrac23\left(\tfrac14\right)^n\right) =\tfrac13+\frac{8}{9N}\left(1-\left(\tfrac14\right)^N\right). $$ The second coordinate is one minus the first, so \(\nu_N\to(1/3,2/3)\).
Check: The row vector is normalized since \(\tfrac13+\tfrac23=1\). Its product with \(P\) is $$ (\tfrac13,\tfrac23)P =\left(\tfrac16+\tfrac16,\ \tfrac16+\tfrac12\right) =(\tfrac13,\tfrac23). $$ This verifies stationarity directly, independently of the limiting calculation.
What the Existence Result Does—and Does Not—Say
The finite-state assumption matters because it keeps all averaged distributions in a finite-dimensional probability simplex, where a convergent subsequence is guaranteed. For comparison, consider the countably infinite state space \(S=\{0,1,2,\ldots\}\) and the transition rule that moves from \(i\) to \(i+1\) with probability \(1\). There is no stationary probability distribution. Indeed, the stationarity equation at state \(0\) requires \(\pi_0=0\), since no state transitions into \(0\). For every \(j\ge1\), the equation requires \(\pi_j=\pi_{j-1}\). These equations force every \(\pi_j=0\), contradicting the requirement that the entries sum to \(1\). The finite-state theorem therefore cannot be extended to all countable chains without additional assumptions.
Even for finite chains, existence alone gives no uniqueness or convergence guarantee. In the two-state cycle, \((1/2,1/2)\) is stationary, but the distributions from the initial state \(1\) do not converge. Also, for the identity matrix on two states, every probability vector \((a,1-a)\), with \(0\le a\le1\), is stationary: multiplication by that matrix leaves every vector unchanged. Thus neither a unique stationary distribution nor convergence of \(\mu P^n\) follows from finiteness alone.
Common mistake. For the two-state cycle started at state \(1\), one might try to obtain a stationary distribution by taking the limit of \(\mu P^n\). The actual sequence begins $$ (1,0),\quad(0,1),\quad(1,0),\quad(0,1),\ \ldots $$ and has no limit. The correction is to average first: \(\nu_{2m}=(1/2,1/2)\) for every \(m\ge1\), while \(\nu_{2m+1}=((m+1)/(2m+1),m/(2m+1))\). Both subsequences tend to \((1/2,1/2)\), which satisfies the stationary equation. The averaging step, not an unverified assumption of convergence, is what makes the existence argument work.
Check Your Understanding
Use the definition of \(\nu_N\) and the stationary equation to check your reasoning.
- For a finite chain, expand \(\nu_NP-\nu_N\) and identify the two terms that remain after cancellation.
- Why does a coordinatewise convergent subsequence of probability vectors have a probability vector as its limit when the state space is finite?
- For the two-state cycle started at state \(1\), compute \(\nu_5\) and verify that its coordinates sum to \(1\).
- For the three-state example with absorbing states, verify by multiplication that \((0,\tfrac12,\tfrac12)\) is stationary.
- Give one reason the existence theorem does not imply that \(\mu P^n\) converges or that the stationary distribution is unique.