User probabilist - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T12:31:44Z http://mathoverflow.net/feeds/user/11762 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process A type of stochastic jump process Probabilist 2010-12-22T01:01:28Z 2011-01-15T19:10:15Z <p>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)$?</p> <p>Context: This question is linked to this question</p> <p><a href="http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time" rel="nofollow">http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time</a></p> http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time Random walks on graphs: Cover time and blanket time Probabilist 2010-12-22T07:52:02Z 2010-12-22T19:28:00Z <p>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&lt;\delta&lt;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.</p> <p>So their now-proven conjecture was that $B_\delta \leq a C$ where $a$ is some constant.</p> <p>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.</p> <p>The remark is near the bottom of page 3 in their paper <a href="http://www.cs.utexas.edu/~diz/pubs/blanket.ps" rel="nofollow">http://www.cs.utexas.edu/~diz/pubs/blanket.ps</a></p> <p>For what it's worth, this question is related to another question I asked here <a href="http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process" rel="nofollow">http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process</a></p> http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process/50164#50164 Comment by Probabilist Probabilist 2011-01-04T14:14:05Z 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 http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process/50164#50164 Comment by Probabilist Probabilist 2010-12-23T00:58:12Z 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. http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process/50164#50164 Comment by Probabilist Probabilist 2010-12-22T22:48:23Z 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&gt;\mu$. This would solve the related problem that I posted here <a href="http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time" rel="nofollow" title="random walks on graphs cover time and blanket time">mathoverflow.net/questions/50137/&hellip;</a> 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$. http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time/50179#50179 Comment by Probabilist Probabilist 2010-12-22T21:37:31Z 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. http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time/50177#50177 Comment by Probabilist Probabilist 2010-12-22T21:30:33Z 2010-12-22T21:30:33Z Omer, it takes $Geom(1/2)$ to blanket the graph, but that blanket could be less than $2aC$. http://mathoverflow.net/questions/50137/random-walks-on-graphs-cover-time-and-blanket-time Comment by Probabilist Probabilist 2010-12-22T10:37:12Z 2010-12-22T10:37:12Z No, $a$ is dependent on $\delta$ http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process/50114#50114 Comment by Probabilist Probabilist 2010-12-22T06:23:15Z 2010-12-22T06:23:15Z Thanks, much appreciated. http://mathoverflow.net/questions/50110/a-type-of-stochastic-jump-process/50114#50114 Comment by Probabilist Probabilist 2010-12-22T02:08:59Z 2010-12-22T02:08:59Z What if $K$ = a\mu for some large positive constant $a$?