Expected exit time of a random walk
Asked at Jane Street, DE Shaw
A token starts at integer position k on the line 0, 1, ..., N. Each step it moves +1 or -1 with equal probability. It stops the moment it hits either barrier 0 or N (gambler's ruin).
Estimate the expected number of steps until it stops, by Monte Carlo, then compare against the exact answer.
N = 10, k = 3 -> ~21 steps (exact: k(N-k) = 3*7 = 21)
Show a hint
Simulate many independent walks and average the step counts. For the exact value, let be the expected steps from position and condition on the first move: , with .
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.