Chapter XV · 28 min
Markov Chains
Tomorrow asks only about today
“The probability of the next letter depends only on the letter just written.”
So far a random variable has been a number attached to one experiment. A Markov chain is a sequence of those numbers — today’s weather, tomorrow’s, the day after — with a merciful rule: the future cares about the past only through the present. You do not need yesterday’s rain to predict tomorrow, once you know today.
That rule is the whole subject. The linear algebra is a way of writing it down: a row of today’s chances, a table of “from → to”, a multiplication that produces tomorrow. We will do the multiplication by hand. Eigenvectors can wait; two equations will do.
Only today
Write for the state at times . The chain is Markov when
In English: given where you are, the next step forgets how you arrived. That is the same mood as the geometric and the exponential — memoryless — but now the “memory” that is discarded is the whole path, not just a waiting time.
The only matrices you need
A vector, here, is a row of numbers that add to one: today’s distribution over states. A matrix is a table. Each row of the table is “where I go tomorrow, given I am in this state today”. Those rows also add to one. Multiplying the row by the table is ordinary arithmetic: for each destination, add up “chance I am here × chance I step there”.
| Word | On the page | In English | In the weather |
|---|---|---|---|
| State | i, j | a place the chain can sit | Sun or Rain |
| Distribution | π | a row of chances, summing to 1 | (0.8, 0.2) — likely sun |
| Transition | P_{ij} | P(next = j | now = i) | P_{Sun,Rain} = 0.3 |
| One step | π P | tomorrow’s row, from today’s | multiply, then the new row sums to 1 |
If today is 80% sun,
That is matrix multiplication. You just did it. The compact line is . After two steps, — apply the table twice. No inverse, no determinant, no eigenvalue yet.
Where the crowd settles
Start at sun, or rain, or 80% sun. Apply the table again and again. For this weather, the row forgets its start and settles at one place:
Two unknowns, two honest equations. From the rain column (or sun — they are redundant once rows sum to one),
With , you get , hence , . In the long run this climate is sunny five days in eight, whatever the first day was. That settled row is the stationary distribution.
- Not every chain settles. A deterministic flip-flop Sun→Rain→Sun never forgets the parity of the day.
- If you can eventually reach anywhere from anywhere, and you are not trapped in a forced cycle, one stationary row exists and the crowd finds it.
- Absorbing states — “the game ended” — keep you once you arrive. Then the long run is “which ending?”, not a blend of weather.
Foundations studio: make the idea yours
This extended studio deliberately slows the pace. It is for a first-time learner who wants to recognize the idea in a new story, not merely reproduce a formula. Work with pencil and paper. Predict before calculating; redraw the pictures; and finish every numerical answer with a sentence in ordinary language.
A mental map before more algebra
A Markov chain is a controlled form of dependence through time. The current state is a sufficient summary of the past for predicting the next step under the model.
Do not treat the arrows as a theorem. They are a study aid. A strong probability habit is to move back one box whenever a formula feels unmotivated: ask what the experiment is, what information is available, and what quantity the question actually requests.
Three formulas worth being able to narrate
Read this line from left to right and explain what every symbol refers to in the experiment. If a symbol has no story, the model is not finished.
Now read the statement backwards: what would have to be known to use it? Backwards reading is often the difference between recognizing a formula and knowing when it applies.
Test the expression at an edge case or simple symmetric case. Probability formulas should survive sanity checks before you trust the arithmetic built on them.
Worked example ladder
A small experiment you can actually do
What usually goes wrong
When you notice this mistake, do not merely correct the final number. Return to the first line where the model became ambiguous. Probability errors are often representation errors wearing arithmetic clothing.
Questions beginners are right to ask
What do rows of a transition matrix sum to?
One, because each row is a conditional probability distribution over the next state given the current state.
Does every chain have a unique stationary distribution?
No. Conditions such as irreducibility and aperiodicity matter for uniqueness and convergence.
Can the state be designed?
Yes. A process that is not Markov under one state description can become Markov if the state is enlarged to include enough memory.
Where the abstraction earns its keep
For each application, ask what counts as an outcome, what the model treats as random, and which assumptions are approximations. This is how probability becomes a modelling language instead of a catalogue of formulas.
Connections: do not store chapters in separate boxes
Problem-solving clinic: from recognition to fluency
There is a stage where every worked example looks clear but a fresh problem still feels foreign. The cure is not another formula; it is practice choosing the representation. Before equations, do a sixty-second scan: identify the experiment, what is known, what remains uncertain, the quantity being asked for, the assumption doing the heavy lifting, and one impossible answer that gives you a sanity bound.
Case clinic A: Weather toy model
Today may influence tomorrow while yesterday matters only through today. A transition matrix encodes the chances of moving between sunny and rainy states.
Case clinic B: Random walk
At each position move left or right with stated probabilities. The chain state is the current position; path history matters only insofar as it determines that position.
Solve or reason about it twice: once exactly and once with a rough estimate, simulation, or symmetry argument. If the two approaches disagree dramatically, investigate before trusting the more sophisticated calculation.
Debug a confident wrong answer
Two questions to answer without notes
What do rows of a transition matrix sum to? One, because each row is a conditional probability distribution over the next state given the current state.
Does every chain have a unique stationary distribution? No. Conditions such as irreducibility and aperiodicity matter for uniqueness and convergence.
A notebook protocol for proficiency
Give this chapter one notebook page divided into four quadrants: picture, formula, example, mistake. Redraw the main visual from memory, narrate one formula in English, invent a fresh story using the same mathematics, and record the most tempting wrong move. Revisit the page after two days and again after a week.
A mastery check before you move on
Try these without looking back. If one item feels slippery, return to the corresponding example and rebuild it rather than memorizing the answer.
- Give a one-minute explanation of the chapter title to a curious teenager without a formula.
- Invent a tiny example with at most six elementary outcomes and solve it completely by enumeration.
- State one assumption that would make your example invalid and identify exactly which line would break.
- Draw the mental map from memory and connect at least two boxes to an earlier or later chapter.
- Write one question whose answer you still do not know. Good questions show that the concept has become active rather than passive.