User probabilist - MathOverflow

A type of stochastic jump process

2010-12-22T01:01:28Z

Let $X \geq 1$ be a integer r.v. with $E[X]=\mu$. Let $X_i$ be a sequence of iid rvs with the distribution of $X$. On the integer line, we start at $0$, and want to know the expected position after we first cross $K$, which is some fixed integer. Each next position is determined by adding $X_i$ to the previous position. So the question is, if we stop this process after the first time $\tau$ for which $Y_{\tau}=\sum_{i=1}^{\tau}X_i > K$, that is, after the first time it crosses $K$, then what is $E[Y_{\tau}-K]$?. Can we get a bound of $O(\mu)$?

Context: This question is linked to this question

http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time

Random walks on graphs: Cover time and blanket time

2010-12-22T07:52:02Z

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

Comment by Probabilist

2011-01-04T14:14:05Z

If $n\rightarrow \infty$ and $\mu=\mu(n)\rightarrow \infty$ as $n\rightarrow \infty$ and $\omega=\omega(n)\rightarrow \infty$ as $n\rightarrow \infty$ , then can we say, by rescaling that $\lim_{n\rightarrow \infty}\frac{m(\omega\mu)}{\omega\mu} = \frac{1}{\mu}$ and thus $m(\omega\mu)\sim \omega$? Intuitively this would make sense, but seems a little too easy

Comment by Probabilist

2010-12-23T00:58:12Z

Yes, I wrote $m(K) \sim K/\mu$. The ASCII characters look fairly clear on my screen, but I will make a point to use Latex in future.

Comment by Probabilist

2010-12-22T22:48:23Z

Shai, thanks for this very nice answer. I am not familiar with renewal theory (my user name is somewhat ironic), but if for my purposes I am happy to let K→∞, then m(K)∼K/μ and so $E(Y_\tau)\sim (1+K/\mu)\mu= O(K)$ when $K>\mu$. This would solve the related problem that I posted here mathoverflow.net/questions/50137/… when we allow the cover time C (which is equivalent to K here) to go to ∞, which of course, is the case for for all graphs as their size goes to $\infty$.

Comment by Probabilist

2010-12-22T21:37:31Z

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.

Comment by Probabilist

2010-12-22T21:30:33Z

Omer, it takes $Geom(1/2)$ to blanket the graph, but that blanket could be less than $2aC$.

Comment by Probabilist

2010-12-22T10:37:12Z

No, $a$ is dependent on $\delta$

Comment by Probabilist

2010-12-22T06:23:15Z

Thanks, much appreciated.

Comment by Probabilist

2010-12-22T02:08:59Z

What if $K$ = a\mu for some large positive constant $a$?