Expected time for the ant to return home on a cube

Question

An ant starts at one vertex of a cube and each second moves along a randomly chosen edge (each of the $3$ incident edges with probability $\tfrac13$ ).

What is the expected number of steps until the ant first returns to its starting vertex?

Accepted Answer

There is a beautiful shortcut for return times on any graph where the walk picks a uniformly random incident edge. The stationary probability of being at a vertex v is proportional to its degree, \piv = \frac{\deg(v)}{2E}, and the expected return time to v is the reciprocal: E[	ext{return to } v] = \frac{1}{\piv} = \frac{2E}{\deg(v)}. A cube has 8 vertices of degree 3, so its edge count is E = \frac{8 \cdot 3}{2} = 12. Every vertex has degree 3, so E[	ext{return}] = \frac{2 \cdot 12}{3} = \frac{24}{3} = 8. The ant returns home in 8 steps on average. Cross-check by first-step analysis. After…

Expected time for the ant to return home on a cube

Your answer

More Probability questions