# Random walks on graphs: Cover time and blanket time

Winkler and Zuckerman conjectured that the blanket time is within a constant factor of the cover time. The conjecture was recently proved. The cover time $C$ is the expectation of the first time $t$ that the walk has seen every vertex. The blanket time $B_\delta$, where $0<\delta<1$ is some constant, is the expectation of the first time $t$ such that each vertex $v$ has been visited at least $\delta \pi_v t$ times. That is, it is the expected time for all the vertices to have been seen roughly as expected by the stationary distribution.

So their now-proven conjecture was that $B_\delta \leq a C$ where $a$ is some constant.

One remark in their paper that I can't see the justification of is the claim that this implies that the expectation of the first time that each vertex $v$ has been visited $\pi_vC$ times is $O(C)$. I was wondering if anyone can offer some insight.

The remark is near the bottom of page 3 in their paper http://www.cs.utexas.edu/~diz/pubs/blanket.ps

For what it's worth, this question is related to another question I asked here A type of stochastic jump process

-
That's interesting. Is $a$ independent of $\delta$? – Tom LaGatta Dec 22 '10 at 9:43
No, $a$ is dependent on $\delta$ – Probabilist Dec 22 '10 at 10:37

With probability at least $1/2$ the blanket time $B_{1/2}$ is at most $2aC$. It only takes a Geom$(1/2)$ such blocks to get $\pi_v C$ visits to each $v$.

-
Omer, it takes $Geom(1/2)$ to blanket the graph, but that blanket could be less than $2aC$. – Probabilist Dec 22 '10 at 21:30

Suppose there exist $a$ and $\delta$ such that $B_\delta\le aC$ for all graphs.

Fix a graph and start a random walk at an arbitrary vertex. Repeatedly wait for a $\delta$-blanketting and reset the visit counts until the total time taken exceeds $C/\delta$. The expected time for this is at most $(1/\delta+a)C$ because the initial blanketting phases take in total at most $C/\delta$ steps (deterministically) and the expected time of the final blanketting is (using the strong Markov property) at most $B_\delta$. In particular $T=O(C)$.

By construction we have $T\ge C/\delta$. Also since $T$ is obtained by concatenating a sequence of $\delta$-blankettings, it is itself a $\delta$-blanketting. This means that each vertex $v$ is covered at least $\delta\pi_v T\ge \pi_v C$ times.

-
The problem is that it doesn't seem to be true that the final round of blanketing actually has an expectation $O(C)$. What we are talking about is a series of jumps on the number line until we cross $K=C/\delta$, and we want to know what in the final jump, the value $t-K=O(C)$. However, as can be seen from the second counter example in the link to my previous question - this is not necessarily the case. – Probabilist Dec 22 '10 at 21:37