Take the 2-minute tour ×
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.

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|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
add comment

2 Answers

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|improve this answer
    
This is a bit simpler than my example :-) –  joriki May 9 '12 at 22:11
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.