Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question
btw, I believe the "standard" notation for $T(u,v)$ is actually $H(u,v)$ (or $H_{uv}$). And $C$ instead of $G$. – Aryabhata May 10 '12 at 1:46
up vote 3 down vote accepted

That seems false.

For the complete graph $K_n$, $T = T(u,v) = \mathcal{O}(n)$, but $G = \Theta(n \log n)$.

share|cite|improve this answer
This is a bit simpler than my example :-) – joriki May 9 '12 at 22:11

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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