4.18 Markov chains

What this is and why it exists

A Markov chain is the smallest model of a process that moves between states, and it earns its place by throwing away almost everything. Where the process goes next depends on where it is now, and on nothing that happened before. That one assumption is strong, and it is what makes every question about the chain answerable by matrix arithmetic instead of by reasoning about histories. The hidden Markov model in the next topic inherits the same assumption and adds one twist, so the effort spent here is paid back immediately. It is also the first place in this area where eigenvectors turn up doing something other than linear algebra homework.

The vocabulary

• State — one of the situations the process can be in.
• Markov property — the next state depends only on the present one.
• Transition probability — the chance of moving from one state to another.
• Transition matrix — all of those probabilities in a table.
• Row-stochastic — every row of the matrix sums to one.
• n-step probability — the chance of getting from one state to another in n moves.
• Stationary distribution — a distribution the chain leaves unchanged.
• Irreducible — every state can eventually reach every other.
• Aperiodic — the chain does not return only on a fixed cycle.

The mental model

The assumption comes first, because everything rests on it. The present state contains all the information relevant to the future; the path taken to reach it contains none. This is a real restriction and not a formality. Weather modelled as sunny or rainy today deciding tomorrow satisfies it approximately. A person's next purchase, if it depends on the whole shopping history, does not — and the usual repair is to enlarge what a state means until it does, which is exactly the trade you are making when you add history to a state.

A chain is one table. Rows are where you are, columns are where you go, entries are probabilities. Check the row sums before anything else. Each row is a full account of what happens next from that state, so it must add to one; a table failing that is not a chain and no result below applies to it. Reading a column instead of a row is the other common slip, and the row sums are what catch it.

Multiply the matrix by itself and you get the two-step behaviour. This is worth seeing rather than accepting. To get from one state to another in two moves you must pass through some intermediate state, so you add up, over every possible intermediate state, the chance of the first move times the chance of the second. That sum is exactly what one entry of the squared matrix computes. The n-step probabilities are the matrix to the power of n, and the general statement — that a path of length n splits at any intermediate point into a path of length k and one of length n minus k — is the Chapman-Kolmogorov relation. It says the chain is consistent with itself, which sounds trivial and is the reason powers of the matrix mean what you want them to.

A distribution multiplied by the matrix moves forward one step, and some distributions do not move. A row of probabilities over the states, multiplied by the transition matrix, gives the distribution one step later. The stationary distribution is the one that comes back unchanged. Written out, that is a vector unchanged by multiplication with the matrix, which is an eigenvector with eigenvalue one. The linear algebra from earlier in this area arrives here doing real work, and finding the long-run behaviour of a chain is finding that eigenvector and scaling it so its entries add to one.

Not every chain settles, and two conditions say which ones do. A chain is irreducible when every state can eventually reach every other, so no part of the space is a trap and no part is unreachable. It is aperiodic when returns to a state are not confined to multiples of some fixed number — a chain that alternates strictly between two states has period two and never settles, it oscillates. A chain with both properties settles to one distribution regardless of where it started, which is the result that makes the stationary distribution worth computing at all. Fail either and the long-run answer depends on the starting point, or does not exist.

Where this shows up next. Language models built from word transitions, page-ranking over links, queueing and reliability models, and immediately the hidden Markov model, where the states become invisible and you see only something emitted from them. The chain machinery does not change there — the transition matrix does the same job — so this topic is genuinely the foundation for the next one rather than a detour before it.

What you should now be able to explain or do

State the Markov property and give one process that satisfies it and one that does not. Write a transition matrix and check the row sums. Compute two-step and n-step probabilities by matrix powers, and explain the intermediate-state argument behind them. Find a stationary distribution as an eigenvector with eigenvalue one and normalise it. State irreducibility and aperiodicity, and say what fails without each.

Check yourself