Random walk across 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 for the ant to reach the diagonally opposite vertex?

Accepted Answer

Classify vertices by graph distance to the target: the start is at distance 3, its three neighbors at distance 2, their neighbors at distance 1, and the target at distance 0. By symmetry, the expected hitting time depends only on this distance. Let Ed be the expected steps from distance d. Count where each move leads: - Distance 3 (start): all 3 neighbors are at distance 2: \quad E3 = 1 + E2. - Distance 2: 2 neighbors at distance 1, 1 neighbor back at distance 3: \quad E2 = 1 + 	frac23 E1 + 	frac13 E3. - Distance 1: 1 neighbor is the target, 2 neighbors at distance 2: \quad E1 = 1 + 	frac2…

Random walk across a cube

Your answer

More Probability questions