Three-State Chains by Balance Equations

Balance Equations for Three States

For a finite Markov chain, a stationary distribution is a probability law that remains unchanged after one transition. In a three-state chain, its coordinates can be found directly: balance the probability flowing into each state with the probability assigned to that state, then impose that the three probabilities sum to one. The main care is algebraic. The balance equations are not all independent, so normalization must be included rather than treating the three equations as unrelated equations for three unknowns.

Let $(X_n)_{n\ge0}$ be a Markov chain on the state space $S=\{1,2,3\}$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with discrete time $n\ge0$. Its transition matrix is $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$; each row sums to one. The chain is irreducible if for every pair of states $i,j$, there is some $n\ge0$ such that $p_{ij}^{(n)}>0$. A probability row vector $\pi=(a,b,c)$ is a stationary distribution if $\pi P=\pi$.

Definition: The coordinate balance equation for state $j$ is $\pi_j=\sum_{i\in S}\pi_i p_{ij}$. It says that the probability at state $j$ after one transition, when the current law is $\pi$, equals the probability assigned to $j$ by $\pi$. For three states, the equations are $$ \begin{aligned} a&=ap_{11}+bp_{21}+cp_{31},\\ b&=ap_{12}+bp_{22}+cp_{32},\\ c&=ap_{13}+bp_{23}+cp_{33},\\ a+b+c&=1,\qquad a,b,c\ge0. \end{aligned} $$

The transition matrix is row-stochastic, but $\pi$ is a row vector: the balance equation for coordinate $j$ collects the entries in column $j$, weighted by the probabilities of the states the chain could have occupied before the transition. These equations are simply the coordinates of $\pi P=\pi$, together with the probability constraints.

Why Two Balance Equations and Normalization Suffice

For any row-stochastic $P$, the three balance equations have a built-in dependence. Subtract the incoming probability from the probability at each state and sum the three residuals. The result is $$ (a+b+c)-\sum_{i\in S}\pi_i\sum_{j\in S}p_{ij} =(a+b+c)-(a+b+c)=0. $$ Thus, if the residuals for two coordinates are zero, the third residual must also be zero. For an irreducible three-state chain, any two coordinate equations are independent. The next result justifies this fact and also guarantees that the method identifies exactly one stationary distribution.

Theorem: Every irreducible transition matrix on $S=\{1,2,3\}$ has exactly one stationary distribution. Its coordinates can be found by solving any two coordinate balance equations together with $a+b+c=1$.

Proof. Existence. Start the chain with any probability row vector $\mu$, and for $N\ge1$ define the averaged row vector $\nu_N=\frac1N\sum_{n=0}^{N-1}\mu P^n$. Each $\nu_N$ has nonnegative coordinates summing to one. The set of such vectors is a closed and bounded subset of three-dimensional Euclidean space, so a subsequence $(\nu_{N_k})$ converges to a probability vector $\pi$. Also, $$ \nu_NP-\nu_N=\frac{\mu P^N-\mu}{N}. $$ Each coordinate of $\mu P^N-\mu$ lies between $-1$ and $1$, because both vectors are probability vectors. Therefore every coordinate of the right-hand side tends to zero as $N\to\infty$. Taking the subsequential limit gives $\pi P-\pi=0$, so $\pi$ is stationary.

Uniqueness and independence. Suppose a real column vector $x$ satisfies $Px=x$. Choose a coordinate $i$ where $x_i$ is maximal, with maximum $M$. The equation $x_i=\sum_jp_{ij}x_j=M$ is a weighted average of numbers no larger than $M$. Consequently, $x_j=M$ whenever $p_{ij}>0$. The same argument applies at every state reached along a path of positive transition probabilities from $i$. Irreducibility supplies such a path from $i$ to every state, so all coordinates of $x$ equal $M$. Conversely, every constant vector satisfies $Px=x$. Hence the null space of $I-P$ has dimension one, and $I-P$, as well as its transpose, has rank two. The stationary vectors are in the null space of $I-P^{\mathsf T}$, which therefore has dimension one. Since a stationary probability vector exists, it is the only stationary probability vector after normalization.

For completeness, no pair of coordinate balance equations is dependent: a dependence between two rows of $I-P^{\mathsf T}$ would give a vector in the null space of $I-P$ with one coordinate zero and the other two possibly nonzero. That null space consists only of constant vectors, so the vector must be zero and the proposed dependence is trivial. Finally, the sum of the three balance residuals is zero by the row-sum calculation above. Thus any two balance equations and normalization imply the third and determine the unique stationary distribution. $\square$

