## Random walks on graphs: Cover time and blanket time

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

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

## 2 Answers

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 2010 at 21:37

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 2010 at 21:30
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 42, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9576865434646606, "perplexity_flag": "head"}