What is the cover time of a random walk on a cube? 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?
 A: 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.     
A: Yet another reference: Some sample path properties of a random walk on the cube, by Peter Matthews (1989). This covers the asymptotic distribution of the time $T$ taken to visit all vertices, the distribution of the number of vertices not visited at times near to $\mathbb{E}[T]$, and the expected time taken for the walk to come within a distance $d$ of all vertices.
A: More generally, you could ask this for any irreducible Markov chain and any starting state.
For each nonempty set S of vertices not containing the starting state $s_0$, let $T_S$ be the time (in steps) it takes to reach S (i.e. if $X_t$ is the state after $t$ steps, the least $t$ such that $X_t \in S$).  Then the
expected time to visit all states is $\sum_S (-1)^{|S|-1} E[T_S]$.  Each $E[T_S]$ is straightforward to calculate: if $P$ is the transition matrix, $P_{S^c}$ the submatrix
for rows and columns not in $S$, and $I_{S^c}$ the corresponding submatrix of the identity matrix, $E[T_S] = \sum_{j \in S^c} ((I_{S^c} - P_{S^c})^{-1})_{s_0,j}$.  For your problem I get a final answer of 1996/95 = 21.01052632.
