How long a graph random walk takes to hit every vertex?

Question

I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step.

On average, how many steps $T$ until the random walk hits every vertex? Can this be efficiently computed?

Here are some cases for which I'd like the question answered (from most general to least general). The more general the case you can solve, the better.

1. $G$ is a directed weighted graph, and an edge is chosen w.p. proportional to its weight.
2. $G$ is an undirected weighted graph, and an edge " " "
3. $G$ is a directed graph.
4. $G$ is an undirected graph.
5. $G$ is a tree.

For bonus points, it'd be cool if you could say something about the distribution of $T$. E.g. is there a chernoff-style bound like $\Pr[T\geq t]\leq e^{-t/\tau}$? What is the variance of $T$? Etc.

All I can easily think of is the following: compute the transition matrix $P$ for the random walk by normalizing rows of the adjacency matrix $A$. Its highest eigenvalue will be 1, and second-highest eigenvalue will be $\lambda_2$. The random walk will converge to its stationary distribution roughly exponentially at a rate (time-scale) of $\frac{1}{\lambda_2}$. At the stationary distribution, each node will have positive probability (because $G$ is connected). So I imagine that $T$ will, at worst, be on the order of $\frac{1}{\lambda_2}$.

Answer 1

The cover time is at most the maximal hitting time multiplied by the harmonic number $1+\ldots+1/n$. This is the Mathews bound, see, e.g., Section 11.2 in [1].

In fact, the cover time can be estimated up to a constant factor deterministically in polynomial time. See [2], where the history of the problem is also discussed.

[1] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/ https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf

[2] Ding, Jian, James R. Lee, and Yuval Peres. "Cover times, blanket times, and majorizing measures." In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 61-70. 2011.