Why sort the states at all?
By now you can describe a chain completely: the transition matrix P holds every one-step jump, and the n-step matrix P^n — built by raising P to a power, as Chapman-Kolmogorov promised in the previous guide — tells you where you might be n steps from now. So you can compute. But computing is not yet *understanding*. Two chains can have very different long-run destinies even though both are just stochastic matrices, and the difference is hidden in the character of their individual states. This guide is about reading that character.
We will hang three questions on every state. First, recurrence vs transience: once I leave this state, am I guaranteed to come back, or might I wander off and never return? Second, if I do return, *how long* on average does it take — finite or infinite? Third, periodicity: are my returns locked to a fixed rhythm (only at multiples of some number d), or can they happen at irregular times? These three labels are not idle taxonomy. They decide whether the chain has an equilibrium at all, whether it converges to that equilibrium, and how fast. Everything in the next two guides rests on them.
Recurrence and transience: will home be seen again?
Fix a starting state i and let f(i) be the probability that the chain, starting at i, ever returns to i at least once. This single number splits all states in two. If f(i) = 1, state i is recurrent: return is certain. If f(i) < 1, state i is transient: there is a genuine chance, namely 1 - f(i), that the chain leaves i and never comes home. The whole theory of recurrence and transience grows from this one return probability.
Here is the beautiful consequence. Each time the chain is at i, the probability it ever comes back is f(i), independently of the past — that is the Markov property at work, since being at i wipes out history. So the total number of visits to i behaves like repeated coin flips: keep returning with probability f(i), stop returning with probability 1 - f(i). If f(i) = 1 you return forever — *infinitely many* visits. If f(i) < 1 the number of visits is geometric with finite mean 1 / (1 - f(i)) — the chain visits i a few times and then abandons it for good. Recurrent means visited infinitely often; transient means visited only finitely often. There is no middle ground.
This gives a clean computational test you can run straight from the matrix powers you already know how to build. The expected number of visits to i, starting from i, is the sum over all n >= 0 of P^(n)(i, i) — add up the diagonal entry across every power of P. State i is recurrent exactly when this sum diverges to infinity, and transient exactly when the sum is finite. So 'is this state recurrent?' becomes 'does a certain series of n-step return probabilities diverge?' — a question about the tail of P^(n)(i, i).
Return probability f(i) = P(ever return to i | start at i)
f(i) = 1 -> RECURRENT -> visited infinitely often
f(i) < 1 -> TRANSIENT -> visited ~ 1/(1 - f(i)) times, then gone
Matrix test (sum the diagonal across all powers):
expected visits to i = SUM over n>=0 of P^(n)(i, i)
diverges (= infinity) -> RECURRENT
finite -> TRANSIENTPositive vs null recurrence: how long is the trip home?
Recurrence guarantees you *will* come home, but says nothing about *when*. So recurrence itself splits in two by the expected return time. Let m(i) be the mean number of steps to return to i, starting from i — a special mean hitting time. A recurrent state is positive recurrent if m(i) is finite (returns arrive at a steady, healthy rate) and null recurrent if m(i) is infinite even though return is certain (you always come back, but the waits grow so heavy on average that their mean blows up).
Null recurrence sounds paradoxical — certain to return, yet infinite expected return time — but it is exactly the same flavor of paradox you met with heavy-tailed random variables: an event can have probability 1 while its waiting time has no finite mean. Crucially, null recurrence can only happen on an *infinite* state space. On a finite chain there is nowhere for probability to slowly drain off to, so every recurrent state is automatically positive recurrent, and (this is a handy fact) a finite chain always has at least one recurrent state — it cannot be transient everywhere, because the chain must be *somewhere* at every step and there are only finitely many places to be.
Why bother distinguishing these? Because positive recurrence is precisely the condition for a genuine equilibrium to exist. When a chain is positive recurrent, the stationary distribution pi exists, and the long-run fraction of time spent at i equals pi(i) = 1 / m(i): the reciprocal of the mean return time. States you bounce back to quickly carry high equilibrium weight; states you return to only sluggishly carry little. Null-recurrent and transient chains have no proper equilibrium — in the null case m(i) is infinite, so 1/m(i) collapses to 0 and no honest probability distribution survives. Hold that pi(i) = 1/m(i) link; the next guide makes it the centerpiece.
Periodicity: marching to a rigid beat
Even a beautifully recurrent state can refuse to settle, because of rhythm. Picture hopping between the two banks of a river, crossing on every single step: from the left bank you can only be back on the left bank after an even number of steps — 2, 4, 6, ... — never after an odd number. That forced beat is periodicity, and it is the last obstacle between a chain and a stable long-run distribution.
Precisely, the period of state i is the greatest common divisor of all the step-counts n at which return is possible — the gcd of every n with P^(n)(i, i) > 0. In the river example, returns happen only at even n, so the gcd is 2 and the state has period 2. If that gcd equals 1, the state is aperiodic: returns can occur at irregular, mutually-prime times with no rigid cycle. A wonderfully simple sufficient condition for aperiodicity is a self-loop — if P(i, i) > 0, then return is possible in one step, the gcd of a set containing 1 is 1, and the rhythm is broken. Even a single state where the chain can stay put kills periodicity.
Class properties: classify in clusters, not one state at a time
Here is the labor-saving theorem that makes all this practical. Recurrence, the positive-vs-null split, and periodicity are all class properties: states that communicate — recall the communicating classes from the structure of the chain, where i and j communicate if each is reachable from the other — necessarily share the same classification. If one state in a class is recurrent, every state in that class is recurrent; if one is positive recurrent, all are; if one has period 2, all do. So you never classify states one by one. You partition the chain into communicating classes, then label each *class* with a single recurrence type and a single period.
There is also a structural shortcut. A communicating class is *closed* if no arrow escapes it — once in, you can never leave. A closed class on a finite chain is recurrent; an *open* (non-closed) class is transient, because there is always a positive-probability route out, and over infinitely many visits you are sure to eventually take it and never come back. So the picture of a finite chain is: the chain drifts through the transient (open) classes for a while, then falls into one closed class and lives there forever. This is exactly the absorbing-chain story, where the closed classes are single absorbing states.
The friendliest case ties everything together. A chain is irreducible when the whole state space is a single communicating class — you can get from anywhere to anywhere. Then the entire chain is recurrent or transient as one unit, and shares one period. The cleanest theorems all start here: an irreducible, aperiodic, positive-recurrent chain has a unique stationary distribution and converges to it from any start. A famous infinite example shows why the labels bite — the simple random walk on the integer line is null recurrent in 1 and 2 dimensions (it returns, but the expected wait is infinite) yet *transient* in 3 dimensions and higher: a drunkard on a line or in a city eventually staggers home, but a bird flying randomly in 3D space may never see its nest again.