Random Walks and Stopping Times for Quant Interviews

Random walks come up everywhere in quant interviews because they model price movements, betting outcomes, and almost any sequential-decision process under uncertainty. Stopping times come up because they’re the formal language for “when do I exit a position.” Together they generate a class of problems that test mathematical maturity and the ability to compute probabilities under uncertainty without grinding through full distributions. This guide covers the canonical setups, the techniques (martingales, recursive equations, reflection arguments), and what interviewers actually want to see.

The Setup: Simple Symmetric Random Walk

A simple symmetric random walk: start at 0; at each step, move +1 or -1 with probability 1/2 each, independently. Let S_n be the position at step n.

Basic facts:

E[S_n] = 0 (symmetric)
Var(S_n) = n (sum of n independent variance-1 random variables)
S_n / √n converges to a standard normal in distribution
The walk returns to 0 infinitely often with probability 1 (in 1D and 2D; in 3D the recurrence probability is ~0.34)

Many interview questions are variations on this walk — biased steps, absorbing boundaries, time changes — or its continuous analog (Brownian motion).

Hitting Probabilities and Gambler’s Ruin

The classic problem

“Random walk starts at 0. Probability of hitting +N before -M (where N, M > 0)?”

For symmetric walk: P(hit +N before -M) = M / (N + M). Symmetric and depends only on relative distances to the boundaries.

Why? By the optional stopping theorem applied to S_n (which is a martingale): E[S_τ] = E[S₀] = 0, where τ is the stopping time of hitting either boundary. If the walk hits +N with probability p and -M with probability (1-p), then 0 = pN + (1-p)(-M), giving p = M/(N+M).

Biased walk version

Walk goes +1 with probability p, -1 with probability q = 1-p, where p ≠ 1/2.

P(hit +N before -M) = [1 – (q/p)^M] / [1 – (q/p)^N+M]. Asymmetric formula.

For p < 1/2 (downward bias) and large N: P(hit +N before -M) ≈ (q/p)^-M / (q/p)^N+M… or more usefully, P → 0 as N grows. Drift dominates eventually.

Gambler’s ruin

Same setup with financial framing: I have $K, you have $L. Each round we flip a fair coin; loser pays winner $1. Probability I go bankrupt first?

This is the random walk hitting -K before +L starting from 0. P(I lose) = L / (K + L). The richer player wins more often. Counterintuitively, even in a fair game, finite bankrolls fail given enough plays.

Expected Hitting Time

Symmetric walk between absorbing boundaries

“Random walk from 0, walls at -M and +N. Expected number of steps until absorption?”

For symmetric walk: E[time to absorption] = N × M.

Why? Using martingale techniques: the process M_n = S_n² – n is a martingale. Apply optional stopping: 0 – 0 = E[S_τ²] – E[τ]. With absorption probabilities computed earlier, E[S_τ²] = N²(M/(N+M)) + M²(N/(N+M)) = MN(N+M)/(N+M) = MN. So E[τ] = MN.

This is one of the most-tested random-walk results.

One-sided walk

“Symmetric random walk from 0. Expected time until first hitting +N?”

Surprisingly: E[τ] = ∞. The walk can wander arbitrarily far in the negative direction before returning, contributing infinite expected time. The probability of hitting +N is 1 (recurrence), but the time has infinite mean.

This is a classic gotcha; many candidates assume finite expected time.

Reflection Principle

A powerful technique for computing probabilities involving extremes of random walks.

Statement (informally): the number of paths from 0 to N in n steps that hit some level M ≥ N along the way equals the number of paths from 0 to (2M – N) in n steps. The “reflection” maps walks above M to walks ending higher.

Application: “Random walk from 0 in n steps. P(maximum ≥ M)?”

By reflection: P(max ≥ M) = P(S_n ≥ M) + P(S_n < M and reflection-of-walk gives end ≥ M) = … after careful argument: P(max ≥ M) = 2 × P(S_n ≥ M) – P(S_n = M). For continuous Brownian motion, P(max_[0,t] ≥ M) = 2 × P(W_t ≥ M).

This shows up in option pricing (barrier options) and is testable in research-engineering interviews at firms like Jane Street, Two Sigma, D. E. Shaw.

Stopping Times

A stopping time is a time τ that depends only on the walk’s history up to time τ — you can decide to “stop” without seeing the future.

Examples of stopping times:

“First time the walk reaches +5”
“First time S_n² exceeds 100″
“Step 1000” (deterministic stopping)

NOT a stopping time: “the step before the maximum is reached” — requires knowing the future.

The optional stopping theorem: under standard conditions, E[X_τ] = E[X₀] for a martingale X_n. The conditions are technical (bounded stopping time, bounded increments, etc.) but for most interview problems they’re satisfied.

Why this matters: stopping problems in trading are everywhere — “when do I exit this position?” — and optional stopping gives you tools to compute expectations of exit conditions without simulating paths.

Classic Interview Problems

The drunk on a cliff

“A drunk takes random steps; cliff is one step to the left. Probability he eventually falls off?”

If symmetric, probability is 1 (recurrence). If biased away from cliff (probability p > 1/2 of stepping right), probability is q/p where q = 1 – p (less than 1).

St. Petersburg paradox connection

“You play a game where each round a fair coin is flipped. You start with $1. If heads, your wealth doubles; if tails, you lose all your wealth. What’s the expected number of rounds you survive?”

