Long-run chain behaviour
A Socratic walk-through of long-run chain behaviour — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does a process with no memory beyond its current state settle into a fixed long-run pattern?
Consider a process that forgets. Tomorrow's condition depends on today's and on nothing earlier — not on last week, not on how long today's condition has lasted. The first expectation is that such a thing should wander unpredictably.
Instead something odd happens. Run it long enough and the fraction of days spent in each condition steadies to a fixed set of numbers that do not depend on where it started. How can forgetting generate regularity, and does it always?
Reasoning it through
REASONING #Write the process down. Suppose two conditions, sunny and rainy, and four numbers: sunny follows sunny with probability 0.9 and rainy with 0.1; rainy follows rainy with 0.5 and sunny with 0.5. That is the whole model — a transition matrix P, one row per current condition, each row summing to one.
Now the only question that matters. If today's chances of sun or rain are the vector π, what are tomorrow's? Each condition contributes its probability, spread according to its row. Tomorrow is π*P*, and n days on, π*P*ⁿ. The whole future is a matrix raised to a power, applied to wherever you began.
That reframes the puzzle sharply. Asking whether the process settles is asking whether π*P*ⁿ converges — and asking what it settles to is asking for a vector that stops changing. If π satisfies π*P* = π, another day leaves it alone. It is a fixed point, a left eigenvector of P with eigenvalue 1, and we call it stationary.
Solve for ours. Let π_s be the long-run share of sunny days. Sunny tomorrow arises from sunny today (0.9 of the time) or rainy today (0.5), so π_s = 0.9π_s + 0.5(1 − π_s), giving 0.6π_s = 0.5, π_s = 5/6 ≈ 0.833 and π_r = 1/6. Five sunny days in six, whatever today holds.
Does one always exist? For a finite chain, yes — eigenvalue 1 is guaranteed because every row sums to one. The delicate questions are whether it is unique and whether you converge to it, which are different conditions.
Uniqueness needs irreducibility: every condition reachable from every other. Split the chain into two clusters that cannot reach each other and it has two separate long-run patterns, and which you get is fixed by where you started — the memory you thought erased survives in the choice of cluster.
Convergence needs aperiodicity, the condition people skip. Take a chain that alternates strictly: A always goes to B, B always to A. The stationary distribution is (0.5, 0.5) and unique. But start at A and the distribution is (1,0), (0,1), (1,0) forever — never converging. The long-run average time in each state is still one-half, so time-averages behave even when the distribution does not. Periodicity does not break the equilibrium; it breaks the approach to it.
Add infinitely many states and a third condition appears. A chain can be irreducible and aperiodic yet have no stationary distribution, because probability leaks away to infinity. The simple random walk on the integers returns to its start with certainty — but the expected time until return is infinite, so it is null recurrent with no equilibrium to settle into. What is needed is positive recurrence: finite expected return time. The connection is exact: π_i = 1 / E[return time to i], so our rainy share of 1/6 says the expected wait between rainy days is six days.
The analogy
THE ANALOGY #Imagine a crowd milling between two rooms, each person independently obeying the same door-choosing rule each minute, nobody remembering where they were an hour ago. Yet the headcounts stop changing once as many people leave each room per minute as arrive — and that balance point is set by the rule alone, not by how the crowd stood when the doors opened.
A crowd genuinely averages over many people at once, whereas a single Markov chain is one wanderer, so what the chain converges to is a probability, not an observed count — and the equality of the two, the time-average of one path matching the ensemble average, is an extra theorem (the ergodic theorem) rather than a restatement.
Clarifying the model
THE MODEL #Three refinements worth carrying away.
First, "no memory" is a claim about the state, not the world. A process looks non-Markovian only if you have chosen too small a state: weather depending on the last three days is perfectly Markov if the state is the triple. Memorylessness is a modelling choice, and the honest question is not "is the world memoryless?" but "does this state carry everything that matters?"
Second, stationarity says nothing about how fast the process settles, and that is usually the practical question. The rate is set by the second-largest eigenvalue in absolute value. Our matrix has trace 0.9 + 0.5 = 1.4 and one eigenvalue is 1, so the other is 0.4: any initial discrepancy shrinks by a factor of 0.4 per day. Chains with a second eigenvalue near 1 are the troublesome ones — a perfectly good equilibrium that takes astronomically long to find, which is the failure mode of Markov chain Monte Carlo runs that appear converged and are not.
Third, stationary does not mean static. In equilibrium the chain still moves every step; what has stopped changing is the distribution over where it is, not where it is.
How would you falsify a claim that some real process has settled? Run it from deliberately different starting states and compare long-run frequencies — if they disagree, the chain is not irreducible and there is more than one equilibrium. Look for oscillation at a fixed lag; a converged chain shows none, a periodic one a clean cycle. And test the Markov assumption itself, the more common failure in applications: check whether the next state depends on the previous one given the current. If it does, the theory above does not apply to the variable you chose.
A picture of it
THE PICTURE #How to readThe two boxes are the only conditions the process can occupy, and it occupies exactly one at a time. Each arrow is a one-step probability, and the arrows leaving any box sum to one — that is the whole model, with no arrow referring to a day before today. Both entry arrows matter: the chain may begin in either condition, and the point is that the choice makes no difference after enough steps. The notes are not further states but the long-run shares those probabilities force — the balance point where traffic along the 0.1 arrow exactly matches traffic along the 0.5 arrow.
What became clearer
WHAT CLEARED #Forgetting makes the regularity possible rather than threatening it. Because each step applies the same rule to whatever distribution it finds, the process repeatedly composes one fixed map, and such a map has a fixed point that draws everything toward it. The starting condition is erased not by luck but by contraction — its influence shrinks geometrically, at a rate read off the second eigenvalue. But the tidy conclusion needs three conditions that are easy to state and easy to forget: every state reachable from every other, no strict cycling, and a finite expected return time. Fail the first and there are several equilibria; fail the second and there is one you never approach; fail the third and there is none at all.
Where to go next
ONWARD #- What detailed balance adds, and why reversible chains are the ones we can design and sample from.
- How mixing time is bounded in practice, since the second eigenvalue is rarely computable for a large chain.
Key terms
TERMS #| Term | What it means |
|---|---|
| Transition matrix | the table of one-step probabilities, each row a distribution over the next state. |
| Stationary distribution | a distribution π with π*P* = π, unchanged by another step of the chain. |
| Irreducible | every state reachable from every other, which makes the stationary distribution unique. |
| Aperiodic | not confined to returning only at multiples of some period, which is what allows convergence rather than oscillation. |
| Positive recurrence | return to a state is certain with finite expected waiting time; π is the reciprocal of that time. |
Every term the collection defines is gathered in the glossary.