I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the average minimum time it takes to visit all vertices?
[Math] the cover time of a random walk on a cube
markov chainspr.probabilityrandom walks
Best Answer
An additional reference:
Chapter 12 in Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell is devoted to an elementary exposition of such cover problems.
A related problem:
The solution to Problem 6556 in the American Mathematical Monthly (Vol. 96, No. 9, Nov. 1989, pages 847-849) looks at the average number of steps for a random walk to visit all the edges on the cube in dimensions $d=2$, $3$, and $4$.
For $d=2$ the answer is easily computed to be 10.
For $d=3$ a system with 387 equations in 387 unknowns is solved to give an answer of about 48.5.
For $d=4$ the problem is declared hopeless.