Steps for a token to reach either end of a track

Question

A token sits on position 4 of a track numbered 0 to 10. Each step it moves one place left or right, each with probability 1/2. It is removed when it reaches position 0 or position 10. On average, how many steps does it take to be removed?

Accepted Answer

The token's position is a symmetric random walk absorbed at 0 and N = 10. Let Di be the expected remaining steps from position i, with D0 = D{10} = 0 and, for interior i, Di = 1 + 	frac12 D{i-1} + 	frac12 D{i+1}. The solution is Di = i(N - i). Starting at i = 4 with N = 10: D4 = 4 \cdot (10 - 4) = 4 \cdot 6 = 24 	ext{ steps.} Takeaway. Expected exit time of a fair \pm 1 walk on 0..N from i is i(N-i); here 4 \cdot 6 = 24.

Steps for a token to reach either end of a track

Your answer

Discussion

Learn the concepts

Related questions