How long does a random walk on a line last?

Question

A token sits at position 3 on the integer line \{0, 1, 2, \dots, 10\}. Each second it steps left or right by one, each with probability 	frac12. Positions 0 and 10 are absorbing walls: the walk stops the instant it reaches either. What is the expected number of steps until the token hits a wall?

Accepted Answer

Let Di be the expected number of steps to absorption starting from position i, with D0 = D{10} = 0. First-step analysis gives, for each interior i, Di = 1 + 	frac12 D{i-1} + 	frac12 D{i+1}. Rearranged, D{i+1} - Di = Di - D{i-1} - 2, so the successive differences decrease by a constant 2: the solution is a downward parabola. The function satisfying the recurrence and the two zero boundary conditions is Di = i\,(N - i), \qquad N = 10. You can verify it directly: i(N-i) is zero at i = 0 and i = N, and plugging in shows each interior equation reduces to 1 = 1. Starting from i = 3: D3 = 3 \cdot …

How long does a random walk on a line last?

Your answer

More Probability questions