1
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ the buzzword is "cover time" $\endgroup$ Jul 12, 2021 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, 2021 at 23:41
  • $\begingroup$ There is no need for the $3e$ factor, see my answer below. $\endgroup$ Jul 21, 2022 at 4:54

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.