Steps to leave a short walk from the middle

Question

A marker starts at position 3 on a line numbered 0 to 6. Each step it moves \pm 1 with equal probability. It stops when it first reaches 0 or 6. On average, how many steps does that take?

Accepted Answer

The marker follows a symmetric random walk absorbed at 0 and N = 6. The expected remaining steps from position i solves Di = 1 + 	frac12 D{i-1} + 	frac12 D{i+1}, \quad D0 = D6 = 0, with solution Di = i(N - i). Starting from the center i = 3 with N = 6: D3 = 3 \cdot (6 - 3) = 3 \cdot 3 = 9 	ext{ steps.} The center is where the walk lasts longest, since i(N-i) is maximized at i = N/2. Takeaway. For a fair \pm 1 walk on 0..N, the duration from i is i(N-i), largest at the midpoint; here 3 \cdot 3 = 9.

Steps to leave a short walk from the middle

Your answer

Discussion

Learn the concepts

Related questions