Expected steps for a fair walk to hit a wall

Question

A token sits at position 3 on a line marked 0 to 10. Each step it moves +1 with probability $\tfrac12$ or -1 with probability $\tfrac12$ . It stops the moment it reaches position 0 or position 10.

What is the expected number of steps until the token stops?

Accepted Answer

Let ek be the expected number of steps to reach 0 or 10 starting from position k. At the walls nothing more happens: e0 = e{10} = 0. First-step analysis. One step is taken now, then the token is at k \pm 1: ek = 1 + 	frac12 e{k-1} + 	frac12 e{k+1}, \qquad 0 < k < 10. Rewrite as e{k+1} - ek = ek - e{k-1} - 2: the differences drop by 2 each step, the signature of a downward parabola. The solution with e0 = e{10} = 0 is ek = k(10 - k). (Check: k(10-k) satisfies k(10-k) = 1 + 	frac12(k-1)(11-k) + 	frac12(k+1)(9-k).) At k = 3, e3 = 3 \cdot 7 = 21. Takeaway. For a symmetric walk between 0 and N…

Expected steps for a fair walk to hit a wall

Your answer

Discussion

Learn the concepts

Related questions