Random walk across a hexagon to the far vertex

Question

Six vertices sit around a hexagon, each joined to its two neighbors. A walker starts at one vertex; each step it moves to a neighbor, each with probability $\tfrac12$ . It stops on reaching the opposite vertex (three edges away).

What is the expected number of steps to reach the opposite vertex?

Accepted Answer

Group vertices by their distance d to the target (measured along the cycle): the start is at d = 3, and d = 0 is the target. Let ed be the expected steps from a vertex at distance d, with e0 = 0. By symmetry both vertices at each distance behave alike. Stepping changes the distance by \pm 1, except the start (d = 3) whose two neighbors are both at d = 2: e3 = 1 + e2, \qquad e2 = 1 + 	frac12 e3 + 	frac12 e1, \qquad e1 = 1 + 	frac12 e2 + 	frac12 (0). From the last, e1 = 1 + 	frac12 e2. Put e3 = 1 + e2 into the middle equation: e2 = 1 + 	frac12(1 + e2) + 	frac12 e1 = 	frac32 + 	frac12 e…

Random walk across a hexagon to the far vertex

Your answer

Discussion

Learn the concepts

Related questions