1.42 Markov chains: study notes

Learn AI by Story

1. The idea in one sentence

A Markov chain is a system that hops between states where the chance of the next state depends only on the current state, not on the path that led there, and for many chains the long-run fraction of time in each state settles to a fixed stationary distribution π that satisfies π = πP.

2. The story from the video

Meena builds a weather app for her hill town. She notices that tomorrow's weather seems to depend mostly on today's. She keeps only two states, Sunny and Rainy, and writes down a small table of chances (illustrative data, not real measurements). After a sunny day, tomorrow is sunny with probability 0.8 and rainy with probability 0.2. After a rainy day, tomorrow is sunny with probability 0.4 and rainy with probability 0.6. Each row of the table adds up to 1.

She asks the app a question: "Today is rainy, so what is the chance of sun in the coming days?" Day 1 is 0.40. Day 2 is 0.56, which comes from 0.4 × 0.8 + 0.6 × 0.4. Day 3 is about 0.62. The numbers keep climbing and flatten out. When she starts the app from a sunny day instead, the numbers fall from 0.8 and also flatten out, at the very same value: 2/3. The chain forgets where it started.

She then finds that the flat value can be found directly, without running any days: it is the distribution that does not change when you apply the table once more, written π = πP. For her town that gives π = (2/3, 1/3), so about two days in three are sunny in the long run.

The video ends with cautions (the "memoryless" assumption is a modelling choice, and some chains never settle) and with where Markov chains show up: Google's PageRank random surfer, the next-word guessing of early language models, reinforcement learning, and, in the next videos, sampling methods. The next video is 1.43 Monte Carlo sampling.

3. Key definitions (glossary)

