πP = π is n equations in n unknowns and one of them is implied by the others, because every column of P − I sums to zero. Drop any one of them by name, put Σπ = 1 in its place, and run exact Gauss-Jordan over the rationals: the steady state is a solution of a linear system and nothing iterates. Beside the solve the page runs the thing readers think a steady state is — repeated multiplication in floating point — and prints how far short it is. On one preset it is short by 2/3 at every step, for ever, because P³ is exactly P⁰ and no limit exists at all.
Core ideas
Three ideas. The first says what a steady state is, the second says why the obvious system is short of information, and the third is the claim this whole course exists to make.
π is stationary when one step of the chain leaves it unchanged: πP = π. That is an algebraic condition on a vector, and it says nothing about starting anywhere, waiting, or anything converging. Read as a linear system it is n equations, one per state, saying that the probability flowing into each state equals the probability flowing out.
πP = π is π(P − I) = 0, and every column of P − I sums to zero because every row of P sums to one. So the n equations have a linear dependency and the system is rank n − 1 at best: it pins π only up to a scale. Dropping one equation loses nothing, and Σπ = 1 supplies the one piece of information πP = π never had.
Power iteration reaches about fifteen decimal places on a well-behaved chain and then stops improving, because it has run out of double rather than out of steps. On the three-cycle it never improves at all: P³ is exactly the identity, the powers repeat for ever, and the error sits at 2/3. The linear system on that same matrix has one solution, and the solve had it before the iteration took its first step.
The material
The equation, the dependency, the replacement, the exact solve, the on-page verification, and the matrix where the two ideas come apart completely.
A distribution π is stationary for P when πP = π, that is Σᵢ πᵢ P[i][j] = πⱼ for every j, together with πᵢ ≥ 0 and Σᵢ πᵢ = 1.
Equivalently π(P − I) = 0 with the normalisation attached. Nothing in this definition mentions a starting distribution, a number of steps, or a limit.
For any transition matrix P, the columns of P − I sum to zero: Σⱼ (P[i][j] − I[i][j]) = 1 − 1 = 0 for every row i. Hence the n equations π(P − I) = 0 have rank at most n − 1, and one of them is implied by the rest.
Row i of P − I has entries P[i][j] for j ≠ i and P[i][i] − 1 at j = i. Its entries add to Σⱼ P[i][j] − 1, which is 1 − 1 = 0 because every row of P is a distribution.
So the all-ones column vector is in the null space of P − I acting on the right, which is exactly the statement that the columns — the equations of the system π(P − I) = 0 — sum to the zero functional. Adding all n equations together therefore gives 0 = 0, and any one of them can be recovered from the other n − 1.
□
That dependency is the reason the system as written cannot be solved: it determines π only up to a multiple, and π = 0 satisfies all of it. The repair is not a trick. One equation carries no information the others lack, so it is removed by name; and Σπ = 1, which πP = π never contained, takes its place. The lab prints the resulting system with the dropped equation named in the caption and the augmented column ruled off, and lets you choose which equation to drop. The answer does not move, and watching it not move is the point of the control.
The verification is not decoration. π is claimed to satisfy two things, and both are recomputed from the vector that came out of the elimination: πP is formed again and compared entry by entry with exact equality of fractions — not a tolerance — and the entries are added up. A page that asserted this instead of computing it would be a page you have to trust, and the whole reason the arithmetic here is rational is that claims of exact equality can be made and checked.
Beside the solve the page runs repeated multiplication in floating point from a corner of the simplex, for as many steps as you like, and prints the worst entrywise disagreement with the exact answer. On the three-brand matrix the disagreement is 2.882e-1 after one step, 2.255e-6 after twenty, and 2.776e-16 after sixty. After four hundred steps it is 3.331e-16, which is not better. The iteration has run out of double, not out of steps, and the exact column did not iterate at all.
Now switch to the three-cycle, 0 1 0; 0 0 1; 1 0 0. It is irreducible, so the balance system has exactly one solution and the page prints π = (1/3, 1/3, 1/3) with πP − π exactly zero. It has period 3, so the powers do something the word “slowly” does not describe: the lab finds that P³ is exactly P⁰, so the sequence of powers repeats with period 3 for ever. The largest entry of Pⁿ − π is exactly 2/3 at every single n, and the floating-point iteration sits at 6.667e-1 at one step, at four hundred steps, and at every step in between.
On the three-cycle the linear system is rank 3 against 3 unknowns and returns (1/3, 1/3, 1/3); powerCycles reports P³ exactly equal to P⁰; and the exact distance from Pⁿ to π is 2/3 for n = 1, 2, 3, 4, 5, 6 and onwards.
The sequence does not fail to converge slowly. It does not converge. And the steady state is not the limit of anything — it is the solution of three equations in three unknowns, which exists and is unique whether or not any limit does. That is what “a steady state is a linear system, not a limit” means, and this one matrix is where the two come apart.
The two-closed-group example is rank deficient: the reduced matrix has rank 3 against 4 unknowns, and the page says so and prints nothing. That is the right behaviour, because there is no shortage of solutions to print — there are infinitely many, and choosing one would be choosing. (1/2, 1/2, 0, 0) is stationary. (0, 0, 3/11, 8/11) is stationary. So is every mixture of the two, and each of those three vectors satisfies πP − π = 0 exactly when it is checked.
Note what the lab does and does not do there. It reports the rank and refuses; it does not exhibit the family. Exhibiting three members, as above, is a stronger demonstration of non-uniqueness than a rank is, because a rank is a claim about an elimination and three checked vectors are three checked vectors. Both are worth having, and they answer slightly different doubts.
Interactive
n dependent equations, one replaced by Σπ = 1, and an iteration that cannot match it
Method
Five steps, and the third is the one that turns an underdetermined system into a solvable one.
For each j, the inflow Σᵢ πᵢ P[i][j] equals πⱼ. Reading down a COLUMN of P is what gives the equation for that state, which is the opposite of how you read the matrix to take a step, and is worth saying out loud the first few times.
Add them all together and you get 1 = 1. The system is rank n − 1, so it fixes π only up to a scale and admits the zero vector. Discovering this after an hour of elimination is the usual route; discovering it from the column sums of P − I takes one line.
Any one. Say which one you dropped, so that the system you actually solved is on the page. Then add Σπ = 1, which is the piece of information πP = π never carried, and you have n independent equations in n unknowns.
Gauss-Jordan over the rationals. The three-brand example takes nine operations and gives (7/17, 11/34, 9/34), with the seventeenths there because seventeen is what the elimination produced, not because anything was rounded to it.
Multiply your answer back through the matrix and compare entry by entry. This costs one matrix-vector product and catches every arithmetic slip in the elimination. If the residual is exactly zero and the entries sum to exactly one, the answer is right — and “exactly” is available here because nothing was a decimal.
The three-brand matrix first, with each of the three balance equations dropped in turn and the normalisation put in its place. Then the two matrices that separate the solve from the limit.
Read the three-brand block first and notice what the three identical answers prove. If dropping a different equation gave a different π, the equations would be carrying different information and removing one would be a choice. They do not, so it is not.
The three-cycle block is the argument the whole of this material is for. Both columns are computed on the same matrix at the same moment: a unique exact answer on the left, and on the right a sequence with no limit whatsoever. “It has not converged yet” is the natural thing to say about 6.667e-1 after four hundred steps, and it is false; there is nothing to converge to, and the exact distance 2/3 is the same at every n rather than shrinking at any rate at all.
The leaky chain is the quiet one. Its π is unique because it has only one recurrent class, and it puts exactly 0 on the transient state. That zero is not a small number rounded down, and no floating-point iteration could have told you the difference: at sixty steps the iteration's worst error is 1.110e-16, which is indistinguishable from a genuinely tiny positive answer.
For a rehearsal, take the two-state chain 1/2 1/2; 1/4 3/4 and solve it by hand. The supplied first move is the balance equation at state one: 1/2 π₁ + 1/4 π₂ = π₁, which gives π₂ = 2π₁. Finish with the normalisation and check your answer against the lab; then ask why the iteration on that matrix stalls at fifteen places rather than sixteen, and what it would take to get the sixteenth.
You should be able to write the n balance equations from the columns of P, show that they are dependent from the row sums, drop one by name and normalise, eliminate in fractions and verify the answer by recomputing πP, and produce a matrix on which the system has a unique solution and the powers have no limit at all.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.