The drunkard near the cliff
Asked at DE Shaw, Optiver
A drunkard stands k steps from the edge of a cliff at position 0. Each step they stagger away from the cliff with probability p and toward it with probability 1 - p. There is no wall on the other side, the line runs to infinity. With p = 0.4 the pull toward the cliff wins, so a fall is certain.
Estimate the expected number of steps until they fall (hit 0) by Monte Carlo, then derive the closed form.
k = 5, p = 0.4 -> ~25 steps
Show a hint
There is only one barrier, so the parabola formula for two barriers does not apply. Use the drift: on average, each step moves the drunkard toward safety, which is negative here.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.