Derivatives Foundation puzzles, solved step by step

Puzzles
100
Traced to a firm
66
Topics
12
Hard
29
Topic
All topicsMental maths and estimation9Random walks and Markov chains7Conditional probability and Bayes7Volatility and correlation7Option pricing intuition7Expected value and optimal stopping10Market making11Option payoffs and no-arbitrage10Probability and counting11Distributions and statistics8Games and logic8Betting and sizing5
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 074What is the expected number of fair coin flips needed to see two heads in a row? And how many to see a head followed by a tail?Random walks and Markov chainsCoreSquarepoint CapitalLondon · 2025

    Try it first

    HH and HT each have probability 1/4 on any two flips. Do they take the same expected time to appear?

    Show the worked solution

    6 flips for HH and 4 flips for HT. Track one state: whether the last flip was a head. For HH, a tail after a head sends you back to the start, so E(start) = 1 + E(one H)/2 + E(start)/2 and E(one H) = 1 + E(start)/2, giving 6. For HT, a head after a head leaves you still holding a head, so E(one H) = 1 + E(one H)/2 = 2 and E(start) = 2 + 2 = 4.

    Why do two patterns with the same probability take different times?

    Two queues at a counter: in one, a mistake sends you to the back; in the other, a mistake keeps your place. Both queues move at the same speed, but one is a much longer wait. Waiting for a pattern is a race with restarts, and what matters is how much progress a failure destroys: a tail after a head destroys everything for HH, while a head after a head destroys nothing for HT. That asymmetry, not the probability of the pattern, sets the expected time. It is also why HT and TH take 4 while HH and TT take 6.

    A failed HH sends you back to the start; a failed HT does notWaiting for H then HStartnothing useful yetOne Hfirst head seenDoneHTT: stayT: back to the startE(start) = 1 + 1/2 E(one H) + 1/2 E(start)E(one H) = 1 + 1/2 x 0 + 1/2 E(start)E(one H) = 4E(start) = 6 flipsWaiting for H then TStartnothing useful yetOne Hfirst head seenDoneHHT: stayH: stay, still one headE(start) = 1 + 1/2 E(one H) + 1/2 E(start)E(one H) = 1 + 1/2 x 0 + 1/2 E(one H)E(one H) = 2E(start) = 4 flips
    Waiting for HH takes 6 flips because a tail after a head sends you back to the start, while waiting for HT takes 4 because a second head after a head still counts as a first head, so no progress is lost.

    How do you set up and solve the equations in the room?

    Two states, two equations, each saying one flip plus the average of what remains. For HH: from the start, a head takes you to one H and a tail keeps you at the start, so E0 = 1 + E1/2 + E0/2; from one H, a head finishes and a tail returns you to the start, so E1 = 1 + E0/2; substitute to get E1 = 4 and E0 = 6. For HT the second equation changes to E1 = 1 + E1/2, since a head keeps you at one H, giving E1 = 2, and the first equation gives E0 = 2 + E1 = 4. The first equation is the same in both problems; only the failure branch differs.

    The relationship
    HH: E0=1+12E1+12E0, E1=1+12E0⇒E0=6HT: E1=1+12E1⇒E1=2, E0=4\text{HH: } E_0 = 1 + \tfrac{1}{2}E_1 + \tfrac{1}{2}E_0,\ E_1 = 1 + \tfrac{1}{2}E_0 \Rightarrow E_0 = 6 \qquad \text{HT: } E_1 = 1 + \tfrac{1}{2}E_1 \Rightarrow E_1 = 2,\ E_0 = 4
    E_0expected flips remaining from the start, no useful progress
    E_1expected flips remaining once the last flip was a head
    1/2the chance of a head or a tail on each flip
    What it says in wordsThe pattern whose failures throw away progress takes six flips on average, and the pattern whose failures keep progress takes four.

    What is the quick check, and where does this matter beyond coins?

    There is a general rule: the expected time to a pattern is the sum of 2 to the k over every length k at which the pattern overlaps itself. HH overlaps itself at lengths 1 and 2, so 2 + 4 = 6; HT overlaps only at its full length 2, so 4. The same arithmetic prices a bet on which of two patterns appears first, and it shows up on a desk whenever a signal needs a run of confirmations: a rule that resets on any contradicting tick waits far longer than one that keeps partial progress. The limitation is the fair coin; with a biased coin the overlap rule still holds but the powers of two become products of the relevant probabilities.

    Where candidates lose it

    The common answer is that HH and HT take the same time because each has probability 1/4. The interviewer is testing whether you see that waiting time depends on what a failure costs, not on the pattern's probability.

    The second loss is setting up the HT chain with a return to the start after a second head. A head after a head is still one head; the state does not change.

    What the interviewer asks next

    • What is the expected number of flips to see three heads in a row?
    • Which appears first on average, HHT or HTH, and why are their waiting times different?
    • The coin lands heads with probability 0.6. Expected time to HH?
    • You flip until you see HT and I flip until I see HH. What is the chance you finish first?

    Asked at Squarepoint Capital, Quantitative Research, London, 2025 (Wall Street Oasis): a few siimple questions on statistical problems e.g. # of throws expected to get 2 heads in a row