In practical calculations, it is often convenient to rearrange each balance equation by moving its self-transition term to the left. The resulting equations express how the probability that leaves a state balances probability arriving from the other states. The examples show both approaches: solving two equations, then checking all three coordinates directly.

Worked Example: A Directed Three-State Cycle

Consider the transition matrix $$ P=\begin{bmatrix} \tfrac{17}{21}&\tfrac{4}{21}&0\\ 0&\tfrac34&\tfrac14\\ \tfrac45&0&\tfrac15 \end{bmatrix}. $$ The row sums are $\tfrac{17}{21}+\tfrac4{21}=1$, $0+\tfrac34+\tfrac14=1$, and $\tfrac45+0+\tfrac15=1$. The positive transitions include the cycle $1\to2\to3\to1$, so every state can reach every other state. Find the stationary distribution.

Let $\pi=(a,b,c)$. The balance equations for states 2 and 3 give $$ b=\tfrac4{21}a+\tfrac34b,\qquad c=\tfrac14b+\tfrac15c. $$ Rearranging the first equation gives $\tfrac14b=\tfrac4{21}a$, so $b=\tfrac{16}{21}a$. Rearranging the second gives $\tfrac45c=\tfrac14b$, so $c=\tfrac5{16}b$. Substituting the value of $b$ gives $$ c=\tfrac5{16}\cdot\tfrac{16}{21}a=\tfrac5{21}a. $$ Normalization now yields $a+\tfrac{16}{21}a+\tfrac5{21}a=2a=1$. Therefore $a=\tfrac12$, $b=\tfrac{16}{21}\cdot\tfrac12=\tfrac8{21}$, and $$ c=\tfrac5{16}\cdot\tfrac8{21}=\tfrac{40}{336}=\tfrac5{42}. $$ The candidate is $\pi=(\tfrac12,\tfrac8{21},\tfrac5{42})$. Its coordinates sum to $\tfrac{21}{42}+\tfrac{16}{42}+\tfrac5{42}=1$.

Check by substitution. The first coordinate of $\pi P$ is $\tfrac{17}{21}\cdot\tfrac12+\tfrac45\cdot\tfrac5{42}=\tfrac{17}{42}+\tfrac4{42}=\tfrac12$. The second is $\tfrac4{21}\cdot\tfrac12+\tfrac34\cdot\tfrac8{21}=\tfrac2{21}+\tfrac6{21}=\tfrac8{21}$. The third is $\tfrac14\cdot\tfrac8{21}+\tfrac15\cdot\tfrac5{42}=\tfrac2{21}+\tfrac1{42}=\tfrac5{42}$. Hence $\pi P=\pi$.

Worked Example: A Fully Connected Chain

Let $$ P=\begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac13&\tfrac13&\tfrac13 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $\tfrac13+\tfrac13+\tfrac13=1$. Every entry is positive, so the chain is irreducible. Find its stationary distribution.

Writing $\pi=(a,b,c)$, use the equations for states 1 and 2: $$ a=\tfrac12a+\tfrac14b+\tfrac13c,\qquad b=\tfrac13a+\tfrac12b+\tfrac13c. $$ Multiplying the first rearranged equation by 12 gives $6a-3b-4c=0$. Multiplying the second rearranged equation by 6 gives $-2a+3b-2c=0$. The first equation gives $a=\tfrac12b+\tfrac23c$, and the second gives $b=\tfrac23a+\tfrac23c$. Substitute the expression for $b$ into the expression for $a$: $$ a=\tfrac12\left(\tfrac23a+\tfrac23c\right)+\tfrac23c =\tfrac13a+c. $$ Thus $\tfrac23a=c$, or $a=\tfrac32c$. Then $b=\tfrac23(\tfrac32c)+\tfrac23c=\tfrac53c$. Normalization gives $(\tfrac32+\tfrac53+1)c=\tfrac{25}{6}c=1$, so $c=\tfrac6{25}$, $a=\tfrac9{25}$, and $b=\tfrac{10}{25}=\tfrac25$.

