Chapter 13 handed us two engines for describing a pile of draws, and the second one left us holding σ/√n. Both engines assume the pile already exists. Now ask a question that unfolds in time. How many flips, on average, until you first see two heads in a row? Who goes broke first, and how long does it take? Nothing in the distribution family tree will answer either one, because those questions are about a process taking one step and then facing the same situation again. This chapter builds the one procedure that handles all of them. You stop trying to sum over an infinite future, and instead you decide what you must remember. That surviving summary is called a state, and once you have it, every question about the process becomes the same question asked again from wherever one step just took you. An unbounded process collapses into a handful of equations that solve each other. By the end you will re-derive 6 flips for HH and 4 for HT from a picture, know why a fair game between two equal players takes 2500 flips, and watch a die-rolling threshold rise from 3.5 to 4.667 as your right to walk away gets more valuable.
Check the shelf before we start. From Chapter 10: conditional probability, where conditioning shrinks the world down to one branch, and the law of total probability, which splits an event across a partition and adds the pieces back up. Chapter 11 handed over E[X] as a probability-weighted average, plus linearity of expectation, which survives dependence. Chapter 12 built the Geometric and its mean 1/p out of a recursion that folded back on itself. Chapter 6 left us matrices and the word singular. Chapter 7 left us eigenvectors. Every one of those gets spent here.
The seam — drag TIME and watch a pile of 2000 draws re-thread itself into one run of flips you can walk.
Drag TIME. The pile lifts off its axis and re-threads into one ordered run.
Drag TIME, then walk the flips. The two red buttons are the routes that look obvious and do not work.
drag TIME →
What you're looking at — the same 12 outcomes, first as a pile, then as a run in time
blue = Ch 13's world: a heap of draws, already collected. Its only questions are shape questions.
cyan = the same outcomes put in order, one step after another — the process this chapter is about.
gold = what you're asking for: μ and σ/√n on the left, the waiting time on the right.
red = the two dead ends. Neither works, which is why the chapter builds a state machine instead.
Fig. 1. Chapter 13 told you what a heap of independent draws looks like once you average it — a centre and a spread, nothing more. Drag TIME and the same twelve outcomes stand up in order, and a question appears that no histogram can touch: how long until HH? The two red stamps are the routes everyone tries first. Both fail, and that failure is the whole reason this chapter builds a state machine and writes one step, then the same expectation again.
That is the seam. The last chapter described what a heap of independent draws looks like once you average it. This chapter describes what happens step by step. So we start with a question the heap picture cannot reach.
01The question a distribution cannot answer
Here is the question. You flip a fair coin over and over until you see HH, two heads in a row, and then you stop. How many flips does that take on average?
Do not read on until you have written a number down. Guessing badly here is the point, and the correction is worth more than the answer.
Most people reason like this, and the reasoning feels airtight. The pattern HH sits in any two consecutive slots with probability ½ × ½ = ¼. Chapter 12 taught us that waiting for an event of probability p takes 1/p trials on average. So the answer is 4 flips, and I want you to write that number down and hold onto it.
Now try the same reasoning on HT, one head then one tail. That pattern also sits in any two slots with probability ¼, so the same argument gives 4 again. And for HT the answer really is 4, which is exactly what makes this trap so good, because the method appears to work.
The truth is that HH takes 6 flips on average and HT takes 4. One of those two answers came out of the Geometric formula correctly and the other one did not, and nothing in the formula tells you which.
Commit two numbers you will not get to check — then meet the flip that two tries are forced to share
1 · bet: flips until HH
bet: flips until HT
2 · slide the window →
set both dials, then LOCK each
Your two numbers stay sealed — they are opened in §14.2, not here.
What you're looking at — a bet you can't check yet, and the one flip two tries are forced to share
gold = your two sealed bets — dialled, locked, opened in §14.2
blue = window 1, the first two-flip slot the pattern could sit in
violet = window 2, the very next slot — one flip further along
red = the shared flip, inside both windows at once
green dashed = the trials 1/p imagined — they never touch
The only waiting-time tool you own so far is the Geometric's 1/p — "how many independent tries until the first success?" With p = 1/4 for a two-flip pattern, two tries cost 4 fresh flips, and 1/p duly says 4. But a two-flip window slid along one strip is not a fresh try: flips 1–2 and flips 2–3 share flip 2, so two windows cost 3 flips, not 4. That single crack is why 4 is the right answer for HT and the wrong one for HH — from the very same coin.
Fig. 2.The sealed bet, and the flip that two windows share. Dial a guess for each pattern and lock it — the pair is sealed and opened later, so you cannot quietly change your mind. Then slide the two-flip window along the strip: window 1 and window 2 sit one flip apart, and the flip they both contain lights red. Two tries, three flips — not four. Switch on treat as independent trials and the green ghosts show what 1/p actually assumed: two slots that never touch. They do not fit, which is why the Geometric hands you a confident number it was never entitled to give.
The tear is precise, and it is worth saying slowly. Chapter 12's 1/p counted independent trials. Think of what a "trial" would have to mean here. Flips 1 and 2 are one window, flips 2 and 3 are the next window, and those two windows share flip 2. Sharing a flip is the definition of not independent — so the tool was never licensed for this job.
You might reach for the other move instead: write down the probability of every possible outcome and sum. But the sample space here is infinite and ragged, since a run can end at flip 2 or flip 5 or flip 40, so there is no clean finite table to write. Both of your tools have now failed on the same question.
This is the honest position to be in, and almost no source will admit you are in it. When both of your tools break, the useful move is not to hunt for a third formula. It is to ask a much more basic question about the process itself.
Suppose I wipe your memory after every flip, and then, just before the next flip, I am allowed to tell you exactly one thing about everything that has happened. What do you want to be told?
Six real flip histories, one target HH — compare futures, cross out what cannot matter, keep what survives.
tap two histories to compare
What you're looking at — six pasts, one question: how many more flips until HH?
history A (first card you tap) and
history B — both replayed against the same three tapes of upcoming flips.
rows agree on every tape ⇒ the two pasts are interchangeable, so one can be crossed out.
a summary that splits an interchangeable pair is wrong — it remembers more than the future needs. (“last flip” would pass here too, but only because progress into HHis the last flip.)
Fig. 3. A state is not declared — it is what is left after you delete everything about the past that the future does not care about. Tap two histories: both are replayed against the same upcoming flips, and the panel counts how many more flips each needs to reach HH. When two pasts answer identically on every tape, nothing downstream can tell them apart, so one is crossed out. Six histories collapse to two. Then name what the survivors share: length, head-count and “ever seen a head” all split a pair whose futures were identical — they remember too much — and only how far into HH I am holds. TTHTH and a bare H are the same state; those four extra flips were wasted memory. That surviving summary is exactly the three-box machine at the bottom — and it is the machine that will turn E[HH] into two equations you can solve.
Play with that panel until the crossing-out feels obvious. The stream TTHTH and the single flip H lead to identical futures, so all the detail in the longer one was wasted. The stream TTHTT and the single flip T also lead to identical futures. What refuses to be crossed out is one small fact: how far into HH you currently are, which is either nothing or one head banked.
That surviving summary has a name. It is the state — the minimal thing you must remember about the past for the future to be decided. Notice that we found it before we named it, by crossing out everything that did not matter. That is the order to keep for the rest of your career, because the naming is easy and the finding is the skill.
Chapter 12's Geometric worked because after a failure you were exactly back at the start, so one starting point was enough. The whole of this chapter is what happens when a failure does not put you back at the start. More than one starting point is needed, and "more than one starting point" is the entire idea of a state.
02★ The machine, and the test that validates it
Draw the states as circles and the one-step chances as labelled arrows between them, and you have built a machine. A token sits on a circle. A coin tells it which arrow to take next.
For HH the machine has three circles: nothing, one H banked, and done. From nothing, a head moves you to one H banked and a tail leaves you where you are. From one H banked, a head finishes the job and a tail throws you back to nothing. Every arrow carries the label ½.
Three circles, four arrows, one live coin. Widen the token's memory as far as you like — nothing changes. Then let the arrow labels drift with the clock, and watch every equation on the page die.
running. Drag the memory window wider and watch nothing change.
row sums · ∅ 1.00 ✓ · H 1.00 ✓
hunting for the first HH…
What you're looking at — a machine whose whole memory is which circle it is standing on.
The circles and arrows are the chain. A tail after one head sends you all the way back to start — that throwback is the entire reason HH waits 6 flips while HT waits only 4.
Widening the memory window changes nothing. Ten remembered flips, zero consulted. Markov isn't amnesia — the state already is the past, compressed.
Two ways to break it. Drift the coin and the labels depend on when, so no single E exists. Tamper a label and a node's arrows stop summing to 1 — that isn't a chain at all.
Fig. 4. The whole chapter in one instrument. Three circles — start, one H, done — four arrows, each labelled with the chance of taking it, and a live coin driving a token around the loop. Watch the cruel arrow first: from one H, a tail does not nudge you sideways, it throws you all the way back to start. That single throwback is why HH averages 6 flips and HT only 4, from the same fair coin. Now the two properties that make the picture legal, each with its own switch. Markov: drag the memory window from 1 flip to 10 — the token is now allowed to see nine more coins than before, and it hops exactly as it did, because the circle it stands on already contains everything those flips could tell it. That's compression, not amnesia. Time-homogeneity: flip on DRIFTING COIN and p slides from 0.50 toward 0.20; every arrow label starts crawling, the equation card goes red — E now depends on when you are — and the running average wait walks off 6 and keeps going. Finally, drag tamper: give start's two arrows a sum of 1.15 and the audit turns red and the machine freezes, because a node that doesn't leave with probability 1 isn't a chain at all. Break either one and the tidy line E = 1 + ½·E_H + ½·E is worth nothing.
Two properties make that picture legal, and only one of them usually gets said out loud. The first is the Markov property: the token needs nothing except which circle it is on. Everything else about the history can be discarded.
Careful. The word "memoryless" is doing two different jobs in this course. Chapter 12's memorylessness was a property of a distribution, where a Geometric that has already waited ten trials looks brand new. The Markov property is a property of a process. The two fuse very easily into "the past does not matter".
The past does matter here, and the state is visibly made of the past, since "one H banked" is a fact about a flip that already happened. What the Markov property says is that the past is relevant only through the state. It is a claim about compression — not a claim about amnesia.
The second property is time-homogeneity. It is used in every single equation in this chapter and appears in almost no treatment of the subject. It says the arrow labels do not depend on the clock. The coin's bias at flip 40 is the same as at flip 1. If that were false, every result on this page would be false, and you would have no idea which assumption had broken.
One more small rule falls out of Chapter 9's axioms. The arrows leaving any single circle must have labels that add to 1, because after one step the token has to be somewhere. Freehand graphs that break this are the most common beginner error, and it happens because nobody ever says the rule.
Now the practical question, the one you will actually need. You have picked some states, so how do you know they are the right ones?
Target HTH. Choose what each circle is allowed to remember, then write a number on every arrow — one of them will refuse.
½
drag the ½ onto a dashed ? — or simply tap one
written 0 of 4 — tap a ?
What you're looking at — a machine for HTH with all its numbers rubbed off
a circle is a candidate state — everything you are allowed to remember.
a chip is the number on one arrow: flip · probability. A fair coin should make every one ½.
a chip that refuses: two different pasts land on that circle and demand different numbers.
a green circle passed — its arrows read ½ off the circle alone, no history required.
Fig. 5. Pick a state set and every arrow comes back blank. Fill the blanks with ½ and most of them accept — until one refuses. It refuses for a reason you can see: two different pasts arrive at that same circle and demand different numbers (½ from HT, but 0 from TH), and a probability that depends on how you got here is not a probability you can write on the node. That is the whole self-check: if labelling an arrow makes you ask about history, your state set is too small.DIAGNOSE names the forgotten fact in words, SPLIT THE NODE puts it back — and both wrong guesses repair into the same machine, the one that tracks how much of HTH you have already matched. Only then is each circle a genuine state, and only then can you write one equation per circle: E = 1 + ½E(next) + ½E(other). (Count-the-heads is short in more than one place; the figure fixes the first break, and the rest go the same way.)
That is the test, and it is the most useful criterion in the chapter. Try to write a number on every outgoing arrow using only the circle you are standing on. If you can, your states are sufficient. If you find yourself asking how the token got here, then the number you need is not on the node, and you are missing a state.
Run it on the bad state set for HTH and watch it fail concretely. If your circles only count how many heads you have seen so far, you cannot label the arrow out of "one head", because whether a T helps you depends on where that head sat. The failure is not vague. It points at exactly the fact you forgot to carry.
03★ The tool the whole chapter is written in
Before we write a single state equation, we need the tool they are all written in. Every source on earth writes a line like E = 1 + ½E₁ + ½E₂ and moves on. Ask which theorem that line is an instance of, and most readers cannot say, because they have never been handed one.
Here is a version you already believe. A coin decides which die you roll, and heads means a fair six-sided die with mean 3.5, while tails means a loaded one with mean 4.2. Nobody hesitates to write ½ × 3.5 + ½ × 4.2.
That is the law of total expectation, and it was in your hands the whole time without a name. Written out, it says E[X] = Σ P(Bi) · E[X | Bi] over any partition of the sample space.
Notice what is genuinely new in it. Chapter 11's linearity was about E[X+Y], and this is not that. This splits the sample space by an event and averages conditional expectations. It also drags in a new object, E[X | B], which is an average computed inside the shrunken world B.
A coin picks the die; you want the average roll. Step through the three honest lines — and watch the slices regroup.
two dice, one coin
What you're looking at — one average, built twice out of the very same slices
a blue slice is the part of a bar contributed by the heads die.
a gold slice is the part contributed by the tails die.
grey = Ch11's plain bar, x × P(X=x), before anyone mentions the coin.
the total never moves: 3.85 in six bars, 3.85 in two stacks. Only the order of adding changed.
Fig. 6. Everyone copies the line E = 1 + ½E₁ + ½E₂ without noticing it is a theorem. Here it is, assembled in three honest lines. Step 1 sets the stage: a coin picks which die you roll, so the sample space really is a heads half and a tails half, each with its own average (3.5 and 4.2). Step 2 writes nothing but Chapter 11's definition — E[X] = Σ x P(X=x) — and the six grey bars are exactly that sum, one bar per face, height = value × probability. Step 3 replaces each P(X=x) with Chapter 10's law of total probability, and every bar visibly splits into the part that came from heads and the part that came from tails. Step 4 is the entire trick: swap the order of the two sums. Add the slices face-by-face and you get 3.85; add them colour-by-colour and the blue ones pile up to ½ × 3.5 and the gold ones to ½ × 4.2 — the same 3.85, because regrouping a finite sum cannot change it. That is the law of total expectation, and it is why the self-referential waiting-time equation is legal rather than circular: the coin flip you already took supplies the 1, and each branch's E is an average in a genuinely different state — conditional expectations, weighted by their probabilities, exactly as here. Tap any bar in steps 2–3 to see its own two halves; the NUMBERS toggle runs the same four beats with arithmetic instead of symbols.
Three honest lines and no new machinery. Start from Chapter 11's definition, expand the probability with Chapter 10's law of total probability, swap the order of the two sums, and the inner sum is E[X | Bi] by definition. Say the parallel out loud as you finish. Chapter 10 conditioned a probability, and this conditions an average. Same shrink-the-world move, different quantity.
04★★ First-step analysis
Everything in this chapter pivots on the next idea, so we are going to set a trap first. Two questions, one card, and you must write both numbers before reading further.
How many fair flips, on average, until you first see HH? And how many until you first see HT?
Almost everyone writes the same number twice. The sharp readers even justify it out loud with the tool they just learned. Each pattern has probability ¼, heads and tails are interchangeable, so Chapter 13's symmetry should settle it. Let that reasoning stand for a moment, because it is exactly the reasoning that has to break.
Write both numbers down before you touch anything — flips until HH, flips until HT. Then open the bet and race two machines off one coin stream.
Write both numbers down first — set the two sliders, then LOCK IT IN.
Bet both, then LOCK IT IN.
What you're looking at — two identical machines, one arrow apart.
The gold arrow is the whole answer. Out of one H banked, the wrong flip for HT is an H — and an H is the start of HT, so it loops in place. The wrong flip for HH is a T, which starts nothing, so it falls to zero.
HH keeps getting knocked back — the ledger counts it — so its mean wait drifts to 6.
HT never falls: 0 knocked back, ever. Mean wait 4. Same coin, same 1/4 chance per pair of slots — different cost of failure.
Fig. 7. Two questions, one card: how many fair flips, on average, until you first see HH? Until you first see HT? Almost everyone writes the same number twice — usually 4 — and the sharp ones justify it: each pattern occupies any two adjacent slots with probability 1/4, and heads and tails are interchangeable. That reasoning is exactly the thing that has to break. Open the bet: HT takes 4, HH takes 6. Now don't read an explanation — look at the two machines. They are the same drawing three times over: nothing → one H banked → done, the same self-loop at nothing, the same forward arrows. One arrow differs. Out of one H banked, the wrong flip for HT is an H — and an H is the opening of HT, so the token loops onto itself and keeps everything it had. The wrong flip for HH is a T, which opens nothing at all, so the token drops the whole way back to zero. Press RUN and feed both machines the same coin stream: the blue token gets knocked to the floor again and again while the violet one merely waits — the ledger reads hundreds against a flat 0 — and the two running means walk apart and settle on 6.00 and 4.00. So the answer was never in the probability of the pattern, which is 1/4 for both. It is in what a failure costs you, and that cost lives in the graph. Which is why we drew the machine before writing a single equation, and why every problem from here starts with what must I remember? rather than what is the formula?
HT takes 4, and HH takes 6. Run the two machines off one shared coin stream, and the reason stops being algebra and becomes a picture of a single arrow.
Look at what happens after a wrong flip. In the HT machine, you have banked an H and you flip another H. You are not thrown backwards at all, because that new head is itself a perfectly good start for HT. In the HH machine, you have banked an H and you flip a T. That T is worthless to you, so you fall all the way back to nothing.
The answer was never in the probability of the pattern, which is ¼ for both. It is in what a failure costs you — and that cost lives in the graph, not in the pattern. That is why we drew the machine before writing a single equation.
Chapter 13's symmetry is a good tool. Name precisely why it misfires here, or you will end up quietly distrusting it everywhere. A valid relabelling has to preserve the law of the process. Swapping H and T is valid, and it maps HH to TT and HT to TH. Nothing maps HH to HT, so no symmetry argument ever claimed those two waits were equal.
Now build the equation the picture is pointing at. Condition on the very first step, using the law of total expectation with the partition "which arrow did that first step take". You spend one flip. You land on some circle, and from there the expected remaining time is the unknown attached to that circle — whichever one it turned out to be.
Written out, that is the whole chapter in one line:
E(s) = 1 + Σs′ P(s→s′) · E(s′)
One step, then the same question again. This is first-step analysis, and every remaining result on this page is that equation with a different quantity poured into it.
Your gut will object, and the objection deserves a real answer rather than a shrug. The unknown appears on both sides, so it looks like you are using E to compute E. That feels circular in a way that x = 3 + x/2 never does.
Is E = 1 + ½·E circular? Read the E on the right two ways — one loops forever, the other solves.
2 · the copy is only legal with both receipts — drag or tap them on
MARKOV
HOMOGENEOUS
the E on the right = this same run
What you're looking at — the same symbol E, read two different ways
E = the average number of flips still to come, starting from where you stand. The blue copy is a whole new run of that same question.
the 1 is the flip you already spent to leave s — the constant that breaks the circle (½·0 is the heads branch: done, nothing left to wait for).
pull a receipt off and the copy stops matching: it needs the past, or its arrows changed. Then the equation is not licensed.
both receipts on → copy = original → the two E's are the same number → solve: ½E = 1, so E = 2.
Fig. 8. The stall everyone hits: E shows up on both sides, so it feels like cheating. Read it the wrong way — the E on the right means this same run, still going — and substitution just nests forever: no step is ever paid, no number ever falls out. Read it honestly and one real flip happens first (that is the 1, and the drawer shows why a constant slides straight out of an expectation), after which what remains is a whole fresh copy of the same question, started at wherever you landed. The copy is only the same problem if two receipts hold: MARKOV — the state carries everything the past could tell you, so the copy needs no history — and HOMOGENEOUS — the arrow numbers did not change while you stepped. Pull either receipt off and watch the copy stop matching the original; put both back and the two E's are provably the same number, which is exactly what lets you treat it as an unknown and solve: ½E = 1, E = 2. That is the whole template, and it will answer HH, gambler's ruin and optimal stopping unchanged.
Here is the sentence that licenses it, and it is the one sources leave out. The E(s′) on the right is not the same run continuing. It is a fresh copy of the same problem — started at s′, from scratch. Those two things are numerically equal for exactly two reasons, and both were installed in the last section. The Markov property says the state summarises everything the past can offer. Time-homogeneity says the rules did not change while you took that step.
The +1 deserves the same treatment. Ask most people why it is there and they say "because you used a flip", which is true and ungrounded. The grounded version is linearity of expectation from Chapter 11, where total time equals one flip plus the remaining time. So E[total] = E[1 + remaining] = 1 + E[remaining], and the constant pulls straight out front.
05The ritual, and the grind that is the real skill
One equation per state, plus a boundary value, gives you a simultaneous linear system. Solving it is not conceptually hard, and it is where readers quietly give up. Three or four equations with halves everywhere, one lost substitution, and people blame their understanding when the failure was bookkeeping.
So here is a fixed ritual, short enough to fit on a card. Name the states, write one equation each, write the boundary, substitute from the target outward, and check.
Two of those five carry more weight than they look. The boundary is E(target) = 0, and it has to actually be written down. It feels like a non-statement, since of course you are done when you are done. Skip it and the system is under-determined and unsolvable, which reads to a learner as personal failure rather than a missing line.
The other one is direction. Beginners start from E(nothing), because that is the number they want, and then chase in circles. Start instead at the state nearest the target, where the boundary already gave you a value, and substitute outward. Nobody teaches that, and it is the same instinct that becomes backward induction later in this chapter.
Run it on HHH and watch every line. From HH, a head finishes and a tail sends you home, so E(HH) = 1 + ½·0 + ½·E(∅). From H, a head advances and a tail sends you home. From ∅, a head advances and a tail leaves you put. The system gives E(∅) = 14, E(H) = 12, and E(HH) = 8.
CodeRun — solve the waiting time twice: back-substitution from the boundary outward, then (I−Q)t = 1. Same numbers, both times.
HHH · 4 states, only 1 known
block 1 of 5 · the machine
# wait.py seed 20260813for i in range(L):
h,t = nxt(i,'H'), nxt(i,'T')
eq: t[i] = 1 + .5t[h] + .5t[t]
t[L] = 0# THE BOUNDARY
solve(I - Q, ones) # route 2
What you're looking at — one equation per state, and the one line that makes them solvable
Each state is how much of the target you already hold — nothing else about the past matters, which is exactly what Markov means. Tap a state to light up its own line in the run.
A flip that advances you. Every equation reads t = 1 + (the same wait again) — and that 1 is a real flip already spent, which is why defining t in terms of t is not circular.
A flip that throws you back. This is the whole asymmetry: HHH needs 14 flips, HTH 10, THH only 8 — same coin, same length, different overlap.
The boundary, t(target) = 0, and the answers it unlocks. Delete it and every state points at another unknown: numpy returns Singular matrix. That is what the boundary was worth.
Fig. 9. The same waiting time solved twice — by hand from the boundary outward, then as (I−Q)t = 1 — then checked against 100,000 simulated flip streams.
Now line up the answers for runs of heads and look for a pattern. One head takes 2, two heads take 6, three heads take 14. Predict four heads before you compute it. The rule is 2k+1 − 2, so four heads takes 30 and five takes 62. A grind just turned into a pattern hunt, and you leave with a self-check.
The same system has a second face. Collect the transitions between the not-yet-finished states into a matrix Q, and every equation at once becomes (I − Q)t = 1, where t is the vector of expected times. Chapter 6 already told us when such a system has a unique solution, which is exactly when I − Q is invertible.
And here is where an abstract word cashes out. Chapter 6 said singular means one thing — the transformation collapses space and cannot be undone. Here it fails to be invertible in exactly one case: the token has somewhere it can get stuck forever and never be absorbed. A statement about a matrix turns out to be a statement about the process.
06Every arrow in one table, and two destinies
Pack the arrow labels into a table, one row per state, and you have the transition matrixP. Row i says where you can go from state i, so every row sums to 1. A matrix with that property is called stochastic.
Fix the convention now and keep it for the rest of the course, because two textbooks use two conventions and one symbol. Rows are from, columns are to, and a distribution is a row vector that multiplies on the left. Mix that up and you get a transposed answer that looks entirely plausible.
Take a small market with two regimes, calm and turbulent. From calm, tomorrow is calm with probability 0.90 and turbulent with 0.10. From turbulent, tomorrow is calm with 0.30 and turbulent with 0.70.
Now answer a two-day question the way you already can. Starting calm, how likely is turbulence in two days? There are exactly two paths to count. Calm to calm to turbulent is 0.90 × 0.10 = 0.09, and calm to turbulent to turbulent is 0.10 × 0.70 = 0.07. Add them and you get 0.16.
C = calm, T = turbulent. Rows are FROM, columns are TO — tap any cell of Pn and watch its paths add up.
row C · 0.840 0.160
row T · 0.480 0.520
paths/row 2^2 = 4
tap a cell in the matrix ↑
Tap a cell to sum its paths
What you're looking at — each entry of Pn is a bag of paths, added up.
the chain and its matrix: row = the state you are in, column = the state you go to
the paths being summed — and the 0.25 the column settles on
ARRIVING: first reaching turbulent at exactly step n — equal to BEING only at n = 1
the transposed reading: same digits, rows no longer sum to 1
Fig. 10. Two states, four arrows, and the only number you are allowed to write on an arrow is the chance of taking it — so the two arrows leaving C must sum to 1, which is why rows sum to 1 and columns need not. Now tap (from C, to T) in P². There are exactly two ways to be turbulent two steps after being calm: stay calm then break, 0.90 × 0.10 = 0.09, or break then stay broken, 0.10 × 0.70 = 0.07 — total 0.16, and that is the number the cell was holding all along. The thing being summed over is the state you were in at the middle step, which makes matrix multiplication nothing more exotic than the law of total probability from Chapter 10, applied at time 1. Push n up and the same sum runs over 2n paths without you doing any more work, and every row slides to (0.750, 0.250) — forget where you started. Press TRANSPOSE MY CONVENTION to watch the identical digits produce a plausible-looking table whose rows sum to 1.32; a row that does not sum to 1 is not a distribution, and that single check catches the error every time. And the strip along the bottom separates two things people say interchangeably: BEING turbulent at step n climbs to a steady 0.25, while ARRIVING there for the first time at step n decays to nothing — they agree only at n = 1, then part company forever.
Look at what you just wrote. Two products, added, where the thing being summed over is the state you passed through in the middle. That is Chapter 10's law of total probability applied at time 1, and it is also exactly the row-times-column recipe from Chapter 6.
So (P²)ij is the two-step probability, and more generally each term of (Pⁿ)ij is one specific n-step path. Matrix multiplication was never notation here. It is a machine for summing over every intermediate state, which is why it shows up the moment you ask a multi-step question.
One trap before we move on, because it costs people weeks. (Pⁿ)ij is the probability of being at j after n steps. It is not the probability of first arriving there at step n. Occupancy and first passage are different questions wearing the same word — and first-step analysis answers the second one.
Watch the powers of P run and something else shows up. Row 0 goes (0.90, 0.10), then (0.84, 0.16), then (0.7824, 0.2176), and by the thirty-second power it has settled on (0.75, 0.25). Hold onto that pair of numbers, because it is the subject of everything that follows.
That pair has to wait, because not every chain is even asking the same kind of question. Some have states you can never leave. Some wander forever.
Six chains, two questions — and one mechanical test decides which question a chain will even answer.
① tap a card ② tap a bin — or drag a card into a bin
THE LEDGER · 0 of 6 sorted
ABSORBING — sort a chain into WHERE DO I END UP to fill this in.
RECURRENT — sort a chain into WHERE DO I SPEND MY TIME to fill this in.
TRANSIENT — one of the six earns this word. Find it.
Tap a card, then tap a bin
What you're looking at — one test, run six times: does any row carry a 1 on its own diagonal?
a 1 on the diagonal = an absorbing state, a door that never opens again → ask where do I end up
no such row → the token wanders forever → ask what share of its life it spends in each state
the wrong bin still computes something — it is just true and useless (or it demands 0 = 1)
the right bin returns a number you would actually pay for: 1/2, 6 flips, 22.6 years, 75%
Fig. 11. Six chains, and only two questions you are ever allowed to ask one. Pick a card — you see its story, not its numbers — and predict the bin before you drop it. The moment it lands the card flips face up and runs a test so mechanical it feels like a trick: is there a row with a 1 sitting on its own diagonal? That row says from this state, I go to this state, with probability 1. It is a door with no handle on the inside. If the chain has one — ruin at 0, riches at 2, the moment you finally see HH, the day the bond defaults — then the token's wandering ends, and the only sensible questions are which door and how long until it shuts: k/N = 1/2, six flips, 22.6 years. If the chain has no such row, nothing ever ends, so "where do I end up" has no answer at all — ask it anyway and the one-step template hands you E = 1 + E, which says 0 = 1, the algebra's way of shouting there is no such wait. Ask the mirror-image question of an absorbing chain and it answers politely and uselessly: drop gambler: two walls into the occupancy bin and you get a stationary distribution sitting entirely on the walls — perfectly true, perfectly worthless, and not even unique. The ledger fills in the three words as you earn them, including the one everybody mis-hears: a transient state like X is not one you cannot return to, it is one you will not — you may bounce back a dozen times, and still, with probability 1, there is a last visit, after which the share of your life spent there is exactly zero.
Read it straight off the matrix. A row with a 1 on the diagonal is a state whose every arrow points back at itself, so once entered it is never left. That is an absorbing state, and no new theory was needed to define it.
Put a gambling chain next to the regime chain and ask each the same thing. Run it a million steps, where is the token? For the gambling chain the answer is a place, since somebody went broke. For the regime chain the answer is a proportion, since it is still hopping. Those two answers need two different machines, and that split organises the rest of the chapter.
One caution on the vocabulary. A transient state is one you will eventually stop coming back to. A recurrent state is one you return to with probability 1. Readers routinely convert that into "you can come back", which is possibility rather than certainty, and the whole distinction is about certainty.
07★ Where the chain settles
A distribution over states is a row vector, and one step moves it by πn+1 = πn P. So ask the obvious question: is there a distribution the map leaves alone?
Setting πn+1 = πn gives π = πP, and what comes out is a linear system in the π's. That is the same object we already learned to solve. Its solution is the stationary distribution.
The name causes real damage, so let us kill the misreading immediately. "Stationary" reads as "nothing changes", and readers hear that the chain stops moving. It never stops — the token keeps hopping forever. What stops moving is the distribution.
A thousand tokens released on the calm/choppy/crisis chain — one token's path on the left, the histogram of all thousand on the right, running in lockstep.
1000 tokens released — watch
HOPS · TOKEN 10
DRIFT · ALL 10000.458
The bars stop moving. The token never does. Watch HOPS climb while DRIFT falls.
What you're looking at — a distribution that freezes over a token that doesn't
One tracked token. Its lane keeps changing for as long as you leave it running — HOPS has no last value. "Stationary" was never a claim about it.
calm, choppy, crisis — the three states. All 1000 tokens start in calm, so the bars must move at first.
π, the stationary distribution. The dashed gold line each bar settles onto, and DRIFT is how far the bars still have to travel to reach it.
Fig. 12. Press play and two things happen at once, and they are not the same thing. The tracked token zig-zags between calm, choppy and crisis and it never stops — HOPS climbs past a hundred, a thousand, forever. Meanwhile the histogram of all thousand walks out from (1, 0, 0) and stops, on (0.5420, 0.3550, 0.1030), and DRIFT collapses toward zero. That is what stationary means: not a chain that halts, but a distribution that stops moving while every individual keeps moving inside it. Now open π = πP and try to get those numbers from algebra alone. Three equations, three unknowns — press SOLVE and you get (0, 0, 0) and a red stamp, because adding the three rows makes every column cancel to 0 = 0: only two are independent. The equations pin the direction of π and are completely silent about its size, so every multiple of π solves them, zero included. Slot in the row that says the thing π = πP never says — π₁ + π₂ + π₃ = 1 — and the same solver returns the histogram's number exactly. The eigen view shows why a π exists at all: every row of P sums to 1, so P applied to the all-ones column gives back the all-ones column, which is the definition of eigenvalue 1 — true for every stochastic matrix, so a stationary direction is never in doubt. The second eigenvalue, 0.684164, is the one that costs you: each step multiplies the leftover distance by about 0.68, which is exactly how fast DRIFT fell. Finally switch to the flip-flop, P = [[0,1],[1,0]]. Its π = (0.5000, 0.5000) satisfies π = πP perfectly — and the histogram slams between all-tick and all-tock forever, because its second eigenvalue is −1, magnitude 1, so nothing ever decays. Irreducible ✓, aperiodic ✗. Solving the equations is not the same as converging to the answer.
Release a thousand tokens and watch the two panels disagree in the most useful way. A single token's path keeps jumping between the three regimes, restlessly, for as long as you let it run. The histogram of all thousand visibly freezes at (0.5420, 0.3550, 0.1030). That is the same split Chapter 13 drew between the data and the average, and it is worth carrying the picture across.
Since the token spends its life bouncing, there is a second reading of π that is often the useful one. It is the long-run fraction of time the chain spends in each state. For that three-regime chain, roughly 54% of days are calm and about 10% are crisis days, forever.
Now the piece of it that looks like magic and is not. Rows of P sum to 1, which says that P applied to the all-ones column vector returns the all-ones column vector. In Chapter 7's language, 1 is an eigenvalue of P, guaranteed, for every stochastic matrix. And π is the left eigenvector belonging to that same eigenvalue. Two honest lines, and the eigen-machinery finally pays off.
There is a dead end you will hit if you solve this by hand, and it is the most common practical failure in the whole topic. Solve πP = π on its own and you get all zeros. The system is singular by construction, since its equations are linearly dependent, so it pins the direction and not the scale. The missing line is Σπ = 1 — not an extra assumption, just the statement that π is a distribution.
Last, a belief worth breaking on purpose. Does a chain always settle down to its stationary distribution? Most people say yes, so try the chain that flips deterministically every step, where P = [[0,1],[1,0]]. Its stationary distribution is (0.5, 0.5), and it satisfies π = πP perfectly. Now start from one state. The histogram oscillates forever and never arrives.
So convergence needs two extra conditions, and you just watched why. The chain must be irreducible, meaning you can get from anywhere to anywhere. And it must be aperiodic, meaning it does not march in lockstep cycles. Most courses announce those two words at you. This one made them earn their place.
08The random walk and Gambler's Ruin
Change what the states mean and the same machinery answers a question about money. You have k dollars, your opponent has N − k, and each round a fair coin moves one dollar across the table. The game ends when somebody has everything.
Let pk be the probability you end up with all N starting from k. First-step analysis works exactly as before, except the quantity being carried is a probability rather than a time, so there is no +1. You get pk = ½pk−1 + ½pk+1.
The boundaries read straight off the definition, the same way E(target) = 0 did. From 0 you have already lost, so p0 = 0. From N you have already won, so pN = 1.
Here is where every reader stalls, and the stall is real rather than a failure of effort. The unknown is now indexed by a variable, so the ritual produces N − 1 equations and "just solve the system" is no longer a finite grind. The standard rescue treats it as a linear difference equation and guesses exponentials. Nobody has handed you that machinery.
You do not need any of it. Read the equation as a sentence rather than as a recurrence, and it says each value is the average of its two neighbours. Rearranged, pk+1 − pk = pk − pk−1, which says every gap is the same size.
Pull any dot off the line — every gap turns unequal, the row relaxes, and it lands back on the one straight line it was always going to be.
every gap equal · p = 0.5000
What you're looking at — one rule, and only one row of dots can obey it
Each dot is p(k): with $k in your pocket and $N on the table, the chance you reach $N before $0. One coin flip either way gives the one-step rule p(k) = ½p(k−1) + ½p(k+1) — every dot is the average of its two neighbours.
A gap is one bar of the ruler: the step from one dot to the next. "Average of neighbours" is exactly "left gap = right gap", so all bars must be the same height, namely 1/N.
Drag a dot away and the bars go unequal and red — the rule is broken. Let go and it relaxes back. No difference-equation machinery: N equal gaps climbing from 0 to 1 leaves exactly one shape.
That shape is the straight line p(k) = k/N. The drawer confirms it a second, independent way — and $1 against $99 in a perfectly fair game still ruins you 0.9900 of the time.
Fig. 13. Gambler's ruin without algebra: each dot is the average of its neighbours, so every gap is equal, so the row can only be the straight line p(k) = k/N — confirmed by the fair-game balance, and brutal at k = 1.
Equal gaps, pinned at 0 on the left and 1 on the right, is a straight line. So pk = k/N, and no characteristic equation was ever needed.
There is a second route to the same answer, and two independent routes agreeing is what makes a result feel like truth rather than a trick. The game is fair, so your expected wealth never moves. It starts at k. At the end it is either N or 0, so it equals p × N. Set them equal and p = k/N in one line. Honesty note: that argument quietly needs the game to end with probability 1, which the straight-line route already delivered.
Now cash it out on a number that should sting. You have $1 and your opponent has $99, and the coin is perfectly fair. Your chance of taking the whole hundred is 1/100, so you go broke with probability 0.99.
Read that against the phrase "fair game" and notice how badly the words mislead. Fair means the expected value of your wealth does not move. It says nothing about the two outcomes being equally likely — nothing at all. Confusing those two is how people lose money for a living.
Now ask how long the game lasts. Same states and the same first step, but the quantity is a time again, so the +1 comes back and gives Dk = 1 + ½Dk−1 + ½Dk+1.
Do not reuse the straight-line reading here, and this is a trap you would walk into honestly. With the +1 present, each value sits one unit below the average of its neighbours. That is a constant second difference, which is the discrete twin of constant curvature, and constant curvature means a parabola.
Guess before you look, because most people say a few hundred. The answer is Dk = k(N − k), so fifty dollars against fifty at a dollar a flip takes 2500 flips on average.
CodeRun — commit a number you cannot take back, then read 20,000 executed fair walks. And drag the +1 until the straight line bends.
How many flips? 50 vs 50.
▶ type a number, then press lock — the code runs
random.seed(20260813)
for _ in range(20_000):
d,w = walk(k=50,N=100)
print(mean(d), mean(w))
commit a guess, then it runs
What you're looking at — one first-step equation, run twice: once without the +1, once with it
no +1 — pk is exactly the average of its two neighbours, so every gap is equal: a dead straight line, k/N.
with the +1 — Dk sits one whole step above that average. Constant second difference −2 = constant curvature = a parabola, k(N−k), peaking at 2500.
20,000 executed walks: 2512.3 against 2500, and 904.4 against 900.
the number you committed before the code ran.
Chapter 13 could have told you 2500 before a line of algebra: a fair walk drifts about √n in n steps, so to cross the 50 dollars to the wall you need √n ≈ 50, i.e. n ≈ 2500. For 10 against 90 the same law gives the geometric mean, √(10×90) = 30, so n ≈ 30² = 900. Drag the +1 dial to zero and watch the parabola flatten into a straight line — that single constant is the whole difference between who wins and how long it takes.
Fig. 14. A genuine CodeRun, and a dial that is literally the +1. Commit a number of flips into the locked field before anything runs — it is drawn back at you in red — and the right panel then shows the real stdout of a script seeded 20260813 that simulates 20,000 fair walks on a $100 table: from k = 50 the mean duration is 2512.3 against the exact k(N−k) = 2500, with a win rate of 0.4951 against the exact 0.5000; from k = 10 it is 904.4 against 900, win rate 0.1003. check verifies rather than asserts — substituting k(N−k) back into Dk = 1 + ½Dk−1 + ½Dk+1 leaves a residual of exactly 0 at every interior k. Δ² prints the second-difference column, constant at −2, and draws the violet chord the curve always sits above — the discrete twin of curvature. √n shows that Chapter 13 predicted 2500 first: a fair walk drifts about √n in n steps, so crossing 50 dollars needs n ≈ 50². Drag the dial and the same equation with its +1 switched off collapses onto the blue straight line.
Chapter 13 could have told you 2500 before any algebra. A fair walk drifts about √n away from where it started, so to travel a distance of 50 you need n with √n ≈ 50. That is n ≈ 2500. The parabola was predictable from a law you already owned.
Last, tilt the coin. The exact answer for an unfair game involves the ratio r = (1−p)/p raised to the power of your bankroll. I will state it and verify it rather than derive it, since the general method is machinery we do not need here.
CodeRun — tilt the coin by two points and watch a linear-looking chance turn exponential: 0.1192 one way, 0.8808 the other.
predict, then step through the run
block 1 of 5 · the template
# ruin.py · seed 20260813
r = q/p
P = (1-r**k)/(1-r**N)
resid = P(k)-(p*P(k+1)+q*P(k-1))
# max|resid| = 1.1e-16# guessed the form, then CHECKED
What you're looking at — one honest step, and the cliff it hides
P(k) = your chance of turning k chips into all N before you hit 0 — the gold number, and the whole figure. Tap a plotted point to jump the run to the line that printed it.
The neighbours k−1 and k+1. P(k) = p·P(k+1) + q·P(k−1) is not circular: you spend one real step first, so the P on the right belongs to a different k. That spent step is what breaks the circle.
q = 1−p, the ruin side. The dashed grey line on replot k is a fair coin, where P is just k/N — a straight line. At p = 0.49 the real curve hugs the floor instead: k sits in an exponent, not a multiplier.
Checked, not trusted: 20,000 simulated walks give 0.1186 against the exact 0.1192, and the residual is 1.1e−16 at all 99 interior k. So: a house on 51–49 cannot lose, while a trader with a real edge still can — two points in a coin is 0.1192 against 0.8808.
Fig. 15. Gambler's ruin, executed: the exact chance swept across a two-point tilt in the coin, confirmed against 20,000 simulated walks, then replotted so the cliff between 0.49 and 0.51 can be seen and not just read.
The shape of that answer is what matters, and it is genuinely violent. Start at 50 against 50, where a coin at p = 0.49 gives you a winning chance of 0.1192 and a coin at p = 0.51 gives you 0.8808. A two-point swing in a coin carries you from near-hopeless to near-certain.
That is why ruin is exponential in the bankroll rather than linear. A small edge against you is not a small problem — it is the whole story. It is the entire reason a casino with a 51-49 edge cannot lose over a year, and the reason a trader with a genuine edge can still be wiped out before it pays. Chapter 15 and Chapter 30 are both downstream of this one fact.
09Where the template lies to you
The template is mechanical enough to be dangerous, and this section installs the one habit that keeps it honest. There is no new concept here. There is the difference between somebody who can run the algebra and somebody who can be trusted with the answer.
Go back one line, to the moment we substituted E(s′) as though it were a number. That step quietly assumed a number exists. Subtracting infinity from infinity is not algebra, and the equation will not complain if you do it.
So here is a process where it bites: a fair walk on the whole numbers, starting at 1, with 0 absorbing and no upper wall. Two questions about it. Do you eventually hit zero, and how long does it take on average?
Most people answer either "no" or "yes, and not that long". The truth is that you hit zero with probability 1, and the expected time to do it is infinite.
A real run: 20,000 unbounded fair walks from 1, absorbing at 0, no ceiling — absorption is certain, and the average never settles.
n=100 · med 3 · mean 1490.5
↓ and tap the gold bar in the strip
ONE STEP, THEN THE SAME AGAIN
E = 1 + ½·0 + ½·E₂
E₂ = E ← same kind of state
E = 1 + ½E
½E = 1
E = 2. a confident answer ✓
but the run says mean = 1490.5
What you're looking at — two columns from one run: what usually happens, and what it averages to
The typical run. From state 1 a fair step lands on 0 half the time, so 10,004 of the 20,000 walks ended on step one and the median — the middle run, half above and half below — never leaves 1–3 steps. Absorption is not in doubt: 19,998 of 20,000 hit 0 inside a 10,000,000-step cap, and the two stragglers would too.
The running mean of the same runs, over the first n of them: 1490.5 → 1885.4 → 3207.7 → 1882.4 → 2739.6 → 3337.9 → 3241.2. It is not converging, it is lurching — the ten longest walks out of 20,000 supply 71.8% of it. Tap the gold bar: dropping one run of 24 takes their average from 5850.1 to 12.2.
Where the algebra broke. Writing E₁ − E₁ = 1 assumes E₁ is a number. It isn't — that line is ∞ − ∞. Probability 1 says it happens; it says nothing about the wait. The violet ghost is Ch13's Cauchy running average: same failure, different costume. Safe rule: finite chain, 0 reachable from everywhere → the template holds.
Fig. 16. This is a real run, not a story about one: 20,000 fair ±1 walks starting at 1, with 0 absorbing and no upper wall — and it prints two columns side by side. The right one, the mean, is the number the one-step template claims to compute; the left one, the median, is what actually happens to you. 19,998 of the 20,000 walks reached 0 inside a ten-million-step cap, so absorption is not in question — on an unbounded fair walk it has probability 1. Yet the median hitting time is 1 step (a fair step from 1 lands on 0 half the time, and 10,004 of the runs ended right there), while the running mean reads 1490.5 at n=100, then 1885.4, 3207.7, 1882.4, 2739.6, 3337.9, 3241.2. Press RUN LONGER and watch the gold line: it does not tighten the way an average is supposed to, it lurches, because each new record-length walk yanks it upward and then thousands of one-step walks slowly drag it back down. The strip along the bottom is that mechanism at 24-run scale — twenty-three walks of 149 steps or fewer and one of 140,121. Tap the gold bar: deleting that single run takes the average of those 24 from 5850.1 to 12.2. Across the full 20,000, the ten longest walks supply 71.8% of the mean, so you are not measuring a property of the walk, you are measuring your luck at meeting monsters. Now the algebra. The shortcut panel does what every first-step derivation does — write E for the expected wait, take one step, and substitute the expectation of wherever you land — and out drops a crisp E = 2. The honest books panel does the same bookkeeping without lying about state 2 (reaching 0 from 2 means reaching 1 first, then 0: two independent copies, so E₂ = 2E₁), and it lands on E₁ − E₁ = 1 — the highlighted line, where a quantity that is infinite was cancelled against itself, and 0 = 1 fell out. The template did not fail; the hypothesis it smuggled in did. Substituting E(s′) presumes a finite number is sitting there waiting to be named, and here there isn't one. Toggle the Cauchy callback and Chapter 13's running average lays the same shape over the top: an average that looks like it is settling right up until the draw that proves it never was. The practical check is short and it keeps the whole rest of the chapter safe: on a finite chain where the absorbing state is reachable from every state, all the expected hitting times are finite and the one-step template is exact. Every gambler's-ruin duration and every backward-induction stopping value that follows sits inside that guarantee. Outside it — unbounded ladders, fair games against infinite pockets, "it always comes back eventually" drawdowns — probability 1 buys you the event and tells you nothing whatsoever about the wait, and confusing the two is how a mean-reversion trade gets mispriced.
Look at the two panels together, because separately either one would mislead you. The median hitting time is 1, so a typical run is over immediately. The running mean jumps from 109.6 to 3840.6 to 2176.6 and onward, and it refuses to settle no matter how much data you feed it.
That is the same picture Chapter 13 drew for the Cauchy average, and it is the same lesson. A probability can be perfectly well behaved while its expectation does not exist.
Take the practical check out of here. On a finite chain where absorption is reachable from every state, expected absorption time is finite and the template is safe. Remove a wall and you have to think for yourself again. Look back at Gambler's Ruin and notice that those two walls were doing real work all along.
Carry the sentence. It will price trades for you later. Certainty is not the same as soon. Anyone who believes that probability 1 implies a reasonable wait will misprice every "it will mean-revert eventually" position they ever look at.
10★★ Putting a choice inside the process
Everything so far described a process that runs itself. Now put a choice inside it, and watch which of your skills survive.
The game is simple. You roll a fair die, and you may either keep the number showing or reroll, with a fixed number of rolls remaining. You have a 4 and two rolls left. Keep it, or reroll? Commit to an answer before you read on.
The value of a state is no longer decided by the dynamics alone. It is V = max(take now, expected value of continuing), and that little max changes everything about how you compute.
Two things break at once, and no source tells you that anything broke. First, the equation stops being linear, so collecting terms and solving simultaneously is genuinely unavailable. Second, the direction reverses, because whether to keep a 4 depends on the value of continuing, which depends on the future.
The unlock is that the future is trivial at the end. With one roll left there is no decision at all, so the value is just the die's mean, 3.5. That known terminal value is your base case, and everything else is bookkeeping backwards from it.
Work the two-roll case in six visible cells. With one roll left worth 3.5, you reroll a 1, 2 or 3, and you keep a 4, 5 or 6. So the value is (3 × 3.5 + 4 + 5 + 6)/6 = 4.25. Now three rolls, where the continuation is worth 4.25, so only a 5 or a 6 survives: (4 × 4.25 + 5 + 6)/6 = 4.667.
Call the die before any maths is done — then build the value ladder backwards, one rung at a time, and watch your 4 change its mind.
your call — KEEP or REROLL?
What you're looking at — the threshold is not the die's average, it IS the value of the rolls you still have
gold rung = Vk, what "k more rolls" is worth. Keep a face only if it beats that.
green = KEEP
red = REROLL (give this face up)
violet = the value your cut would have produced — never above the gold rung.
Fig. 17. Put a max inside the equation and the whole Chapter 8 machine stops working — so the horizon has to rescue you. Start on the left: a die is dealt with a stated number of rolls left, and you must call KEEP or REROLLbefore anything is computed. Most people keep a 4 — it beats the die's average of 3.5, after all — and with one roll left that is exactly right. Now climb. Rung 1 is the last roll: there is no decision at all, both words go grey, and the panel simply writes V₁ = 3.500000. Rung 2 gives you a real choice, so drag the cut until each face is marked correctly; the value assembles in front of you as (3×3.5 + 4 + 5 + 6)/6 = 4.250000, and any other cut draws a violet line below the rung — never above it, because the optimal rule is optimal. Keep climbing and the ladder rises 3.500, 4.250, 4.667, 4.944, 5.130, crossing the dashed 4-line between rung 1 and rung 2 — and the tracked 4 chip flips from KEEP to REROLL as it does. That is the whole idea: the threshold is not the die's average, it is the continuation value — what still having k rolls is worth — so it climbs with the horizon and the same face changes its verdict. Finally, press TRY THE LINEAR SOLVER: the old move of collecting terms and solving simultaneously gets a stamped refusal, because to collect the V′ terms you must already know which faces lose to V′, and that depends on V′. A max is not linear. So you do not solve — you start at the last roll, where the answer needs no decision, and work backwards. That is backward induction, and it is the same shape that will price an American option in Part 4.
Watch your 4 flip colour as the horizon grows. Almost everyone fixes one threshold, usually "take anything above the average of 3.5", and applies it at every stage. The threshold is not fixed. The threshold is the continuation value, so it rises: 3.5, then 4.25, then 4.667.
Concretely, a 4 is a keep with one roll left and a reroll with three left. Same die face, opposite decision, and the only thing that changed is how much future you still own.
Name what you just used. The number attached to each state is the value function, and computing it from a known ending backwards is backward induction. Both names are load-bearing in Chapter 40, and you have now built them by hand.
Something sits underneath all of this. It is the reason the right to walk away is worth anything at all.
One die, two machines — average then choose, or choose then average. Drag the floor c: the gold gap between them is what the right to walk away is worth.
Predict: where is the right to walk away worth most?
▶ guess · then drag the floor
max(avg) 3.50 · avg(max) 4.25
guess, then drag the floor
What you're looking at — one die, two machines that differ only in the ORDER of the same two steps
average first — collapse the six faces to 3.5, then take the max against the floor. The spread is gone before you ever choose.
choose first — take max(face, c) on each face (low faces get lifted to the floor), then average. The gold band is the difference: the option value.
make it linear — same two endpoints, no bend. The gap collapses to exactly 0.00.
This is Jensen's inequality as a picture: because max is convex (it has an elbow), E[max(X, c)] ≥ max(E[X], c), and the chord between two outcomes always sits above the bend. The gap is widest when the floor sits at the die's own average — where the decision is genuinely live — and it is zero at both ends, where you already know what you'll do. That is why an option costs money: not because prices move, but because you choose after you see. The same elbow is an insurance payout and a call option's hockey stick.
Fig. 18. The same fair die feeds two machines that use the identical two steps in opposite order, and the whole chapter's payoff lives in the gap between them. Average first collapses the six faces to 3.5 and only then compares against the floor c you may take instead — one flat answer, max(E[X], c), drawn in blue. Choose first applies max(face, c) to each face separately, lifting only the faces that fall short (they turn gold), and averages afterwards — E[max(X, c)], drawn in gold. Drag c from 1 to 6 and the gold band never once goes negative: at c = 3.5 it is worth 0.75, its maximum, while at both ends it is exactly 0 — at c = 1 you never want the floor, at c = 6 you always do, and a decision you have already made is worth nothing. Switch to the bend to see why: the payoff curve is a flat stretch hinged to a rising one, and a chord drawn between any two outcomes across that hinge sits above the curve. That is Jensen's inequality with the name taken off. Press make it linear and the elbow straightens between the same two endpoints; the gold band shuts to 0.00 exactly, which proves the value came from the bend and from nothing else. The same elbow, sketched below the machines, is an insurance payout and a call option's hockey stick — and it is the shape that will price an early-exercise decision in Part 4.
Averaging and then taking the max is not the same as taking the max and then averaging. Formally E[max(X, c)] > max(E[X], c), and that is Chapter 11's Jensen inequality with the convex function max. The gap between the two sides is exactly what the option to reroll is worth.
That is the first honest sighting of option value in this course, and it arrives thirteen chapters before Black-Scholes. An option is not valuable because prices move. It is valuable because you get to choose after you see the outcome — and max is convex.
11A fair coin out of a crooked one
One last problem. It uses every piece of the chapter at once, and the answer is genuinely surprising. Somebody hands you a biased coin and will not tell you the bias. Can you generate a perfectly fair bit from it?
Most people say no, and the instinct behind that is a conservation feeling: you cannot manufacture fairness out of unfairness. The instinct is wrong, and the procedure that beats it is three lines long.
Flip the coin twice. If you get HT, call it heads, and if you get TH, call it tails. If instead you get HH or TT, throw the pair away and start again.
The sharp objection arrives immediately, and it deserves a straight answer. If heads are more likely then HH is more likely than TT, so surely the bias leaks through?
Five beats — von Neumann's trick: a perfectly fair bit out of a coin whose bias you are never told.
can a bent coin be made fair?
beat 1 of 5 · the question
the coin's bias p0.70
commit above, then press next ▸
What you're looking at — two cells that carry the identical expression, at every bias
HT — heads then tails. Its chance is p×(1−p). We agree to call it HEADS.
TH — tails then heads, chance (1−p)×p. The same two numbers multiplied, so the same value — one rectangle, quarter-turned. We call it TAILS.
HH and TT — discarded, and you flip again. This is the objection everyone raises, and the answer is: discarding is conditioning. Divide p(1−p) by 2p(1−p) and the p cancels — we restricted the sample space to the part that was symmetric all along, rather than removing bias from anything.
The price. One step, then the same expectation again: E = 2 + (1−2p(1−p))E, so E = 1/(p(1−p)) flips per fair bit — 4 at p=0.5, 11.1 at p=0.9, 101 at p=0.99. Same answer the other way: each pair succeeds with probability 2p(1−p), and a Geometric wait averages 1/(2p(1−p)) pairs — times 2 flips a pair.
Fig. 19. Von Neumann's trick as a five-beat build: the two middle cells of the pair table hold the identical expression p(1−p) at every bias, so keeping only HT and TH conditions the coin down to a symmetric half rather than scrubbing the bias out of it — and the state machine's self-loop is exactly what you pay for it, 1/(p(1−p)) flips per fair bit.
Look at the four cells. HH costs p² and TT costs (1−p)², while the two middle cells are p(1−p) and (1−p)p. Those two are the same expression, whatever p is, and that is the entire proof. It takes one glance rather than any algebra.
Now answer the objection properly. Discarding HH and TT is not throwing bias away, it is conditioning down to the part of the sample space that was symmetric all along. Chapter 10's shrink-the-world move and Chapter 13's symmetry argument are doing one job together here.
Notice the shape of the machine, too. "Start again" is a self-loop, an arrow from the start state back to itself, so this is the same picture we have been drawing all chapter. It is also why the procedure is not free.
Price it with the template. Each attempt spends two flips, and it succeeds with probability 2p(1−p), so E = 2 + (1 − 2p(1−p))·E. Solving gives E = 1/(p(1−p)) flips per fair bit. The same answer drops out of Chapter 12's Geometric mean with success probability 2p(1−p), which is a nice cross-check.
Read the cost at the extremes. It teaches something well beyond the trick. An honest coin costs 4 flips per bit, a coin at p = 0.9 costs 11.1, and a coin at p = 0.99 costs 101. Randomness is a resource with a price — and a nearly-certain coin has almost none of it to give.
12The template, and where it goes
Everything on this page was one procedure wearing five costumes. Here it is in five lines, and each line points at the section that built it.
What must I remember? That question finds the state. Where can I go from here, and with what chance? Those are the arrows, and the labelling test is what checks them. What is one step worth, plus whatever I face next? That is one equation per state, and the boundary line is whatever is already known at the end. Then solve, as a linear system if the process runs itself, and backwards if you get to choose.
Five lines answered every question on this page. Now take them cold to three finance problems you have never seen — then walk out through the four doors.
five lines. one recognition trigger.
Every worked answer on this page is these five lines in a different costume.
One name in each tray is a whole history, not a summary. Your call.
tap a numbered line, or press next line
What you're looking at — one template, worn four ways, and the question that spots it
The states — the small summary of the past that decides the future. Line 1 is the only creative step; a rating, an inventory and a regime all pass the test, and a history (the last 30 returns) does not.
The one step, then the same expectation again. Lines 2–3 are the whole move: you spend a real step first, so the E on the right belongs to a later state — that spent step is the constant that breaks the circle.
Unlabelled arrows glow red on the cold board. The board checks two things only — states named, every outgoing arrow labelled — and then stops. It never tells you the answer, because setting it up is the skill.
Four doors out, each keeping four lines and moving one: hide a state → HMM/Kalman (Ch 33); hand line 5 to a machine → dynamic programming (Ch 40); keep “today = average of tomorrow” → martingales (Ch 25, 27); take ruin seriously → Kelly (Ch 15, 30).
Fig. 20. The map so far, turned into a working checklist. Step the five lines and each lights the figure that built it; then take the template cold to three problems the chapter never showed you — a bond migrating to default, an inventory drifting to a forced unwind, a market flipping between calm and turbulent — and the board stops the moment you have named the states and labelled the arrows, because that is the whole transferable skill.
The recognition trigger is the part worth drilling. It is not the word "coin" and it is not the word "walk". It is one question, and this is the one to memorise. Is there a small summary of the past that decides the future?
Try it cold on three things you have never modelled: a bond migrating between credit ratings with default absorbing, a market maker whose inventory drifts up and down until it must be unwound, and a market that switches between calm and turbulent. Name the states and draw the arrows for each of them, then stop there. You will feel the template fit before you have any of the finance.
Now where the threads go. When the state is hidden and must be inferred from noisy observations, this chapter becomes the hidden Markov model and the Kalman filter of Chapter 33. When the value function is computed by machine over a large state space, backward induction becomes the dynamic programming of Chapter 40.
The fair-game line from Gambler's Ruin has the longest reach of all. Expected wealth is conserved, so today's value is the average of tomorrow's. That sentence is the martingale, and it becomes risk-neutral pricing in Chapters 25 and 27. The ruin arithmetic is why bet sizing exists, which is Chapter 15's Kelly criterion and Chapter 30's bankroll work.
Carry three things out of here. First, the state is something you find by crossing out history, and you validate it by trying to label every outgoing arrow. Second, first-step analysis is not circular, because the remaining problem is a fresh copy of the same problem, and that is true only because of Markov plus homogeneity.
Third, and this is the one that costs money when it is missed. The template will hand you a confident finite number for a quantity that is infinite, and it will do it without a warning. Certainty is not the same as soon.
Chapter 15 pushes on exactly that crack. When expected value returns an absurdity, an infinite price for a coin game or an argument for swapping envelopes forever, the fix is never better arithmetic. It is a better model, and that is where utility and the Kelly criterion come from.