Recursion & First-Step Analysis in quant interviews
"Let f(n) = expected…" — the universal technique for self-similar probability problems.
TRY A PROBLEM NOW · NO SIGNUP
In the classical secretary problem, as n → ∞, what fraction should you reject outright before accepting the next best-so-far candidate?
WHAT IT IS
Recursion — specifically first-step analysis — is the technique of expressing the expected value (or probability) of interest as a function of the state, then writing a recurrence based on what happens after one step. If you're at state k, you know the distribution of next states, and you know the expected cost to get there (often just 1 step); so E[f(k)] = 1 + Σ P(next state j | current state k) · f(j). Solve the system, often by spotting a pattern, writing the generating function, or grinding through the linear algebra. First-step analysis is the default tool for waiting-time problems, Markov-chain expected values, and any problem where the structure after one step is a shrunken version of the original. Interviewers probe recursion skills because they distinguish candidates who have a reflex for decomposition from candidates who try to solve everything in closed form.
WHEN IT APPEARS IN INTERVIEWS
Universal. First-step analysis is the workhorse across every firm's probability rounds. SIG and Jane Street push the hardest — they'll ask follow-ups that require solving the recurrence in closed form, not just writing it.
FIRMS THAT TEST THIS
SAMPLE PROBLEMS
You flip a fair coin until you see the pattern HTH. What's the expected number of flips?
Define states based on how much of HTH you've matched so far: {empty, H, HT, HTH}. Write E[state] = 1 + Σ p(transition) · E[next state] for each non-absorbing state. Solve: E = 10.
A drunk starts at position 5 on a line from 0 to 10. Each step: +1 or -1 with equal probability. Expected steps to first hit 0 or 10?
Let f(k) = E[steps | start at k]. Boundary: f(0) = f(10) = 0. Recurrence: f(k) = 1 + ½ f(k-1) + ½ f(k+1). Solve the second-order linear recurrence; answer: f(k) = k(10 - k) = 25 for k = 5.
You roll a fair six-sided die repeatedly, summing until the running sum is greater than 6. Expected value of the final sum?
Let f(k) = expected final sum given running sum is k. For k > 6: f(k) = k. For k ≤ 6: f(k) = (1/6) Σ_{d=1..6} f(k + d). Work backwards from f(6) down to f(0); answer is f(0) ≈ 8.03.
SOLVING STRATEGIES
- ·Define the state clearly and minimally — the state must capture everything relevant about 'where you are' in the problem.
- ·Write the recurrence with the conditioning on the first step explicit: f(state) = (immediate cost) + Σ P(next | state) · f(next).
- ·Handle boundary conditions first — they're usually trivial and fixing them early catches errors later.
- ·For finite state spaces, the recurrence is a linear system. Solve via substitution, matrix inversion, or pattern recognition.
- ·For infinite state spaces, look for generating functions, invariants, or a closed-form guess you can verify by plugging in.
COMMON VARIATIONS
- ·Multi-dimensional state: two counters, a position plus a history flag, etc.
- ·Conditional recurrences: 'given that we eventually win, expected number of steps'.
- ·Infinite-horizon recurrences — often require more care around convergence.
- ·Continuous-state analogues: integral equations instead of sums.
FAQ
The state should be the smallest summary of the past that's sufficient to describe the future. If the problem is Markov, the current state is the position. If it has partial history (like coin-pattern matching), include the prefix match in the state.
That's fine — solving it numerically via substitution or iteration is still a valid answer for interviews, as long as you can explain why. Interviewers value the correct setup more than closed-form elegance.
They're essentially the same idea at different levels of formality. First-step analysis is DP on a probabilistic state space; DP is the algorithmic implementation. Interview answers usually stop at the recurrence and don't need to discuss implementation.
When the state space is infinite, when multiple recurrences couple together, or when you need the exact distribution (not just expectation). Jane Street final rounds sometimes push into these territories.
RELATED TECHNIQUES
If the problem has states and transitions, it's a Markov chain — and quant interviewers love them.
The single most common technique in quant interviews. Every problem reduces to it eventually.
When to stop and take the offer — the secretary problem and its cousins.
Not ready to sign up? Get 5 hand-picked quant interview problems every week. No spam, unsubscribe any time.
Drill recursion & first-step analysis problems now
400+ problems, adaptive selection, AI-generated alternative explanations. Free tier covers 20 attempts.
Start practicing free