Coin flips, for quant interviews

The coin has no memory

The starting question is almost always a trap disguised as a warm-up: a fair coin has come up heads five times in a row — what's the probability the next flip is tails? The answer is $1/2$, and the interviewer is watching to see if you flinch. Independent flips carry no memory; the coin cannot ‘owe’ you a tail. What people confuse is two different quantities. Calling six heads in advance is genuinely unlikely — $(1/2)^6 = 1/64 \approx 1.6\%$ — but conditioned on the five heads that already landed, the sixth flip is an ordinary $1/2$. The rare event already happened; it doesn't get ‘paid back.’ Say this crisply and you've cleared the filter the question exists to apply.

Expected flips: the waiting-time question

The signature coin question is a waiting time: how many fair flips, on average, until you first see the pattern HH? And until HT? The surprise the interviewer is hunting for is that these differ — $\E[\text{HH}] = 6$ but $\E[\text{HT}] = 4$ — even though each two-flip pattern is equally likely in isolation. The reason is overlap, and the clean way to show it is a two-state Markov argument.

For HT, let $a$ be the expected flips from scratch and $b$ the expected flips once you're holding a head. From scratch, one flip either gives a head (go to state $b$) or a tail (stay): $a = 1 + \tfrac12 b + \tfrac12 a$. Once you hold a head, a tail finishes and a head just keeps you holding a head: $b = 1 + \tfrac12\cdot 0 + \tfrac12 b$. The second equation gives $b = 2$; substituting, $\tfrac12 a = 1 + \tfrac12(2) = 2$, so $a = 4$.

For HH the algebra is identical except for one arrow. Once you hold a head, a tail doesn't keep you waiting — it throws you back to the start: $b = 1 + \tfrac12\cdot 0 + \tfrac12 a$, while $a = 1 + \tfrac12 b + \tfrac12 a$. From the second, $a = 2 + b$; substituting into $b = 1 + \tfrac12 a$ gives $b = 1 + \tfrac12(2+b) = 2 + \tfrac12 b$, so $b = 4$ and $a = 6$. That single backward arrow — a tail after a head deletes your progress — is the entire two-flip gap.

The formula behind the number

You don't have to rebuild the Markov chain every time. Conway's leading-number identity gives the expected waiting time for any pattern under a fair coin as a sum over its self-overlaps: for each length $i$ where the pattern's first $i$ symbols equal its last $i$ symbols, add $2^i$.

HH overlaps itself at length 2 (the whole word) and length 1 (its trailing H is also a leading H), so it collects both terms. HT overlaps only at length 2, because a trailing T is not a leading H. Push to three symbols and the same rule predicts $\E[\text{HHH}] = 2^3 + 2^2 + 2^1 = 14$ while $\E[\text{HTH}] = 2^3 + 2^1 = 10$ — more self-similar patterns are always slower to arrive. And it generalizes off the fair coin: with $\Prob(H)=p$ and $q = 1-p$, the two-state derivation yields $\E[\text{HH}] = (1+p)/p^2$ and $\E[\text{HT}] = 1/p + 1/q$, which collapse to $6$ and $4$ at $p = \tfrac12$.

Streaks and runs

Waiting times explain a fact interviewers like to test directly: in a short block of flips, some patterns are simply likelier to appear than others. Enumerate all $2^3 = 8$ equally likely outcomes of three fair flips. The pattern HH shows up in exactly three of them — HHH, HHT, THH — so $\Prob(\text{HH appears}) = 3/8$. The pattern HT shows up in four — HHT, HTH, HTT, THT — so $\Prob(\text{HT appears}) = 4/8 = 1/2$. Same asymmetry, same cause: HT is the easier pattern to stumble into, which is why its waiting time is shorter. A related run question — the probability that $n$ flips contain no two consecutive heads — is counted by Fibonacci numbers, $F(n{+}2)/2^n$; for $n=4$ that's $F(6)/16 = 8/16 = 1/2$.

Biased coins, and faking a fair one

Change $\Prob(H)$ to $p$ and two things happen. First, the expected flips to a single head is $1/p$ — with variance $(1-p)/p^2$ (for the fair coin, mean $2$ and variance $2$). Second, and more fun to be asked: given only a biased coin of unknown $p$, produce a perfectly fair bit. Von Neumann's trick: flip twice. Map HT to ‘heads’ and TH to ‘tails’ — each occurs with probability $p(1-p)$, so they're exactly equal whatever $p$ is — and discard HH or TT, reflipping. A pair is usable with probability $2p(1-p)$, so you burn $1/\big(p(1-p)\big)$ flips per fair bit on average: $4$ flips when $p=\tfrac12$, about $4.76$ when $p=0.7$. The bias cancels because you only ever compare two mutually exclusive, equal-probability orderings.

Variants that change the answer

The waiting-time result is fragile in instructive ways, and naming the fragility is what separates a strong candidate:

• First to appear (Penney's game). Change the question from ‘how long to HH’ to ‘which of HH vs HT appears first,’ and most candidates expect the same asymmetry — but this race is a genuine 50/50 tie. Both patterns begin with H, so nothing is decided until the first head lands; the very next flip then resolves it — another head completes HH, a tail completes HT, each with probability $\tfrac12$. The real Penney asymmetry needs patterns that share less of a prefix: for example TH beats HH with probability $3/4$ (HH can only win the race if the first two flips are both heads, probability $1/4$). Extend to three-symbol patterns and the game becomes genuinely non-transitive — for any pattern your opponent picks, you can pick one that beats it. (Note the contrast with the streaks section: HT is more likely than HH to appear within a fixed short block, but in the unbounded ‘who's first’ race against HH it only ties.)
• Order matters, not just counts. Two flips giving ‘one head and one tail’ has probability $\tfrac12$ (HT or TH), not $\tfrac13$ — the outcomes HT and TH are distinct. Treating unordered counts as equally likely is the fastest way to a wrong number.
• Biased coin. Every clean answer above assumed $p=\tfrac12$. If the coin is biased, $\E[\text{HH}]=(1+p)/p^2$, the streak probabilities shift, and ‘50/50’ reasoning is simply wrong. Always confirm the coin is fair before you use symmetry.

Common mistakes

• The gambler’s fallacy. Believing a tail is “due” after a run of heads. Independence means the conditional probability is unchanged; only the ex ante run was rare.
• Assuming all patterns wait the same. Answering that HH and HT both take 4 (or both 6) flips. The self-overlap of HH costs two extra flips — you must track whether a failure destroys progress.
• Confusing “appears in a block” with “waiting time.” These are different questions with different answers; read which one is being asked.
• Dropping the discard branch in Von Neumann. Forgetting that HH/TT are thrown away is how candidates “prove” the extractor is biased.