Random walk across an octahedron

Question

An ant starts at one vertex of a regular octahedron and each second moves along a randomly chosen edge. Every vertex of an octahedron connects to $4$ others (all except the single vertex directly opposite it), so each of those $4$ edges is chosen with probability $\tfrac14$ .

What is the expected number of steps for the ant to reach the vertex directly opposite its start?

Accepted Answer

Lump vertices by distance to the target. The start is at distance 2; the four "equator" vertices are each at distance 1; the target is at distance 0. By symmetry the expected hitting time depends only on this distance. Let Ed be the expected steps from distance d. From the start (distance 2). All 4 neighbors are equator vertices at distance 1: E2 = 1 + E1. From an equator vertex (distance 1). Its 4 neighbors are: the target (distance 0), the start (distance 2), and the 2 other equator vertices (distance 1). So E1 = 1 + 	frac14 \cdot 0 + 	frac14 E2 + 	frac24 E1. Rearrange the second equatio…

Random walk across an octahedron

Your answer

More Probability questions