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}$.

  • 2
    $\begingroup$ the buzzword is "cover time" $\endgroup$ Jul 12 at 23:01
  • $\begingroup$ @mathworker21 Thanks! This paper (resources.mpi-inf.mpg.de/departments/d1/teaching/ws11/SGT/…) gives nice bound on $T$, which is that it's less than $3 e H_M \ln(n) + 2n$, where $e=2.718...$ and $H_M$ is the maximum hitting time between any two vertices (which is computable in poly time). $\endgroup$
    – chausies
    Jul 12 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.