Stationary Distributions as a Numerical Calculation
For a finite-state Markov chain, a stationary distribution can be found by solving linear equations. In an actual calculation, however, solving is only part of the task: the equations must be set up with the correct row-vector convention, and the resulting vector must be checked as a probability distribution and as an invariant vector. These checks are useful even when the calculation is exact, and essential when a numerical solver returns approximate values.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on the finite state space \(S=\{1,\ldots,m\}\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix is \(P=(p_{ij})\), with \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\); every entry is nonnegative and every row sums to \(1\). We write distributions as row vectors. A stationary distribution is a row vector \(\pi\) with nonnegative entries, \(\sum_i\pi_i=1\), and \(\pi P=\pi\).
It is convenient to solve for a column vector \(x=\pi^{\mathsf T}\). The balance equations are then \((P^{\mathsf T}-I)x=0\), together with \(\mathbf{1}^{\mathsf T}x=1\), where \(I\) is the identity matrix and \(\mathbf{1}\) is the column vector of ones. The balance equations are linearly dependent: their sum is always zero for any \(x\), because \(P\mathbf{1}=\mathbf{1}\). When the stationary distribution is unique, one can omit any one balance equation and replace it by the normalization equation. The result is a square system.
Why the Normalized System Works
Proof. Set \(A=P^{\mathsf T}-I\), and let \(x\) be the column vector formed by transposing the stationary distribution. Since \(P\mathbf{1}=\mathbf{1}\), we have \(\mathbf{1}^{\mathsf T}A=\mathbf{1}^{\mathsf T}P^{\mathsf T}-\mathbf{1}^{\mathsf T}=0\). Thus the sum of the \(m\) entries of \(Az\) is zero for every column vector \(z\). If \(m-1\) entries of \(Az\) are zero, the remaining entry must also be zero.
It remains to show that the reduced square system has a unique solution. Suppose \(z\) solves its homogeneous system: the retained balance equations give \(m-1\) zero entries of \(Az\), and the homogeneous normalization equation gives \(\mathbf{1}^{\mathsf T}z=0\). By the preceding sum argument, \(Az=0\) in every entry. The nullspace of \(A\) is one-dimensional: otherwise, there would be an invariant vector \(z\) not proportional to \(x\); subtracting \((\mathbf{1}^{\mathsf T}z)x\) would give a nonzero invariant vector \(w\) with zero sum. Since the stationary distribution \(x\) is strictly positive, \(x+\varepsilon w\) would still be nonnegative for all sufficiently small \(|\varepsilon|>0\), and would be a different stationary distribution with total mass one, contradicting uniqueness. Therefore \(z=cx\) for some constant \(c\). The zero-sum condition gives \(0=\mathbf{1}^{\mathsf T}z=c\mathbf{1}^{\mathsf T}x=c\), so \(z=0\). The homogeneous system has only the zero solution, hence the square system is invertible. The stationary distribution solves the system, so it is its unique solution. \(\square\)
This argument explains an important limitation. The normalized equations force invariance and unit total mass, but they do not by themselves force nonnegative entries. The theorem’s irreducibility assumption ensures that the solution equals the strictly positive stationary distribution. For a general chain, check nonnegativity separately; if there are multiple stationary distributions, the reduced square system may not have a unique solution.
Worked Example: Solving and Checking a Three-State Chain
Consider the chain on \(S=\{1,2,3\}\) with
Before using the matrix, check its rows: \(\tfrac12+\tfrac12+0=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(0+\tfrac12+\tfrac12=1\). The chain is irreducible: each neighboring pair communicates, so every state can reach every other state. Write \(x=(x_1,x_2,x_3)^{\mathsf T}\). The three balance equations from \(P^{\mathsf T}x=x\) are
Omit the middle equation and use \(x_1+x_2+x_3=1\). The first retained equation gives \(x_2=2x_1\); the third gives \(x_2=2x_3\). Hence \(x_1=x_3\), and normalization becomes \(4x_1=1\). Therefore \(x_1=x_3=\tfrac14\) and \(x_2=\tfrac12\), so \(\pi=(\tfrac14,\tfrac12,\tfrac14)\). Each entry is nonnegative and their sum is \(\tfrac14+\tfrac12+\tfrac14=1\).
Check the invariance residual. Multiplication gives \(\pi P=(\tfrac14,\tfrac12,\tfrac14)\): its first component is \(\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac14+\tfrac14\cdot0=\tfrac14\); its second is \(\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac12\); and its third is \(\tfrac14\cdot0+\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac14\). Thus \(r=\pi P-\pi=(0,0,0)\). The omitted middle balance equation also holds, as its left side is \(\tfrac12\cdot\tfrac14-\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac14=0\).
Interpreting the Checks
The three checks test different properties. A small residual indicates that the vector nearly satisfies the balance equations. A unit sum checks the normalization, while nonnegativity checks that the vector is a probability distribution. Neither a small residual nor a unit sum implies nonnegativity. Conversely, a vector can be nonnegative and sum to one without being invariant.
For a floating-point calculation, choose tolerances appropriate to the numerical method and the scale of the problem. For instance, report the maximum absolute residual \(\max_j |(\pi P-\pi)_j|\), the normalization discrepancy \(|\sum_i\pi_i-1|\), and the minimum computed entry \(\min_i\pi_i\). A residual that is small relative to the chosen tolerance is evidence of a numerically accurate solution, not a proof that the exact equations hold. Ill-conditioned systems can amplify small errors in the input or computation, so the residual should be interpreted alongside the system and the precision used.
For a reducible chain, a stationary distribution may have zero entries, or there may be many stationary distributions. A zero entry is not itself an error. In a non-unique case, a linear solver may return one normalized invariant vector, or it may report singularity; in either case, check nonnegativity and invariance directly. Normalization alone is never enough to call a vector a stationary distribution.
Worked Example: A Unique Stationary Distribution with Zero Entries
Consider \(S=\{1,2,3\}\) and
The row sums are \(1+0+0=1\), \(1+0+0=1\), and \(0+1+0=1\). State \(1\) is absorbing; state \(2\) moves to \(1\), and state \(3\) moves to \(2\). For \(x=(x_1,x_2,x_3)^{\mathsf T}\), the balance equations are \(x_2=0\), \(x_3-x_2=0\), and \(-x_3=0\). Omit the first equation and retain the other two with \(x_1+x_2+x_3=1\). The second retained equation gives \(x_3=x_2\), and the third gives \(x_3=0\); hence \(x_2=0\), and normalization gives \(x_1=1\). Therefore \(\pi=(1,0,0)\).
Check: the entries are nonnegative, sum to \(1+0+0=1\), and \(\pi P=(1,0,0)=\pi\). The zero entries are correct: the chain eventually enters state \(1\), and states \(2\) and \(3\) receive no stationary mass. Requiring every stationary probability to be strictly positive would incorrectly reject this answer; strict positivity is guaranteed for irreducible finite chains, not for every finite chain.
Worked Example: Why Normalization Does Not Guarantee a Stationary Distribution
Take \(S=\{1,2\}\) and \(P=I_2\), the identity matrix. Its rows are \((1,0)\) and \((0,1)\), each summing to \(1\). Every probability vector \((a,1-a)\) with \(0\le a\le1\) is stationary, because multiplying by \(I_2\) leaves the vector unchanged.
Here \(P^{\mathsf T}-I_2\) is the zero matrix. If we retain one balance equation and replace the other with normalization, the retained equation is \(0=0\), and normalization is \(x_1+x_2=1\). The vector \(x=(2,-1)^{\mathsf T}\) solves both equations, since \(2+(-1)=1\). But it is not a stationary distribution: its second entry is negative. In row-vector form, \((2,-1)P-(2,-1)=(0,0)\), so its residual is exactly zero despite its failure to be a probability vector.
Correction: the calculation has produced a normalized invariant vector, not a stationary distribution. Check nonnegativity; here \(-1<0\), so reject it. The example also shows why the uniqueness condition matters: the reduced system is not invertible, and its solutions include vectors that are not probability distributions.
A Reliable Workflow and a Common Pitfall
For a finite-state calculation, use the following order. First verify that the supplied matrix is a valid transition matrix by checking nonnegative entries and row sums of \(1\). Next form \(P^{\mathsf T}-I\), keeping the column-vector unknown \(x=\pi^{\mathsf T}\) consistent throughout. If uniqueness is known, replace one balance equation by \(\mathbf{1}^{\mathsf T}x=1\) and solve. Finally, verify nonnegativity, unit sum, and the residual \(x^{\mathsf T}P-x^{\mathsf T}\). If the system is singular, do not force a unique answer: determine whether there are multiple stationary distributions, and check any proposed vector against all three probability and invariance conditions.
Common pitfall: treating a normalized solution as a probability vector. In the identity-matrix example, the incorrect conclusion is “the equations and normalization hold, so \((2,-1)\) is stationary.” The correction is to apply the definition: a stationary distribution must also have nonnegative entries, and \(-1<0\). Another common calculation error is to use \(P x=x\) while treating \(x\) as a column vector under the row-stochastic convention. The correct column equation is \(P^{\mathsf T}x=x\); the row-vector equation is \(\pi P=\pi\).
Check Your Understanding
For each question, distinguish invariance, normalization, and nonnegativity rather than relying on only one check.
- Why does the sum of the entries of \((P^{\mathsf T}-I)x\) equal zero for every \(x\) when \(P\) is row-stochastic?
- In the three-state chain from the first worked example, verify the omitted middle balance equation by substituting \(x=(\tfrac14,\tfrac12,\tfrac14)^{\mathsf T}\).
- Can a vector have residual zero and total mass one but fail to be a stationary distribution? Give the vector and matrix from the example that demonstrate this.
- For a finite reducible chain, must every entry of a stationary distribution be strictly positive? Explain using the second worked example.
- What should be investigated if the normalized square system is singular rather than having a unique solution?