Coins: counts, complements and waiting for a pattern
Flips have no memory, but sequences have structure. The number of heads is binomial; the wait for HT is shorter than the wait for HH; and a run of heads tells you nothing about the next flip, unless you doubt the coin.
- Compute the probability of exactly k heads in n flips
- Use the complement for 'at least one head'
- Explain why HT arrives before HH on a fair coin, and compute both waits
- Recover a coin's bias from the chance of an all-tails run
The intuition
Five flips of a fair coin, exactly two heads: choose which two of the five flips are the heads, C(5, 2) = 10 ways, each with probability (1/2)⁵. That is 10 ÷ 32. At least one head is easier by the complement: 1 − (1/2)⁵. The binomial is counting from the last chapter with a probability attached to each sequence.
Waiting times are different. How long until you first see HT, a head followed by a tail? Wait for a head, on average 1/p flips, then wait for a tail, 1/(1 − p) more. On a fair coin that is four flips. HH takes six, because failures are not equal: going for HT, a second head is not a setback, you still hold your head; going for HH, a tail throws everything away. That asymmetry is the point of the question.
P(exactly k heads in n) = C(n, k) pᵏ (1 − p)ⁿ⁻ᵏ. P(at least one head) = 1 − (1 − p)ⁿ. E[flips until HT] = 1/p + 1/(1 − p); E[flips until HH] = 1/p + 1/p². From P(no heads in n) = x, the bias is p = 1 − x^(1/n). The next flip after a run of heads is still p.
Why it works
- The conventions here: independent flips of one coin with P(heads) = p. Counts of heads in n flips are binomial. Waiting times are the standard first-step results.
- Binomial = choose the heads, then multiply. Any particular sequence with k heads has probability pᵏ(1 − p)ⁿ⁻ᵏ, and there are C(n, k) such sequences. The expected number of heads is np, and k near np is the most likely count.
- HT adds two waits. First a head (geometric, mean 1/p), then a tail (mean 1/(1 − p)). Nothing is lost along the way.
- HH needs a first-step equation. After the first head, the next flip is either a head (done) or a tail (start again from nothing): E = 1/p + 1 + (1 − p)E, which gives E = 1/p + 1/p². On a fair coin, 6 against 4.
- The order flips at a very biased coin. When heads are likely enough (above about 61.8%), the tail that HT needs becomes the slow part and HH arrives first.
- Runs carry no memory, unless the coin is in doubt. After ten heads the next flip is still p. But if you are not sure the coin is fair, the run is evidence about p, and Bayes (chapter 6) says to shift your estimate toward heads.
| P(exactly 2 heads): C(5, 2) × (1/2)⁵ = 10 ÷ 32 | 31.25% |
| P(at least one head): 1 − (1/2)⁵ | 96.875% |
| E[flips until HT]: 1 ÷ 0.5 + 1 ÷ 0.5 | 4 flips |
| E[flips until HH]: 1 ÷ 0.5 + 1 ÷ 0.5² | 6 flips |
| A coin with P(no heads in 5) = 1.024%: (0.01024)^(1/5) = 0.4 | P(heads) = 60% |
| P(next flip is heads after 5 heads in a row) | still 50% |
Double the flips to 10 and P(at least one head) becomes 1 − (1/2)¹⁰ = 99.9%: the failure probability squares, it does not halve.
The formulas
Choose which flips are heads, then the probability of one such sequence.
The complement of all tails.
Wait for a head, then wait for a tail.
A tail after the first head sends you back to the start.
The bias from an all-tails probability.
Worked example
Count the sequences with that many heads, then multiply by the probability of one of them. The follow-up compares k with the expected number of heads.
See it move
Same coin. Change its bias, the number of flips, and the number of heads asked about. The heads slider stops one below the flips.
- Raise P(heads). At least one head and at least k heads become more likely, the wait for HH shortens; watch the wait for HT, which is shortest at a fair coin.
- Add flips. At least one head and at least k heads become more likely; the waiting times do not move, because they do not depend on how many flips you plan.
- Ask about more heads. At least k heads becomes less likely; watch exactly k, which peaks near the expected number of heads.
Run it backwards
The chance of seeing no heads at all in a run of flips is known. What is the coin's bias?
(1 − p)ⁿ is the all-tails probability. Take the n-th root to get the per-flip tail probability, and subtract from one.
The follow-up is about the real world: you observe a run, not its probability, so you estimate p with a likelihood or an interval rather than solving for it.
Traps
Say it in the interview
“Fair coin. Which comes first on average, HH or HT, and by how much?”
Check yourself
5 fresh questions, with new numbers. Answer each one correctly to finish the chapter. Get one wrong and you will see the full working, then you can try it again with new numbers.
Answers within 1% are marked right. Type the number; $, %, x and M are fine. First tries count toward Learned: the topic is Learned once every chapter is done and 75% of first tries were right.
- Binomial: C(n, k) sequences, each with probability pᵏ(1 − p)ⁿ⁻ᵏ.
- 'At least one' is 1 − (1 − p)ⁿ; doubling the flips squares the failure probability.
- E[HT] = 1/p + 1/(1 − p); E[HH] = 1/p + 1/p². Failed attempts at HH keep nothing.
- A run of heads does not change the next flip. It can change your estimate of the coin.