2
$\begingroup$

Uriel Feige has shown in 1995 in his paper "A Tight Lower Bound on the Cover Time for Random Walks on Graphs", the following result:

For any graph $G$ on $n$ vertices, and any starting vertex $u$ $$E_u[G]\ge n\ln{n}+o(n\ln{n}).$$

Here $E_u[G]$ denotes the cover time, that is, the expected number of steps that it takes a walk that starts at $u$ to visit all vertices of $G$.

Let $C_u[G]$ denote the number of steps that it takes a walk that starts at $u$ to visit all vertices of $G$. In that case, $E_u[G] = \mathbb{E}(C_u[G])$. Say that an event occurs with high probability (or whp) if it's probability tends to $1$ when $n$ tends to $\infty$. Clearly, if for a vertex $u$, $C_u[G]\ge n\ln{n}+o(n\ln{n})$ whp, then $E_u[G]\ge n\ln{n} + o(n\ln{n})$. However, the opposite does not follow.

Still, is it true that the following (stronger) result holds?

For any graph $G$ on $n$ vertices, and any starting vertex $u$ $$C_u[G]\ge n\ln{n}+o(n\ln{n})$$ whp.

If not, is there any non-trivial lower bound for general graphs? For specific graphs? It is known, for example, for the complete graph $K_n$ (this is simply a coupon-collector problem).

$\endgroup$
2
$\begingroup$

A general result of Aldous is that if the expected cover time is much larger than the maximal expected hitting time (maximum over all vertices) then the cover time concentrates, i.e. $C/EC\sim 1$. The bound is non asymptotic. See Theorem 1 in http://scf.berkeley.edu/~aldous/Papers/me47.pdf

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ofer, thanks for your answer. It seems like this result applies only for specific families of graphs, rather then for general graphs (those families for which the conditions of Theorem 3 hold). Is it even true for general graphs? $\endgroup$ – Bach Jul 19 '15 at 6:11
  • $\begingroup$ As I wrote: the result I mentioned has as condition that the expected cover time should be asymptotically much larger than the maximum hitting time. Of course this implies something about the graph (think 1D torus). This result covers for example the complete graph you asked about. As for the rest of your question, do you know a graph where the maximum hitting time to a vertex is smaller than nlog n? $\endgroup$ – ofer zeitouni Jul 19 '15 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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