Check by substitution. The first coordinate of $\pi P$ is $\tfrac9{25}\cdot\tfrac12+\tfrac25\cdot\tfrac14+\tfrac6{25}\cdot\tfrac13=\tfrac9{50}+\tfrac5{50}+\tfrac4{50}=\tfrac9{25}$. The second is $\tfrac9{25}\cdot\tfrac13+\tfrac25\cdot\tfrac12+\tfrac6{25}\cdot\tfrac13=\tfrac3{25}+\tfrac5{25}+\tfrac2{25}=\tfrac{10}{25}$. The third is $\tfrac9{25}\cdot\tfrac16+\tfrac25\cdot\tfrac14+\tfrac6{25}\cdot\tfrac13=\tfrac3{50}+\tfrac5{50}+\tfrac4{50}=\tfrac6{25}$. The coordinates sum to $\tfrac9{25}+\tfrac{10}{25}+\tfrac6{25}=1$, as required.

Worked Example: A Chain with Transitions in Both Directions

Consider $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac13&\tfrac13&\tfrac13\\ 0&\tfrac14&\tfrac34 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12=1$, $\tfrac13+\tfrac13+\tfrac13=1$, and $\tfrac14+\tfrac34=1$. The positive transitions connect 1 with 2 and 2 with 3 in both directions, so the chain is irreducible. Find $\pi$.

The balance equations for states 1 and 3 are $a=\tfrac12a+\tfrac13b$ and $c=\tfrac13b+\tfrac34c$. The first gives $\tfrac12a=\tfrac13b$, hence $b=\tfrac32a$. The second gives $\tfrac14c=\tfrac13b$, hence $c=\tfrac43b=2a$. Normalization gives $a+\tfrac32a+2a=\tfrac92a=1$, so $a=\tfrac29$, $b=\tfrac13$, and $c=\tfrac49$.

Check by substitution. The first coordinate is $\tfrac12\cdot\tfrac29+\tfrac13\cdot\tfrac13=\tfrac19+\tfrac19=\tfrac29$. The second is $\tfrac12\cdot\tfrac29+\tfrac13\cdot\tfrac13+\tfrac14\cdot\tfrac49=\tfrac19+\tfrac19+\tfrac19=\tfrac13$. The third is $\tfrac13\cdot\tfrac13+\tfrac34\cdot\tfrac49=\tfrac19+\tfrac13=\tfrac49$. Also $\tfrac29+\tfrac13+\tfrac49=\tfrac29+\tfrac39+\tfrac49=1$.

Checks, Interpretation, and a Common Error

A stationary distribution is an invariant law: if $X_0$ has distribution $\pi$, then $X_1$ also has distribution $\pi$, since the law of $X_1$ is $\pi P$. This definition does not itself assert that the distribution of $X_n$, from every starting law, converges to $\pi$. The calculation here is about solving the invariance equations, not about such a limiting claim.

Common pitfall: a mistaken substitution or omitted normalization. In the first example, the equations give $c=\tfrac5{16}b$ and $b=\tfrac8{21}$. Substituting gives $c=\tfrac5{16}\cdot\tfrac8{21}=\tfrac{40}{336}=\tfrac5{42}$. Using an incorrect value such as $b=\tfrac{10}{21}$ in that multiplication would instead produce $\tfrac5{16}\cdot\tfrac{10}{21}=\tfrac{50}{336}=\tfrac{25}{168}$, which is not the required coordinate. A separate error is to solve balance equations only up to a common multiplier and stop there: the resulting vector is not a probability distribution until its coordinates are normalized to sum to one.

For a three-state irreducible chain, a reliable calculation has four parts:

Check that every row of $P$ sums to one and that the chain is irreducible.
Write the coordinate balance equations using the columns of $P$.
Solve two independent balance equations together with $a+b+c=1$.
Substitute the proposed distribution into all three balance equations and check nonnegativity and total mass one.

Check Your Understanding

Use the coordinate equations and verify each proposed answer by substitution.

For $P=\begin{bmatrix}\tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac13&\tfrac23\end{bmatrix}$, first check the row sums and irreducibility, then find the stationary distribution.
Why does satisfying two coordinate balance equations for a row-stochastic three-state matrix force the third balance equation to hold?
For the first worked example, verify directly that $c=\tfrac5{16}b$ when $b=\tfrac8{21}$ and $c=\tfrac5{42}$.
Explain why a stationary distribution must also satisfy $a+b+c=1$, even if the coordinate balance equations have been solved.
State the difference between a stationary distribution and a claim that the distributions from a starting state converge to it.

Three-State Chains by Balance Equations

What You'll Learn