The rule that forgets where it came from

Three states, called A, B and C, and a rule: from wherever the walk is now, the chance of each next state is fixed. Not fixed in advance for all time — fixed given the current state, and independent of everything before it. A process with that property has no memory beyond its position.

The question worth asking of such a rule is what it does in the long run. And the answer, when it exists, has a strange property: it does not depend on where the walk began.

The rule as a matrix #

The nine numbers in that diagram form a three-by-three array: the entry in row A, column B is the chance of moving from A to B. Every row adds to one, because the walk has to go somewhere, and the figure asserts it.

Written that way, one step of the walk is a multiplication. If the chance of being at each state is written as a row of three numbers, then multiplying that row by the matrix gives the chances after one step — each destination’s new share is the sum, over sources, of the chance of being there times the chance of moving from there.

Which means k steps is the matrix raised to the kth power, and the whole long-run question becomes a question about powers of one array of numbers. That translation is the only clever step in the subject, and everything after it is linear algebra.

Watching the rows come together #

Each row of the k-step matrix says where the walk is after k steps given where it started. So the rows disagreeing is exactly the statement that the starting point still matters.

Watch them. After one step, the entry in the A column runs from 0.10 to 0.40 depending on the row — a gap of 0.30. After two steps the gap is smaller. After eight, the three rows are 0.28, 0.35, 0.37 and 0.28, 0.35, 0.37 and 0.28, 0.35, 0.37. The figure measures the largest gap within a column and asserts that it never grows.

When the rows agree, the walk has forgotten. A walker who has been going for eight steps could have started anywhere, and the chances of finding them at each state are the same either way.

What “forgetting” is a claim about #

The word needs pinning down, because there are two things it could mean and only one of them is true here.

It does not mean the walk’s position becomes independent of its past. It never does: where the walk is now depends heavily on where it was one step ago, and that dependence is the entire rule. A walker at C is far more likely to be at C-adjacent states next than a walker at A is.

What it means is that the distribution stops depending on the start. After enough steps, the chance of finding the walk at B is the same whether it began at A, B or C — but any particular walk still has a history, and the last few steps of that history are still visible in where it is now.

The distinction matters because it is the difference between a statement about one trajectory and a statement about the ensemble of all of them. This site’s order out of noise theme is full of the same distinction: a random walk has a perfectly definite shape as a distribution and no shape at all as a path, and the bell curve from coin flips is a fact about many flips rather than about any of them.

The shares, by three routes #

The common row that the powers converge to has a name — the stationary distribution — and a defining property that is simpler than the limit it came from. It is the row of numbers that the matrix leaves unchanged. Apply the rule to it and get it back.

That is a system of linear equations, and solving it gives exact fractions: 12/43, 15/43 and 16/43, which as decimals are 0.2791, 0.3488 and 0.3721. No limit is taken and no power is computed. The figure solves the system, then separately iterates the rule sixty times starting from certainty at A, then separately walks the chain forty thousand times and counts visits, and asserts that all three agree — the first two to within a millionth, the third to within a hundredth.

The walk is seeded, so the third bar is a fixed number rather than a fresh experiment, which is a rule this site applies to every stochastic figure. What it corroborates is a claim of a different kind from the other two: not that a number satisfies an equation, but that a process actually spends that share of its time there.

Why the shares are an eigenvector #

The stationary distribution is defined by π times the matrix equals π, which is the equation for an invariant direction with the stretch factor equal to one.

So the whole subject sits inside a subject the site has already built. A transition matrix always has 1 as an eigenvalue — because the rows add to one, the column of all ones is fixed on the other side — and the stationary distribution is the corresponding eigenvector on the left, scaled so its entries add to one.

The convergence has the same explanation. Iterating a matrix pushes any starting vector towards the eigenvector with the largest stretch factor, and for a transition matrix that factor is 1 and the others are smaller. The rate at which the rows come together is set by the size of the second-largest, which is why the eight-step matrix agrees to two decimals and the two-step one does not.

