A token sits on a vertex of a regular hexagon and at each step moves to one of the two adjacent vertices with equal probability. What is the expected number of steps until it reaches the vertex directly opposite its start?

A token sits on a vertex of a regular hexagon and at each step moves to one of the two adjacent vertices with equal probability. What is the expected number of steps until it reaches the vertex directly opposite its start?

Approach: Collapse the six vertices into states indexed by graph distance from the target, which the symmetry of the hexagon allows, then write and solve the three first-step equations.

9. Label states by distance to the target: the walk starts at d = 3 and must reach d = 0. First-step analysis from d = 3 gives E_3 = 1 + E_2, since both neighbours sit at distance 2. From d = 2 the neighbours are at distances 1 and 3, so E_2 = 1 + (E_1 + E_3)/2. From d = 1 the neighbours are the target and a distance-2 vertex, so E_1 = 1 + E_2/2. Substituting gives E_2 = 2 + (3/4)E_2, hence E_2 = 8, E_1 = 5 and E_3 = 9. Grouping states by symmetry is what reduces six unknowns to three. On a cycle of 2n vertices the same argument gives a hitting time of n^2, which is 9 for n = 3.

Follow-up: What is the expected number of steps to reach a vertex two positions away instead?

Key concepts: first-step analysis, random walk on a graph, hitting time, states by symmetry.