LessonThis is a lesson restated in new words. Any figure in it is an example from the source, not this desk's record.
The number of tosses until the first run of three heads is a random waiting time, not a fixed count. First-step analysis, which conditions on the next flip and reuses the same waiting problem after a reset, produces the mean exactly. For heads probability p it is 1/p + 1/p² + 1/p³. A fair coin therefore waits 14 tosses on average. In the lecture, 10,000 simulated series averaged about 13.87.
Why it matters
A fixed-horizon probability can be read from a matrix power. The waiting time has no fixed horizon. A brute-force tree never closes, because a long string of tails is always possible. Simulation still estimates the mean: flip until HHH appears, record the length, and average many trials. An interview that asks for the expectation wants the expression that average is approaching. The same recurrence covers a run of any length.
The idea in plain words
Let H_k be the tosses needed to see k heads in a row, starting from a blank slate. The target is the expectation of H_3.
From a blank slate, one toss is spent immediately. With probability p it is heads and a run of length one is finished, so that branch costs 1. With probability 1-p it is tails and the problem restarts, so that branch costs 1 plus a fresh copy of H_1. The law of total expectation, a mean written as a probability-weighted average of conditional means, says
E[H_1] = p·1 + (1-p)·(1 + E[H_1]).
Solving yields E[H_1] = 1/p. That is also the mean of a geometric count of trials until the first success. The first-step argument recovered it without needing the name.
To reach two heads, start as if one head is already in hand. The next flip either completes the pair at a cost of one toss, or tails and returns you to the full H_2 problem after that wasted toss. Conditioning gives E[H_2] = 1/p + E[H_1]/p, which is 1/p + 1/p².
One more step starts from two heads already banked. Success costs one toss. Failure costs one toss plus a new attempt at H_3. Then E[H_3] = 1/p + E[H_2]/p, which expands to 1/p + 1/p² + 1/p³.
The pattern is the useful part. Moving from a streak of k to a streak of k+1 satisfies E[H_{k+1}] = (1 + E[H_k])/p. Setting k = 1 reproduces the two-head formula, a small check that the recurrence was copied correctly.
How to use it
Pick p and add the three powers. For a fair coin, p = 1/2, so the terms are 2, 4, and 8, and the sum is 14. A head-heavy coin finishes sooner because those powers shrink as p grows.
The Monte Carlo check compares with the formula. It does not replace it. Keep flipping independent trials until three heads sit at the end of the list, store the length, and repeat. Ten thousand repetitions at p = 1/2 averaged near 13.87. That figure is a count of tosses, not a percent.
Every tails, at any depth, would grow a new copy of the whole tree. First-step analysis does not draw those copies. It names their average length and solves for it.
What usually goes wrong
People plug the geometric mean in for the triple. The value 1/p is only the wait for a single head. It ignores restarts that wipe out a streak of one or two. The extra powers of p are those ruined partial runs.
The failure branch must add both the toss just spent and a full new expectation. Drop the added one and the equation stops counting every flip. A short simulation is also a weak substitute for the formula. The waiting time has a long right tail, so a few dozen series bounce around 14. The lecture's 10,000 trials were a check, not a new answer.
Questions people ask
What if the target run is longer than three?
Unroll the recurrence. Each added head in the target multiplies the previous mean by 1/p and then adds 1/p. Three heads is the case written out above.
Does 14 include the successful tosses?
Yes. H_3 counts every toss from the start through the head that completes the run. The three finishing heads sit inside the 14.
Why is the mean finite if the run is certain to appear?
On an infinite sequence a coin with p between zero and one hits HHH with probability one, so a fixed-horizon question becomes trivial at infinity. The waiting time is still random, and its mean is the finite sum above.