Ant Across the Cube

Question

An ant sits on one corner of a cube and each second walks along a randomly chosen edge (each of the 3 equally likely). What is the expected number of seconds to reach the diagonally opposite corner?

Accepted Answer

Lump states by symmetry. Only the graph distance to the target matters (Hamming distance of the corner's coordinates): start at distance 3, target at 0. Let E_d be the expected time from distance d. Neighbor structure: from distance 3 all moves go to distance 2; from distance 2, two moves go to distance 1 and one back to 3; from distance 1, one move hits the target and two go back to 2: E_3 = 1 + E_2, qquad E_2 = 1 + tfrac23 E_1 + tfrac13 E_3, qquad E_1 = 1 + tfrac23 E_2. Substitute the first into the second: E_2 = 2 + E_1 after simplification; plug into the third: E_1 = 1 + tfrac23(2 + E_1) Rightarrow tfrac13 E_1 = tfrac73 Rightarrow E_1 = 7. Then E_2 = 9 and E_3 = mathbf10. (Exact linear solve over all 8 vertices gives the same 7, 9, 10.) The two skills: (1) symmetry reduction, collapsing 8 states to 3 before writing equations is the difference between a 1-minute and a 15-minute solve; (2) first-step analysis as the universal hammer for expected hitting times. Sanity instinct: 10 > 3 (the shortest path) by a sensible margin since two of three moves from distance 1 bounce backward.

Ant Across the Cube

Problem

Your answer

Hints

More Brainteasers & Logic to train on