Three structural facts, all of them read off the arcs and none of them off the probabilities. Two states communicate when each can reach the other, which partitions the states into classes. A class is recurrent when nothing leaves it — a statement about which arcs exist, not about how large they are — and transient otherwise. The period of a class is the greatest common divisor of its cycle lengths, and the lab computes it without enumerating a single cycle. Irreducible and aperiodic are the two hypotheses of the convergence theorem, and this page is where they become checkable rather than assumed.
Core ideas
Three properties of the same digraph. The first partitions the states, the second says which parts the chain settles into, and the third says whether it settles at all or merely returns on a schedule.
Reachability is reflexive (n = 0) and transitive (compose the paths), so two-way reachability is an equivalence relation and its classes tile the state space with no overlaps and nothing left over. That is why the lab can print a reachability table and a class list side by side: the second is forced by the first, and ↔ in the table is exactly the entries that share a class.
If some arc leads out of a class and never comes back, the chain takes it eventually — probability one, whatever the arc's size — and cannot return, so the class is visited finitely often. If no arc leaves, the class is closed and the chain that enters it stays. The test is a scan of the arcs out of the class, and a probability of 1/1000 decides it exactly as a probability of 1/2 does.
Take the lengths of all the cycles through a state and take their greatest common divisor. Enumerating cycles is expensive and unnecessary: level the class by breadth-first search and take the gcd of level(u) + 1 − level(v) over every arc u → v in it. Every cycle's length is a sum of those quantities, so the two gcds agree, and the second costs one traversal.
The material
Reachability and its classes, the arc test for recurrence, the period as a gcd, and the two hypotheses the one unproved theorem on this path needs.
State j is reachable from i, written i → j, when Pⁿ[i][j] > 0 for some n ≥ 0. States i and j communicate, written i ↔ j, when i → j and j → i.
↔ is an equivalence relation, and its classes are the communicating classes. A class C is closed, or recurrent, when no arc leads from a state of C to a state outside it, and transient otherwise. The chain is irreducible when there is exactly one class.
Reachability is computed as the transitive closure of the arc relation, so the table the lab prints is closed under composition rather than a list of single steps. A cell shows ↔ when the two states reach each other, → when only one direction works, and a dot when neither does; the ↔ cells are precisely the pairs sharing a class.
Suppose one arc leads out of C and does not lead back. Each visit to its tail takes it with some fixed positive probability, so over infinitely many visits the chance of never taking it is zero. The chain therefore leaves C with probability one and, since it cannot come back, visits C finitely often: that is what transient means. If instead no arc leaves, the chain that enters C can never be anywhere else, and every state of C is visited again and again.
Nothing in that argument used a magnitude. It used only that the arc exists and that the probability of never taking a fixed positive chance infinitely often is zero. This is the single most common place to reason about the wrong thing: a reader looking at 0.001 out of a class and 0.999 inside it sees a class the chain is basically never going to leave, and the correct answer is that it leaves, every time, eventually.
The three-state example 1/2 1/4 1/4; 0 3/4 1/4; 0 1/2 1/2 has classes {trial} and {kept, lapsed}. The first column is zero below the diagonal, so nothing returns to trial; the lab reports it transient and colours it red, and reports {kept, lapsed} recurrent because no arc leaves it.
The chain is therefore reducible, so the convergence theorem does not apply to it. It still has a unique stationary distribution — (0, 2/3, 1/3), which mode steady computes — and the zero is not a rounding: the chain spends finitely much of its time at trial, so the long-run fraction is exactly nothing.
The period of state i is d(i) = gcd{n ≥ 1 : Pⁿ[i][i] > 0}, the greatest common divisor of the lengths of the closed walks from i back to itself. States in the same class have the same period, so it is a property of the class. A class with d = 1 is aperiodic.
A self-loop forces d = 1 immediately, since 1 divides everything. A three-state ring with no other arcs has closed walks of lengths 3, 6, 9, … and therefore period 3: the chain returns to where it started only at multiples of three, for ever, and no amount of waiting changes that.
The lab does not enumerate closed walks. It levels the class by breadth-first search from one of its states and takes the gcd of level(u) + 1 − level(v) over every arc u → v inside the class. Each closed walk's length is the sum of those quantities along it, so every walk length is a multiple of that gcd; and each arc lies on some closed walk, so the gcd of the walk lengths divides it. The two divide each other and are therefore equal, and one traversal has replaced an enumeration.
If a finite chain is irreducible and aperiodic then Pⁿ[i][j] → πⱼ as n → ∞ for every i and j, where π is the unique solution of πP = π with Σπ = 1.
This is one of the three results the footer of this subject names as stated and not proved. What is proved here is nothing; what is computed here is both hypotheses, on whatever matrix you type, and the conclusion's π is obtained by solving a linear system in the material that follows — not as a limit.
A stated theorem whose hypotheses you can check is a different object from a stated theorem taken on trust. Both conditions are needed, and each fails on its own preset here. The three-cycle is irreducible and periodic: the powers return to the identity every third step and converge to nothing, while the linear system still has exactly one answer. The two-closed-group example is aperiodic and reducible: the powers do converge, and not to a single π, because there is no single π for them to converge to.
The four-state example 1/2 1/2 0 0; 1/2 1/2 0 0; 0 0 1/3 2/3; 0 0 1/4 3/4 has two classes, {a, b} and {c, d}, and both are recurrent: no arc leaves either.
So the chain is reducible with two recurrent classes, and the balance equations have a whole family of solutions rather than one. The lab reports two recurrent classes here and says that mode steady on the same matrix refuses to print one of them as though it were the answer.
Interactive
communicating classes, recurrence, and the period — the hypotheses, computed
Method
Arcs, then closure, then classes, then the two properties. Every step is about the pattern and none of them is about the numbers.
One arrow per positive entry, self-loops included. Cover the fractions up if it helps. Everything in this material is a property of the arrows, and keeping the magnitudes in view is how a reader talks themselves into treating a small probability as absent.
Find what each state can reach, following arrows as far as they go. Two states with arrows both ways share a class. The result is a partition; if you end up with a state in two groups, you have made an error, because communication is an equivalence relation and cannot overlap.
Scan the arcs out of the class. One that leaves and does not come back makes the class transient, however small it is. None at all makes it recurrent, and a chain with exactly one class is irreducible.
Level the class from any state and take the gcd of level(u) + 1 − level(v) over its internal arcs. A self-loop anywhere gives 1 straight away. Do not conclude “aperiodic” from having failed to spot a rhythm: the gcd is a computation and the eye is not.
Irreducible and aperiodic together are what the convergence statement needs. Either one alone is not enough, and both of the presets that break it are on the dropdown of this page.
The same four questions asked of four matrices: how many classes, is it irreducible, which classes are recurrent, and what is the period. Every answer below is read off the arcs.
Matrix A is the one to sit with, because it is the case where the intuition “transient means rare” is most tempting and most wrong. The chain starts at trial with probability one; it is there at step zero, and it may be there at step five. What makes {trial} transient is that the number of visits is finite with probability one, and the long-run fraction of time spent there is therefore exactly zero — a fact you will see printed as an exact 0 in the steady state, not as a small number.
Matrices B and C are the two failures, and they fail differently. B is irreducible, so the linear system has one answer; it is periodic, so the powers have none. C is aperiodic, so the powers settle; it is reducible with two recurrent classes, so what they settle to depends on where the chain started, and no single distribution is the answer.
For a rehearsal, take matrix B and add a self-loop: change the first row to 1/2 1/2 0 and renormalise nothing else, so the matrix reads 1/2 1/2 0; 0 0 1; 1 0 0. The supplied first move is that it is still irreducible. Work out the period before you type it: the closed walks now have lengths 1 and 3, so the gcd is 1, and one added arc has turned a chain whose powers never settle into one whose powers do.
You should be able to compute reachability and read the classes off it, decide recurrence by scanning for an escaping arc and say why the arc's size is irrelevant, obtain the period as a gcd rather than by observation, and state the two hypotheses of the convergence result together with a matrix that fails each one.
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.