That last sentence is the part that generalises furthest and the part no picture on this page shows. The gap between the largest and second-largest stretch factors is the whole story of how quickly a chain forgets.

The share, and the time spent there #

There is a second reading of the stationary distribution, and it is the one the third bar in that figure is about.

The first reading is a probability: after many steps, the chance of finding the walk at B is 15/43. That is a statement about an ensemble of walks and it is what the matrix powers converge to.

The second is a proportion of time: one walk, run for a long while, spends 15/43 of its steps at B. That is a statement about a single trajectory and it does not follow from the first — a process could perfectly well have the right distribution at every moment and spend its time in some other pattern.

For an irreducible finite chain the two coincide, which is a genuine theorem and not a restatement. The figure’s forty-thousand-step walk is a check on the second reading specifically, and the fact that it lands within a hundredth of the solved value is evidence for a claim that the other two computations never touch.

The same coincidence is what makes the expected return time to a state the reciprocal of its share. If a walk spends a sixteenth of its time somewhere, it comes back on average every sixteen steps — which is the collector’s 1/p argument from the neighbouring essay, applied to a chain instead of to a run of independent trials.

Where the limit does not exist: a rule with a period #

Take the rule that always moves round the ring. It is a Markov chain — the next state depends only on the current one — and every state is reachable from every other. Its powers do not converge to anything.

They cannot, because after k steps a walk that began at A is at a state determined entirely by k modulo three. The matrix cycles with period three, forever. The figure suppresses the “rows come together” assertion for this chain, because the assertion would be false and stating it would be the sort of thing this site exists to avoid.

But the chain does have a stationary distribution: a third, a third, a third. Applying the rule to that row returns it unchanged. So the stationary distribution can exist without being a limit. What fails is not the equation; it is the claim that iterating from an arbitrary start approaches its solution.

The condition that rules this out is called aperiodicity, and it is satisfied as soon as any state has some chance of staying put, or as soon as loops of two different lengths exist. The mixing chain at the top of this page has a chance of staying put at every state, and that alone is enough.

Where the limit does not exist: two rules that never meet #

The other failure is different in kind. Here the states split: A and B form a region with no way out, D is a state with no way out at all, and C is a doorway leading to either.

Every power of this matrix has rows that disagree, and always will. A walk that began at A stays in the A–B pair forever with certainty. A walk that began at D is at D forever. The starting point is never forgotten because there is no route between the parts.

This chain does not even have a unique stationary distribution — the row concentrated at D is stationary, and so is the balanced row over A and B, and so is every blend of them. A limit that depends on the start is not a limit of the process, and a stationary distribution that is one of infinitely many is not an answer to anything.

The condition that rules this out is irreducibility: every state reachable from every other, in some number of steps.

The two conditions, stated together #

A finite chain that is irreducible — every state reachable from every other — and aperiodic — not locked into a cycle of fixed length — has exactly one stationary distribution, and the powers of its matrix converge to the matrix all of whose rows are that distribution, from any start.

Both conditions are necessary and the two figures above are why. Neither is about randomness: the ring chain is perfectly random-looking as a rule and is entirely deterministic; the reducible chain has plenty of randomness inside each region and none between them.

The two-state chain in the figure is the smallest case where the theorem has content. Its shares are exactly a third and two thirds, which is what the ratio of the two leaving-chances forces: a state that is twice as sticky is occupied twice as often.

A chain is a graph with numbers on it #

The diagrams on this page are directed graphs, and that is not a presentational choice — the two conditions above are both statements about the graph alone, with the probabilities ignored.

Irreducibility says the graph is strongly connected: from any state there is a directed path to any other. Whether an arrow carries a chance of a half or a thousandth changes nothing about whether the path exists. The reducible chain fails on its shape, and it would fail the same way with any numbers in it.

Aperiodicity is also a property of the graph: the lengths of all the closed walks through a state must have no common factor above one. The ring has every closed walk a multiple of three, and a single self-loop anywhere would destroy that instantly.

