One-way wall, expected steps home from the far end

Question

A checker sits on square 3 of a short board with squares 0, 1, 2, 3. Square 0 is the goal: the checker stops there. From squares 1 or 2 it steps left or right at random. Square 3 is a wall: from square 3 the only move is to square 2.

On average, how many steps until the checker reaches square 0 from square 3?

Accepted Answer

Let t1, t2, t3 be the expected steps to reach 0 from squares 1, 2, 3. The wall at 3 forces a move to 2, and squares 1 and 2 give a fair choice: t1 = 1 + 	frac12 \cdot 0 + 	frac12 t2, \qquad t2 = 1 + 	frac12 t1 + 	frac12 t3, \qquad t3 = 1 + t2. Put t3 = 1 + t2 into the middle equation: t2 = 1 + 	frac12 t1 + 	frac12(1 + t2) \implies 	frac12 t2 = 	frac32 + 	frac12 t1 \implies t2 = 3 + t1. Then t1 = 1 + 	frac12(3 + t1) = 	frac52 + 	frac12 t1, so 	frac12 t1 = 	frac52 and t1 = 5. Hence t2 = 8 and t3 = 1 + 8 = 9. Takeaway. A reflecting wall just changes one equation (forced move) while…

One-way wall, expected steps home from the far end

Your answer

Discussion

Learn the concepts

Related questions