Steps for a token on a square to hit the trapdoor

Question

Four corners of a square are labeled 1, 2, 3, 4 in order, with edges 1\!-\!2, 2\!-\!3, 3\!-\!4, 4\!-\!1. A token steps to one of the two neighboring corners with equal probability each move. Corner 4 is a trapdoor: the token stops when it lands there. It starts at corner 1, which is adjacent to the trapdoor. On average, how many steps until the token falls through corner 4?

Accepted Answer

Let e1, e2, e3 be the expected steps to reach corner 4 from corners 1, 2, 3; corner 4 has value 0. The neighbors are: 1\leftrightarrow\{2,4\}, 2\leftrightarrow\{1,3\}, 3\leftrightarrow\{2,4\}. So e1 = 1 + 	frac12 e2 + 	frac12 \cdot 0, \qquad e2 = 1 + 	frac12 e1 + 	frac12 e3, \qquad e3 = 1 + 	frac12 e2 + 	frac12 \cdot 0. By symmetry e1 = e3. Then e2 = 1 + 	frac12 e1 + 	frac12 e1 = 1 + e1. Substitute into e1 = 1 + 	frac12 e2: e1 = 1 + 	frac12 (1 + e1) = 	frac32 + 	frac12 e1 \;\Longrightarrow\; 	frac12 e1 = 	frac32 \;\Longrightarrow\; e1 = 3. Being adjacent to the trapdoor does not…

Steps for a token on a square to hit the trapdoor

Your answer

Discussion

Learn the concepts

Related questions