So the qualitative question — does this chain have a limit at all — is a question in graph theory, of exactly the kind the bridges of Königsberg asks, and the numbers only start mattering once the answer is yes. That separation is unusually clean and it is worth keeping: two chains with completely different probabilities behave the same way qualitatively if their diagrams have the same arrows.

Both failures, read off the eigenvalues #

The two chains that have no limit were diagnosed above by looking at their diagrams — one is a locked cycle, the other falls into pieces. There is a second diagnosis that treats them as one phenomenon, and it is worth having because it explains why those two are the conditions rather than some third thing nobody thought of.

Start with what is true of every transition matrix. The eigenvalue 1 is always there, because the rows add to one. And no eigenvalue can have size greater than one, which takes a line: if some row of numbers is multiplied by the matrix, each new entry is an average of old entries weighted by a row of the matrix, so no new entry can exceed the largest old one in size. A stretch factor above one would have to make something bigger, and averaging never does. So the spectrum of a transition matrix sits inside the unit disc with at least one point on its rim.

Convergence is exactly the statement that 1 is the only point on that rim, and that it is there once. Everything strictly inside the disc dies away under iteration; what survives is whatever sits on the boundary. Two things can go wrong, and they are the two.

The ring chain has three eigenvalues on the rim. Its matrix is the cyclic shift, so cubing it gives the identity, so every eigenvalue is a cube root of one — the three cube roots of unity, each of size one exactly. Nothing decays. Iterating rotates the components of the starting vector through a cycle of three forever, which is the algebraic form of the sentence the walk’s position is determined by the step count modulo three. Period three in the picture is three roots of unity in the spectrum, and they are the same fact.

The reducible chain has the eigenvalue 1 twice. The A–B pair is a closed chain in its own right and contributes its own 1; the trap at D contributes another. An eigenvalue repeated means a whole plane of fixed rows rather than a single one, and a plane of solutions is precisely the infinity of stationary distributions the section above found by hand. Irreducibility is the condition that makes the eigenvalue 1 simple.

So the theorem in its spectral form reads: a finite chain that is irreducible and aperiodic has 1 as a simple eigenvalue and every other eigenvalue strictly inside the disc. That is the Perron–Frobenius theorem, and this is one of the places it earns its keep, since it turns two conditions that look like separate accidents of graph shape into one statement about where a spectrum sits.

It also delivers the rate for free. Once every other eigenvalue is strictly inside, the largest of them in size governs how fast the rest of the starting vector decays, so the gap between one and that size is the chain’s forgetting rate — and the number this page cannot draw is now identified rather than merely gestured at. It is the distance from the rim to the next-nearest eigenvalue.

What the picture cannot show #

The chains here are finite, and the interesting ones often are not. A random walk on the whole line is a Markov chain with infinitely many states, and everything above breaks in an instructive way — the walk that comes home returns to its start with certainty in one and two dimensions and not in three, and no stationary distribution exists in any of them, because there is nowhere for the shares to concentrate.

The rate is invisible. The figures draw one, two, four and eight steps because those fit on a page. Whether a chain forgets in eight steps or eight million is the question that matters wherever chains are actually used, and it is decided by an eigenvalue that no drawing here displays.

And the memorylessness is an assumption, not a finding. Every figure on this page begins with a matrix, and the matrix already encodes the claim that the past does not matter beyond the present state. Whether any particular process really has that property is not a mathematical question and nothing here bears on it.

Where the ladder goes next #

Two directions, and the site has ground on both sides.

Upwards, the questions get quantitative: not whether the chain forgets but how fast, which is a question about the second eigenvalue and which connects to how well a graph is connected. That is the machinery behind sampling methods that are used precisely because the stationary distribution can be arranged in advance — build a chain whose stationary distribution is the thing wanted, run it until it forgets, and read off where it is.

Sideways, the same object answers questions that are not about the long run at all. The coupon collector is a chain whose states are how many kinds have been seen and whose only moves are forward or stay put; its interesting quantity is the expected time to reach the end rather than any share of the long run, because it has no long run — it stops. Chains that stop are called absorbing, and the whole theory of them is about expected times rather than about limits, which is the same matrix asked a different question.