MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 15 characters in body

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$ for 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 http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process

1

# 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$ for each vertex $v$ has been visited $\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 http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process