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.
- $G$ is a directed weighted graph, and an edge is chosen w.p. proportional to its weight.
- $G$ is an undirected weighted graph, and an edge " " "
- $G$ is a directed graph.
- $G$ is an undirected graph.
- $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}$.