8
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ That's interesting. Is $a$ independent of $\delta$? $\endgroup$
    – Tom LaGatta
    Commented Dec 22, 2010 at 9:43
  • $\begingroup$ No, $a$ is dependent on $\delta$ $\endgroup$
    – Probabilist
    Commented Dec 22, 2010 at 10:37

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Omer, it takes $Geom(1/2)$ to blanket the graph, but that blanket could be less than $2aC$. $\endgroup$
    – Probabilist
    Commented Dec 22, 2010 at 21:30
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Probabilist
    Commented Dec 22, 2010 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .