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?

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 847849) 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. 


Up to symmetry, there are very few ordered pairs (connected set of visited vertices, position of ant). We give each one a variable corresponding to the expected time from this ordered pair to the final state: $A = B+1$ $B = (B + 2C_{1,1})/3 + 1$ $C_{1,1} = (C_{1,2} + D_1 + D_{2,1})/3 + 1, C_{1,2} = (2C_{1,1} + D_{3,1})/3 + 1$ $D_1 = (2D_1 + E_{1,1})/3 + 1$ $D_{2,1} = (D_{2,2} + E_{1,3} + E_{2,1})/3 + 1, D_{2,2} = (D_{2,1} + D_{2,2} + E_{1,3})/3 + 1$ $D_{3,1} = (D_{3,2} + 2E_{1,4})/3 + 1, D_{3,2} = D_{3,1} + 1$ $E_{1,1} = (E_{1,2} + 2F_{1,1})/3 + 1, E_{1,2} = (E_{1,1} + 2E_{1,3})/3 + 1$, $E_{1,3} = (E_{1,2} + E_{1,4} + F_{1,1})/3 + 1, E_{1,4} = (2E_{1,3} + F_{2,1})/3 + 1$ $E_{2,1} = (E_{2,2} + F_{1,2} + F_3)/3 + 1, E_{2,2} = (E_{2,1} + E_{2,3} + F_{2,3})/3 + 1, E_{2,3} = (2E_{2,2} + F_{1,2})/3 + 1$ $F_{1,1} = (F_{1,1} + F_{1,2} + G_{1,1})/3 + 1, F_{1,2} = (2F_{1,1} + F_{1,2})/3 + 1$ $F_{2,1} = (F_{2,2} + 2G_{1,2})/3 + 1, F_{2,2} = (F_{2,1} + 2F_{2,3})/3 + 1, F_{2,3} = (2F_{2,2} + G_{1,2})/3 + 1$ $F_3 = (2F_3 + G_{1,3})/3 + 1$ $G_{1,1} = (H + 2G_{1,2})/3 + 1, G_{1,2} = (2G_{1,1} + G_{1,3})/3 + 1, G_{1,3} = G_{1,2} + 1$ $H = 0$ Now we solve for $A$: $H = 0$ $G_{1,1} = 7, G_{2,1} = 9, G_{1,3} = 10$ $F_{1,1} = 23/2, F_{1,2} = 13$ $F_{2,1} = 23/2, F_{2,2} = 27/2, F_{2,3} = 13$ $F_3 = 13$ $E_{1,1} = 527/38, E_{1,2} = 593/38, E_{1,3} = 569/38, E_{1,4} = 563/38$ $E_{2,1} = 89/6, E_{2,2} = 31/2, E_{2,3} = 47/3$ $D_1 = 641/38$ $D_{2,1} = 9529/570, D_{2,2} = 9887/570$ $D_{3,1} = 639/38, D_{3,2} = 677/38$ $C_{1,1} = 3517/190, C_{1,2} = 10799/570$ $B = 1901/95$ $A = 1996/95 \approx 21.010526316$ Corollary: I have too much spare time. 


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)^{S1} 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. 


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. 

