An ant starts at one corner of a cube and moves along edges randomly. What is the expected number of steps to reach the opposite corner?

An ant starts at one corner of a cube and moves along edges randomly. What is the expected number of steps to reach the opposite corner?

Approach: Set up Markov chain with states based on distance from target.

10 steps. Let E_d be expected steps from distance d. E_0=0, E_1=1+E_2, E_2=1+2/3*E_1+1/3*E_3, E_3=1+E_2. Solving gives E_3=10.

Follow-up: What about an n-dimensional hypercube?

Key concepts: Markov chain, hitting time, system of equations.