Markov / Recursion · Interview Question
Flip a fair coin until you see two Heads in a row (HH). What is the expected number of flips?
How to answer
6. Let S = start state, H = 'one Head so far'. First-step equations: E_S = 1 + (1/2)E_H + (1/2)E_S and E_H = 1 + (1/2)(0) + (1/2)E_S. Solving: E_S = 2 + E_H and E_H = 1 + (1/2)E_S give E_H = 4, E_S = 6. It exceeds the naive 4 because a Tail after an H resets all progress.
Key idea: Two-state Markov chain; condition on the next flip from each state.
More: Quant interview prep · Quant salary
Related Markov / Recursion questions
- A coin is flipped until the first tail; you win $2^n where n = heads before that tail. Fair price?
- A disease has 1% prevalence. A test is 99% sensitive and 99% specific. You test positive — probability you have it?
- A fair die pays you its face value in dollars. What is the fair price to play, and what is the variance of the payout?
- A unit stick is broken at two independent uniform points into three pieces. Probability they form a triangle?