LessonThis is a lesson restated in new words. Any figure in it is an example from the source, not this desk's record.
Counting heads one toss at a time gets messy once the question is about a run, not a single flip. A Markov chain keeps only the length of the current head streak. From that chain, one matrix answers three interview questions: whether a run of three heads appears anywhere in n tosses, whether the series ends on such a run, and whether the first such run finishes on toss n.
Why it matters
Listing every string that contains HHH explodes as n grows, and it is easy to answer the wrong event. Standing on a streak of three at the final toss is not the same as having seen that streak at least once. Those two events, plus a first success that lands exactly at the end, are the three questions in the lecture. The same bookkeeping appears whenever a process restarts after a failure. You do not need the whole history. You need the progress so far.
The idea in plain words
A Markov chain is a sequence of labels in which the next label depends only on the label you hold now. The labels here are H0, H1, H2, and H3: zero, one, two, or three heads in a row. A head moves you one step forward. A tail sends you back to H0, because the streak is broken.
From H0, tails stays put and heads moves to H1. From H1 or H2 you cannot linger. Heads advances the streak. Tails resets it. From H3 the diagram has a choice. If the chain may leave H3, another head can leave the latest three tosses as heads, and a tail starts over. That version tracks where you stand after exactly n tosses.
If the question is whether the run has occurred at any time up to n, H3 has to be absorbing. Once you arrive, later tosses leave you there. The coin can keep flipping, but the label no longer forgets that the run already happened. For a finite n, the chance of being in that trap is the chance the run appeared somewhere in the series.
The diagram becomes a transition matrix. Rows and columns are the four states. Each entry is the chance of moving from the row state to the column state, so each row sums to one and every entry lies between zero and one. The Chapman-Kolmogorov relation says the chance of traveling from state i to state j in n steps is the matching entry of that matrix raised to the nth power.
How to use it
Write two matrices. In the first, H3 can fall back to H0 on tails. The H0-to-H3 entry of the nth power is the chance that toss n itself completes a streak of three, whether or not an earlier streak occurred. In the second matrix, put a one on the H3 diagonal and zeros elsewhere. The same entry is now the chance the streak has been seen at least once by toss n.
The third question is a difference. Let F(n) be the absorbing-matrix probability of having seen the run by toss n. The chance that the first completion happens at toss n is F(n) minus F(n-1). A series can end on HHH after an earlier HHH, and the difference throws those series out.
The lecture checks the formulas with n fixed at 10. Simulation put the "seen somewhere" frequency at 0.50 against a matrix value of 0.507. Ending on the run came in near 12 percent against 12.5 percent. First arrival on the final toss came in at 0.041 against about 4.3 percent. Seeing the run anywhere is the largest chance. Merely ending on it is smaller. Having the first success land exactly at the end is smallest.
What usually goes wrong
The common slip is to read the nth power of the non-absorbing matrix as "the run occurred somewhere." That entry only looks at the state on toss n. A path that hits H3 early and then tails out is a success for the "anywhere" question and a failure for the "end on it" question.
A second slip is to treat the first-arrival probability as F(n) itself. F(n) stacks every success from toss 3 through n. Only the step from F(n-1) to F(n) isolates paths whose first success is the last toss. Starting the chain in H1, as if a head had already been imagined, shifts every answer.
Questions people ask
Does the coin's bias belong in the matrix?
Yes. If heads has probability p, every forward arrow is p and every reset is 1-p. Change p and you rebuild the matrix. The three questions keep the same shapes.
Why is the answer zero for n below three?
One or two tosses cannot contain a streak of three, so both matrices send no probability into H3. The interesting entries begin at the third power.
Can this diagram give the waiting time?
The waiting time is an expectation, not one entry of a finite power. The follow-up is a first-step calculation on these same states, which produces a closed form rather than a single probability.