Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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

2 Answers 2

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$.

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

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.

share|improve this answer
    
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
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.