State: one of the possible situations the system can be in at a given step. Plain English: the label for "where we are right now", such as Sunny or Rainy.
Markov property: the probability of the next state given the whole past equals the probability given only the present, P(X₍ₙ₊₁₎ | X₀, …, Xₙ) = P(X₍ₙ₊₁₎ | Xₙ). Plain English: the present is all you need; the history adds nothing.
First-order Markov chain: a chain where the next state depends on exactly one previous state (Bishop, 11.2.1). Plain English: one day of memory.
Transition probability: the chance of moving from state i to state j in one step, written Pᵢⱼ. Plain English: one entry of the weather table.
Transition matrix: the square table P of all the Pᵢⱼ, with every row summing to 1. Plain English: the whole rulebook in one grid.
Homogeneous chain: a chain whose transition probabilities are the same at every step (Bishop, 11.2.1). Plain English: the rulebook never changes.
n-step probability: the chance of going from i to j in exactly n steps; it is the (i, j) entry of the matrix power Pⁿ (Grinstead and Snell, 11.1). Plain English: look n days ahead by multiplying the table by itself.
Distribution row vector: a row of probabilities over the states, such as (0.4, 0.6) for "40% sunny, 60% rainy". Plain English: our current belief about the state.
Stationary (invariant) distribution: a distribution π with π = πP, so one more step leaves it unchanged. Plain English: the balance point where the flows cancel.
Detailed balance: the condition π(i)Pᵢⱼ = π(j)Pⱼᵢ for all pairs of states. Plain English: the traffic from i to j equals the traffic back (Bishop, 11.2.1; sufficient for stationarity but not necessary).
Reversible chain: a chain that satisfies detailed balance. Plain English: filmed and played backwards, it looks statistically the same.
Irreducible chain: every state can be reached from every other state in some number of steps. Plain English: no islands.
Aperiodic chain: the chain does not lock into a fixed cycle length. Plain English: it does not tick like a clock between the same states.
Ergodic chain: a chain that is irreducible and aperiodic, which gives a unique equilibrium distribution (Bishop, 11.2.1; Grinstead and Snell, 11.3). Plain English: it forgets its start and settles to one answer.
Regular chain: a chain where some power of P has all entries positive (Grinstead and Snell, 11.1). Plain English: after enough days, any state can follow any state.
Absorbing state: a state that, once entered, is never left (Grinstead and Snell, 11.2). Plain English: a trap door.
Eigenvalue: a number λ with vP = λv for some nonzero vector v. Plain English: a scaling factor; the stationary distribution is the eigenvector for λ = 1 (Goodfellow et al., 17.3).
Mean first passage time: the expected number of steps to reach a given state for the first time (Grinstead and Snell, 11.5). Plain English: the average waiting time.
Mean return time: the expected number of steps to come back to a state you start in. Plain English: how long between visits; equals 1 ÷ π(state) (background: Kac's formula).

4. Detailed explanation, from basics to the full picture

Step 1: Start with states and a rule for hopping

Pick a finite list of states. For Meena that is {Sunny, Rainy}. A sequence of random states X₀, X₁, X₂, … is a Markov chain if each step obeys the Markov property: P(X₍ₙ₊₁₎ | X₀, …, Xₙ) = P(X₍ₙ₊₁₎ | Xₙ). Bishop calls this a first-order Markov chain and writes the whole joint distribution as a product of one starting distribution and a string of one-step conditionals.

Step 2: Write the rule as a transition matrix

Number the states 1 = Sunny and 2 = Rainy. Put the probability of "from i to j" in row i, column j:

P = [[0.8, 0.2], [0.4, 0.6]]

Rows are today and columns are tomorrow. Each row sums to 1 because from any state something must happen: 0.8 + 0.2 = 1 and 0.4 + 0.6 = 1.

Step 3: Push a distribution forward one day

If we hold a distribution as a row vector v = (v_sun, v_rain), then tomorrow's distribution is vP. For a rainy start, v = (0, 1), so vP = (0.4, 0.6): a 0.4 chance of sun. Each entry is a weighted sum: the new chance of sun is v_sun × 0.8 + v_rain × 0.4. That is the law of total probability applied once.

Step 4: Look many days ahead with matrix powers

Applying P again and again gives vP², vP³, and so on. Grinstead and Snell show that the n-step transition probabilities are exactly the entries of Pⁿ. So P² tells you the chance of each state two days from now, given each starting state, in one table.

Step 5: Watch the chain forget its start

Run the numbers for a rainy start and the chance of sun is 0.40, 0.56, 0.624, 0.6496, 0.6598, and about 0.6666 on day 10. For a sunny start it is 0.8, 0.72, 0.688, 0.6752, 0.6701, heading to 2/3. Two different starting points converge to the same number. That is the signature of an ergodic chain: a unique equilibrium distribution that does not depend on where you began.

Step 6: Solve for the stationary distribution directly

We want a row vector π with π = πP and entries adding to 1. For two states, write π = (a, 1 − a). The "sun" component gives a = 0.8a + 0.4(1 − a), which simplifies to a = 0.4a + 0.4, hence 0.6a = 0.4 and a = 2/3. The equivalent balance reading is: the flow from sun to rain, 0.2 × π(sun), must equal the flow from rain to sun, 0.4 × π(rain). So 0.2 π(sun) = 0.4 π(rain), which says π(sun) is twice π(rain). Therefore π = (2/3, 1/3).

Step 7: See why it settles, using eigenvalues

Goodfellow et al. (17.3) note that the stationary distribution is an eigenvector of the transition matrix with eigenvalue 1, and that the second-largest eigenvalue determines how fast the chain mixes. For Meena's P the eigenvalues are 1 and 0.4. The gap from the limit shrinks by a factor of 0.4 per day. For a rainy start: 2/3 − 0.4 = 0.2667, then 0.1067, then 0.0427, and so on. A second eigenvalue close to 1 would mean a slow-forgetting chain.

Step 8: Know when a limit exists

A unique limit needs the chain to be irreducible (every state reachable) and aperiodic (no fixed cycle). A chain that goes A, B, A, B, A, B forever never settles: it has a stationary distribution (½, ½) but the day-by-day distribution keeps flipping between "surely A" and "surely B".

5. Everything the video skipped

Variants

Absorbing chains: some states are traps; the questions become "what is the chance of ending in each trap" and "how long until absorption" (Grinstead and Snell, 11.2).
Regular and ergodic chains: regular chains are the cleanest case, with Pⁿ converging to a matrix whose rows are all π. Grinstead and Snell (11.4) call this the fundamental limit theorem.
Higher-order chains: let the next state depend on the last k states. Shannon (1948) built zero-order, first-order and higher-order Markov ("Markoff") approximations to English text, an early statistical language model. A higher-order chain can always be turned into a first-order chain by redefining the state as the last k symbols.
Continuous-state chains: states can be real numbers; the transition matrix becomes a transition kernel T(z, z′). Bishop uses this form for sampling.
Markov decision processes (background): add actions and rewards to a Markov chain; they are the standard model of reinforcement learning, coming later on the roadmap.

Formulas in simple words

Next-day distribution: v' = vP. In words: multiply the belief row by the table.
n days ahead: vPⁿ. In words: multiply by the table n times.
Stationary: π = πP and Σ π(i) = 1. In words: the balance point where one more step changes nothing.
Detailed balance: π(i)Pᵢⱼ = π(j)Pⱼᵢ. In words: flow i to j equals flow j to i. If it holds, π is stationary; the reverse need not be true.
Mean return time to state i: 1 ÷ π(i) (background: Kac's formula; Grinstead and Snell, 11.5 treat mean first passage times).
Convergence speed: distance to π shrinks roughly like (second eigenvalue)ⁿ.

Limitations

The Markov property is a modelling choice, not a law of nature. Real weather depends on pressure systems and seasons, not just on whether today was rainy. If the memory matters, enlarge the state (for example, "yesterday and today").
Estimating a transition matrix needs data for every row; with many states the table is huge and sparse.
Slow mixing: a chain with a second eigenvalue near 1 takes very long to forget its start (Goodfellow et al., 17.3 and 17.5).

Background

Andrey Markov studied these chains in the early 1900s (background). In the video series they matter because MCMC (video 1.44) designs a Markov chain whose stationary distribution is the distribution we want to sample from. Bishop (11.2) traces MCMC back to physics, to Metropolis and Ulam (1949) and Metropolis et al. (1953).

Links on the roadmap

Before this: probability basics. After this: 1.43 Monte Carlo sampling (how averages of random samples estimate things), then 1.44 MCMC (Metropolis-Hastings and Gibbs) where Markov chains are the engine.

6. Worked examples with real numbers

Example A: Two days ahead for Meena's weather

Setup: P = [[0.8, 0.2], [0.4, 0.6]], today is rainy (illustrative data).

Day 1 chance of sun: 0.4 (the "rainy" row, "sunny" column).
Day 2 chance of sun: 0.4 × 0.8 + 0.6 × 0.4 = 0.32 + 0.24 = 0.56.
Check with P²: row 2, column 1 of P² is 0.4 × 0.8 + 0.6 × 0.4 = 0.56, which matches. P² = [[0.72, 0.28], [0.56, 0.44]].
Day 3 chance of sun: 0.56 × 0.8 + 0.44 × 0.4 = 0.448 + 0.176 = 0.624.

Result: starting from rain, the chance of sun is 0.40, 0.56, 0.624 on days 1, 2, 3, climbing toward 2/3.

Example B: Finding the long-run weather by balance

Setup: same chain; find π with π = πP.

Let π = (a, b) with a + b = 1, where a is the long-run chance of sun and b of rain.
Flow from sunny to rainy per day is a × 0.2; flow from rainy to sunny is b × 0.4.
Balance means a × 0.2 = b × 0.4, so a = 2b.
Substitute in a + b = 1: 3b = 1, so b = 1/3 and a = 2/3.
Verify: (2/3) × 0.8 + (1/3) × 0.4 = 0.5333 + 0.1333 = 0.6667 = 2/3.

Result: π = (2/3, 1/3), about 66.7% sunny and 33.3% rainy in the long run.

Example C: How fast does the chain forget?

Setup: the eigenvalues of P are 1 and 0.4; start rainy.

The long-run sun chance is 2/3 ≈ 0.6667. At day 0 the chance is 0, so the gap is 0.6667.
Day 1 gap: 0.6667 × 0.4 = 0.2667, so the sun chance is 0.6667 − 0.2667 = 0.4000.
Day 2 gap: 0.2667 × 0.4 = 0.1067, so the sun chance is 0.5600.
Day 3 gap: 0.1067 × 0.4 = 0.0427, so the sun chance is 0.6240.
Day 5 gap: 0.6667 × 0.4⁵ = 0.6667 × 0.01024 = 0.0068, so the sun chance is about 0.6598.

Result: the gap shrinks by a factor of 0.4 every day, and these values match the table of 0.40, 0.56, 0.624, 0.6496, 0.6598.

Example D: Average waiting time between sunny days

Setup: the stationary distribution is π = (2/3, 1/3). Use the return-time rule (background: Kac's formula).

Mean return time to Sunny = 1 ÷ π(sun) = 1 ÷ (2/3) = 1.5 days.
Mean return time to Rainy = 1 ÷ π(rain) = 1 ÷ (1/3) = 3 days.
Sanity check: the long-run weighted average of 1 ÷ π(i) over the states is Σ π(i) × (1 ÷ π(i)) = 2/3 × 1.5 + 1/3 × 3 = 1 + 1 = 2, which equals the number of states, as the rule predicts.

Result: on average a sunny day recurs every 1.5 days and a rainy day every 3 days.

Example E: A 3-state chain (Land of Oz)

Setup: Grinstead and Snell's Land of Oz weather chain (from Kemeny, Snell and Thompson) has states Rain, Nice, Snow with rows (½, ¼, ¼), (½, 0, ½), (¼, ¼, ½). The two-step table below was computed with Python for these notes.

Row sums: ½ + ¼ + ¼ = 1; ½ + 0 + ½ = 1; ¼ + ¼ + ½ = 1.
Two days after a Rain day, the chance of Rain is ½ × ½ + ¼ × ½ + ¼ × ¼ = 0.25 + 0.125 + 0.0625 = 0.4375.
Doing the same for the other entries gives the Rain row of P² as (0.4375, 0.1875, 0.375).
Raising P to a high power makes every row approach (0.4, 0.2, 0.4).

Result: in Oz, long-run weather is 40% Rain, 20% Nice, 40% Snow, no matter where you start.

7. Comparison tables

Meena's chance of sun by start

Day	Start rainy	Start sunny
1	0.40	0.80
2	0.56	0.72
3	0.624	0.688
4	0.6496	0.6752
5	0.6598	0.6701
limit	0.6667	0.6667

Properties of chains

Property	Meaning	Why it matters
Irreducible	Every state reachable from every other	No isolated islands
Aperiodic	No fixed cycle length	No endless flipping
Ergodic	Irreducible and aperiodic	Unique equilibrium
Absorbing	Some state is a trap	Chain ends up stuck
Reversible	Detailed balance holds	Easy proof of stationarity

Memory in sequence models

Model	Remembers	Example
Zero-order	Nothing, only letter frequencies	Random letters
First-order	Previous symbol	Weather today to tomorrow
Higher-order	Previous k symbols	Shannon's English approximations

8. Common mistakes and myths

Myth: "Markov means the past does not matter at all." The past matters through the present state. If today's state already encodes what you need, the older days add nothing extra. If not, the model is simply too small.
Mistake: reading the matrix columns as the rows. In these notes rows are today and columns are tomorrow, and rows sum to 1. Columns need not sum to 1.
Mistake: expecting the chain to reach the limit exactly. The distribution only approaches π. After 10 days it is 0.6666, not exactly 2/3.
Myth: "Every chain has one long-run answer." A periodic chain such as A, B, A, B never settles, and a reducible chain can have different limits depending on where it starts.
Mistake: confusing the stationary distribution with a single trajectory. π describes long-run fractions or probabilities, not a prediction for tomorrow.
Mistake: assuming detailed balance is required. Bishop notes it is sufficient, not necessary, for a distribution to be stationary.
Myth: "The Markov assumption is true of the world." It is a modelling choice to be tested against data.
Mistake: using illustrative numbers as real climate facts. Meena's 0.8, 0.2, 0.4, 0.6 are made up for teaching.

9. Real-life and AI uses

PageRank: Wikipedia describes a random surfer who clicks links, and with probability 1 − d jumps to a random page, where the damping factor d is generally assumed to be around 0.85. The page importance scores are the stationary distribution of that chain (Wikipedia, used as a second source only).
Early language models: Shannon (1948) generated English-like text from first-order and higher-order Markov approximations, the ancestor of n-gram language models that predict the next word from the last few words.
Reinforcement learning (background): Markov decision processes extend chains with actions and rewards. This is covered later on the roadmap.
MCMC: Markov chain Monte Carlo builds a chain whose stationary distribution is the target we want samples from (Bishop, 11.2; Goodfellow et al., 17.3). This is the subject of video 1.44.
Physics origins: the Metropolis algorithm came out of statistical physics (Bishop, 11.2).
Everyday modelling (background): weather, queues, board games with dice, and web browsing patterns are often first modelled as Markov chains.

10. Self-check questions (with answers)

What is the Markov property? The next state depends only on the current state, not on earlier history: P(X₍ₙ₊₁₎ | X₀, …, Xₙ) = P(X₍ₙ₊₁₎ | Xₙ).
What must be true of each row of a transition matrix? Its entries are probabilities that sum to 1.
In Meena's chain, how do you get the day-2 chance of sun from a rainy start? 0.4 × 0.8 + 0.6 × 0.4 = 0.56.
What does the (i, j) entry of Pⁿ mean? The probability of going from state i to state j in exactly n steps.
What equation defines a stationary distribution? π = πP, with the entries of π summing to 1.
What is π for Meena's chain? π = (2/3, 1/3), from 0.2 π(sun) = 0.4 π(rain).
What controls how quickly the chain forgets its start? The second-largest eigenvalue; for Meena it is 0.4, so the gap shrinks by a factor of 0.4 per day.
Why does a chain that alternates A, B, A, B never settle? It is periodic, so the day-by-day distribution keeps flipping even though a stationary distribution (½, ½) exists.
What two properties together make a chain ergodic? Irreducible (every state reachable) and aperiodic (no fixed cycle).
What is the mean return time to Sunny in Meena's town? 1 ÷ π(sun) = 1.5 days.

11. Key takeaways, go deeper, next

Key takeaways

A Markov chain is defined by states and a transition matrix whose rows sum to 1; the next state depends only on the current one.
Multiplying a distribution by P moves it one step; Pⁿ gives n steps.
Ergodic chains forget their start and converge to a unique stationary distribution π with π = πP.
For Meena's chain, π = (2/3, 1/3) and the second eigenvalue 0.4 sets the forgetting speed.
The Markov property is a modelling choice, and periodic or reducible chains need care.

Go deeper

Read Grinstead and Snell, chapter 11, for absorbing chains, ergodic chains, the fundamental limit theorem, and mean first passage times.
Read Bishop, section 11.2.1, for detailed balance and reversibility.
Try it yourself: change Meena's matrix to [[0.9, 0.1], [0.3, 0.7]] and solve for π (balance method: 0.1 π(sun) = 0.3 π(rain), so π = (0.75, 0.25)).

Next on the roadmap: 1.43 Monte Carlo sampling.

12. Sources and further reading

Grinstead and Snell, Introduction to Probability (AMS), Chapter 11 Markov Chains: 11.1 transition matrix, 11.2 absorbing chains, 11.3 ergodic chains, 11.4 fundamental limit theorem, 11.5 mean first passage time
Bishop, Pattern Recognition and Machine Learning (2006), Section 11.2.1 Markov chains, within 11.2 Markov Chain Monte Carlo
Goodfellow, Bengio and Courville, Deep Learning (2016), Chapter 17 Monte Carlo Methods, 17.3 Markov Chain Monte Carlo methods
Shannon, A Mathematical Theory of Communication (1948), Markoff approximations to English text (PDF copy)
Wikipedia, PageRank (second source only), PageRank: random surfer and damping factor

Accuracy note: Meena's town, her states and her probabilities are illustrative data made up for teaching; the arithmetic was checked in Python. The Land of Oz two-step row and its limit (0.4, 0.2, 0.4) were computed for these notes from the matrix given by Grinstead and Snell. Items marked "(background)" are standard facts that were not taken from the listed sources.

Markov chains: study notes