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

This is a followup to my question Cover times and hitting times of random walks.

Consider a random walk on an undirected graph with $n$ vertices 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 \log^k n$$ for some constants $c,k$ which do not depend on the graph or on $n$?

share|cite|improve this question
look at thm 26, chapter 2 in Aldous' & Fill's online book, possibly subtitled 'the Matthews' method'. – mike May 10 '12 at 13:15
Thanks! This completely answers my question. – robinson May 10 '12 at 20:24
@mike: If that completely answers the question, could you post it as an answer with a brief statement of what thm 26 states? – George Lowther May 11 '12 at 22:30

Your Answer


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

Browse other questions tagged or ask your own question.