Consider a random walk on an undirected graph which, at each step, moves to a uniformly random neighbor. Define $T(u,v)$ to be the expected time until such a walk, starting from $u$, arrives at $v$, and let $T = \max_{u,v} T(u,v)$. Define $G(u)$ to be the expected time until such a walk, starting from $u$, visits every vertex and let $G = \max_u G(u)$. Is it true that $G \leq cT$ for some constant $c$ which does not depend on the graph and any of its parameters (e.g., number of nodes)?
Cover times and hitting times of random walks
2
$\begingroup$
probability
graph-theory
-
0btw, I believe the "standard" notation for $T(u,v)$ is actually $H(u,v)$ (or $H_{uv}$). And $C$ instead of $G$. – 2012-05-10
2 Answers
3
That seems false.
For the complete graph $K_n$, $T = T(u,v) = \mathcal{O}(n)$, but $G = \Theta(n \log n)$.
-
0This is a bit simpler than my example :-) – 2012-05-09
2
No. Take a graph with one central vertex and $n$ vertices connected only to the central vertex. The expected time to visit every vertex is determined by the coupon collector's problem and goes as $n\log n$, whereas the expected time to visit any vertex from any other vertex only goes as $n$.