Geometric: E = 2. (Probability of survival each round is 1/2; expected wait until first tails is 2.)

Wald’s identity application

“You flip fair coins until you’ve seen 5 more heads than tails. Expected number of coin flips?”

By Wald’s identity: E[number of flips] × E[heads minus tails per flip] = E[final heads minus tails] = 5. But E[per-flip heads minus tails] = 0 for symmetric walk! So Wald doesn’t directly apply — expected flips is actually infinite. Trick question: standard candidates miss this.

Doubling strategy

“You bet $1 on a fair coin. If you lose, double your bet. Continue until you win once, then stop. Expected total profit?”

You eventually win once (probability 1). At that win, you get back all losses + $1. Expected profit = $1.

But: expected total wagered is infinite. The strategy works in theory but requires infinite bankroll. Real-world constraint exposes the trap.

Brownian Motion (Quick Conceptual Reference)

The continuous analog of random walks. Brownian motion W_t has:

W₀ = 0
Independent, normally-distributed increments: W_t – W_s ~ N(0, t – s)
Continuous paths (almost surely)

For interviews:

Most random-walk results have Brownian motion analogs
Geometric Brownian motion (S_t = S₀e^{μt + σW_t}) is the standard model for stock prices in Black-Scholes
For options-pricing-adjacent rounds, knowing the basic structure (drift μ, volatility σ, log-normal distribution) is essential

Tactical Patterns

Pattern 1: Identify the relevant martingale

Many random-walk problems yield to applying the optional stopping theorem to a clever martingale. Common martingales:

S_n itself (for symmetric walk)
S_n² – n (variance martingale)
(p/q)^S_n for biased walks
Exponential martingales for Brownian motion

Pattern 2: Set up a recursive equation

Let f(k) = expected value of some quantity starting from position k. Write f(k) = (1/2)f(k-1) + (1/2)f(k+1) + (per-step contribution). Solve with appropriate boundary conditions.

Pattern 3: Use reflection

For problems involving maxima or minima, reflection arguments often beat direct enumeration.

Pattern 4: Sanity-check with extremes

If your formula gives expected hitting time NM, check N=1, M=1: should give 1 (single step ends the walk). Check N=1, M=large: should be roughly N × M / N = M (most walks end at -M because the +N boundary is closer; expected time near M, which the formula gives).

Practice Strategy

Weeks 1–2: work through 20+ random-walk problems from Crack and Zhou. Focus on getting comfortable with hitting probabilities and expected hitting times.

Weeks 3–4: deeper martingale techniques, optional stopping applications, reflection arguments. Joshi’s Quant Job Interview Questions and Answers is good for this depth.

Weeks 5+: Brownian motion connections, geometric Brownian motion for option pricing prep, Wald’s identity applications. Hull’s Options, Futures, and Other Derivatives for the financial-application context.

Frequently Asked Questions

How is “random walk” different from “Brownian motion” in interviews?

Random walk is the discrete-time, integer-step process. Brownian motion is the continuous-time, continuous-path limit. Most discrete random-walk results have Brownian analogs (often with the same formula structure). For prop-firm interviews, discrete random walk is sufficient. For hedge-fund quant-research interviews and bank strats interviews, Brownian motion comes up because options pricing and stochastic calculus build on it. Know that they’re related; know specific results in whichever domain matches your target firm.

What’s the difference between expected hitting time being infinite vs finite?

If a stopping time has finite expected value, the average of many trials converges to a finite number. If it’s infinite, no finite average exists; large outlier waits dominate. Practically: a one-sided random walk (no upper boundary) reaches any positive level eventually with probability 1, but the expected time is infinite because the walk can wander arbitrarily far in the negative direction first. With absorbing boundaries on both sides, the expected hitting time is finite (and equals N×M for symmetric walk). The distinction matters because traders running real strategies need finite-time confidence in their stops.

How do I know when to use the optional stopping theorem vs other methods?

Optional stopping is most useful when (1) you can identify a martingale relevant to the problem, and (2) the stopping time is bounded or the increments are bounded. Common pattern: “expected something at hitting time” → identify martingale, apply E[X_τ] = E[X₀] or = E[X₀] + drift. If the martingale isn’t obvious, fall back to recursive equations. With practice, the choice becomes intuitive.

Why does the gambler’s ruin problem matter for trading?

Direct connection: a trader with finite capital trading positive-EV strategies still faces ruin risk if individual trades have negative outcomes that cumulatively exceed capital. The random-walk analog: even with positive drift, finite bankroll means non-zero probability of hitting zero before infinity. Position-sizing rules (Kelly criterion, fractional Kelly, fixed-fractional sizing) are practical responses to gambler’s-ruin reasoning. Interviewers test the math because traders apply it daily.

Are random-walk problems harder at hedge funds than at prop firms?

Generally yes. Prop firms (Jane Street, Citadel Securities, HRT) test discrete random-walk problems at brainteaser depth — hitting probabilities, expected hitting times. Hedge funds (Two Sigma, D. E. Shaw, Citadel hedge fund) push deeper into stochastic processes — Brownian motion, Itô calculus, stopping-time theory at academic depth. Bank Strats interviews are similar to hedge-fund depth on the math, with more emphasis on derivative-pricing applications. Calibrate prep accordingly.