Expected tosses for a run of n consecutive heads

This question asks about the expected waiting time in a simple coin-flipping experiment until a specific streak appears: a run of a given length of consecutive heads. The candidate must formalize the situation as a stochastic process with a small number of well-chosen states, each representing how close the current sequence is to achieving the desired run. It is a standard type of run-length problem that shows up in probability interviews and in roles where intuition for random sequences and stopping times is important, such as quantitative research and trading.

Solving it leans on Markov chain reasoning, first-step analysis, and setting up linear relations between expected times to absorption from different states. The interviewer is looking for an organized state definition, correct conditioning on the next coin toss, and comfort turning probabilistic descriptions into algebraic equations. They also watch whether the candidate spots the recursive structure and deals correctly with the "reset" behavior when the streak is broken. Clarity of notation, the ability to simplify the resulting system, and a qualitative understanding of how the expectation scales with the run length all matter.

What it tests

This problem class is governed by the principle of Markovian state transitions and first-step analysis, where the process can be described by a set of states (such as the current run length of consecutive heads) and transitions between them based only on the most recent outcome. The expected time to reach a target state (like n consecutive heads) can be recursively related to the expected times for simpler states, because the process 'resets' in a memoryless way after certain outcomes (like a tails). The recurrence arises because, from any non-terminal state, the next step either advances you closer to the goal or resets your progress, each with fixed probabilities. The exponential growth in expected waiting time comes from the compounding effect of these resets: each additional required head doubles the expected time, since any tails at the penultimate stage forces a complete restart. This structure is common in problems involving runs or patterns in sequences of independent trials, where progress can be lost and must be rebuilt from scratch.