Solving Finite Stationary Systems with Gaussian Elimination

Why Stationary Equations Need a Normalization

A stationary distribution for a finite Markov chain is found by solving \(\pi P=\pi\), but this equation alone does not determine probabilities: it is homogeneous, so any scalar multiple of a solution is also a solution. The additional condition that the probabilities sum to one fixes the scale. There is a second issue: the stationary equations are linearly dependent. Gaussian elimination makes both facts visible and gives a reliable way to solve examples without guessing balance relations.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S=\{1,\ldots,m\}\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix \(P=(p_{ij})\) is row-stochastic, so \(\sum_{j=1}^m p_{ij}=1\) for every state \(i\). A stationary distribution is a row vector \(\pi=(\pi_1,\ldots,\pi_m)\) satisfying \(\pi_i\ge0\), \(\sum_i\pi_i=1\), and \(\pi P=\pi\). In the calculations below, we transpose this equation and treat \(\pi^T\) as a column of unknowns.

The normalization equation is \(\sum_i\pi_i=1\). It must be imposed along with stationarity, not inferred from the homogeneous equations. The key to reducing the system is that the stationary residual always sums to zero.

Proof. Let \(\mathbf{1}\) denote the column vector of \(m\) ones. Since \(P\) is row-stochastic, \(P\mathbf{1}=\mathbf{1}\). For any row vector \(\pi\), whether or not it is stationary,

Thus the sum of the \(m\) coordinates of \(r\) is zero. If any \(m-1\) coordinates of \(r\) are zero, the remaining coordinate must also be zero, proving the redundancy claim. Replacing one stationary equation by normalization retains the other \(m-1\) equations; those imply the omitted equation, and normalization adds exactly the required probability constraint. This reasoning also covers \(m=1\): there are no retained stationary equations, and normalization sets the sole probability to one. \(\square\)

In matrix language, set \(A=P^T-I\). The stationary equations are \(A\pi^T=0\). The dependence just proved implies \(\operatorname{rank}(A)\le m-1\), so there is at least one free direction before normalization. Row reduction reveals whether normalization leaves one solution or a family. If \(\operatorname{rank}(A)=m-1\), the nullspace has dimension one, and normalization gives at most one solution. If the rank is lower, there can be additional free variables; nonnegativity must still be imposed on any family of algebraic solutions.

A Practical Row-Reduction Procedure

For a finite chain, the calculation can be organized as follows. First check every row of \(P\) sums to one. Next form the stationary equations by equating the \(j\)th coordinate of \(\pi P\) with \(\pi_j\), for each \(j\). Select \(m-1\) of those equations, replace the remaining equation with \(\sum_i\pi_i=1\), and write the augmented matrix. Use exact fractions throughout. Finally, interpret any free variables and check both \(\pi P=\pi\) and \(\sum_i\pi_i=1\).

The choice of which stationary equation to omit does not affect the normalized solutions, by the theorem. A convenient choice is often the equation that makes the augmented matrix easiest to reduce. The method does not by itself assert that the stationary distribution is unique, nor does it say that the chain's distribution from an arbitrary initial law converges to the stationary distribution. Those are distinct questions.

Free Variables and More Than One Stationary Law

A rank-deficient system can remain underdetermined after normalization. In that case, row reduction describes the stationary vectors as a family, and the probability constraints determine which members of that family are distributions. The next example shows why it is important not to assume every finite chain has a unique stationary distribution.

Exact Elimination in a Four-State Example

In a larger system, Gaussian elimination is useful because it keeps the dependencies and arithmetic visible. A row operation replaces an equation by a linear combination that has the same solutions; multiplying an equation by a nonzero number or adding a multiple of one equation to another preserves the solution set. The following example displays the equations, reduces them using exact arithmetic, and verifies the resulting distribution in the original system.

Common Pitfalls and Interpretation

Common mistake: assuming a uniform vector is stationary without checking the columns. In the four-state example, the uniform candidate \((\tfrac14,\tfrac14,\tfrac14,\tfrac14)\) would give first coordinate of \(\pi P\) equal to \(\tfrac14(\tfrac12+\tfrac14)=\tfrac3{16}\), not \(\tfrac14\). So it is not stationary. Row-stochasticity means rows sum to one; it does not mean columns sum to one. Always substitute the candidate into \(\pi P\).

A second error is to treat all \(m\) stationary equations as independent and then infer uniqueness from having \(m\) equations. Their dependence is forced by row-stochasticity. Another is to omit normalization: the zero vector satisfies \(\pi P=\pi\) but is not a probability distribution. Finally, a valid stationary distribution describes an invariant law: if \(X_0\) has distribution \(\pi\), then the distribution remains \(\pi\) at every discrete time. Stationarity alone does not assert convergence to \(\pi\) from every starting distribution.

For a finite chain, existence of at least one stationary distribution is a standard finite-state result established in the earlier material on stationary distributions. Gaussian elimination addresses the calculation once the equations are written down. It also tells you when the normalized equations leave free variables, as in the two-absorbing-state example. A free parameter should be reported along with the constraints that make all entries nonnegative.