Will a random walk on [0, inf) tend to infinity? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-22T23:40:12Z http://mathoverflow.net/feeds/question/60417 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60417/will-a-random-walk-on-0-inf-tend-to-infinity Will a random walk on [0, inf) tend to infinity? wjomlex 2011-04-03T08:49:13Z 2011-04-03T12:58:44Z <p>Consider a random walk on [0, inf) where you start at 0. With probability p = 0.5, you increase by 1. With probability (1-p) = 0.5, you decrease by 1, but not below 0.</p> <p>As time goes to infinity, will your position tend to infinity? If not, to what finite value does it converge? </p> <p>Edit: To be a bit more precise, what is the limit of the average position as time goes to infinity?</p> <p>If your position tends to infinity for p = 0.5, for which other probabilities p is this true? (Clearly p > 0.5 will cause you to tend to infinity, so p &lt; 0.5 is what I'm after)</p> <p>What is the probability of being at position x after an arbitrary amount of steps?</p> <p>I made a simple simulation to test the p = 0.5 case, and after 500 million iterations, it seems to tend to infinity, but I'd like a more solid explanation.</p> <p>Thanks!</p> http://mathoverflow.net/questions/60417/will-a-random-walk-on-0-inf-tend-to-infinity/60419#60419 Answer by Aryeh Kontorovich for Will a random walk on [0, inf) tend to infinity? Aryeh Kontorovich 2011-04-03T08:53:55Z 2011-04-03T08:53:55Z <p>For any $p>0$ and any finite $N$, with probability one, eventually your random walk will exceed $N$.</p> http://mathoverflow.net/questions/60417/will-a-random-walk-on-0-inf-tend-to-infinity/60422#60422 Answer by Aryeh Kontorovich for Will a random walk on [0, inf) tend to infinity? Aryeh Kontorovich 2011-04-03T09:42:02Z 2011-04-03T09:42:02Z <p>Let me try again. Let $R_n$ be the random variable denoting the longest contiguous run of heads for $n$ independent $p$-biased coin tosses. </p> <p>It is well-known <a href="http://mathdl.maa.org/images/upload_library/22/Polya/07468342.di020742.02p0021g.pdf" rel="nofollow">1</a> that $E R_n\sim\log_{1/p}((1-p)n)$ plus small correction terms (the variance is $O(1)$). </p> <p>This means that $S_n=\sum_{i=1}^n X_i$ grows at least as $\log n$ for any fixed $p$, and proves almost-sure escape to $\infty$.</p> http://mathoverflow.net/questions/60417/will-a-random-walk-on-0-inf-tend-to-infinity/60425#60425 Answer by camomille for Will a random walk on [0, inf) tend to infinity? camomille 2011-04-03T11:26:26Z 2011-04-03T11:26:26Z <p>The symmetric random walk $(X_k)$ on $\mathbb{Z}$ is recurrent. Therefore, with probability one, you will visit infinitely often $0$. The same is true for $(|X_k|)$, which is more ore less your random walk (the more or less depends on what happens exactly at the origin).</p> <p>In other words, with probability one, the $\liminf$ is $0$. The $\limsup$ behaviour is the subject of the law of the iterated logarithm. </p> http://mathoverflow.net/questions/60417/will-a-random-walk-on-0-inf-tend-to-infinity/60428#60428 Answer by Alekk for Will a random walk on [0, inf) tend to infinity? Alekk 2011-04-03T11:58:01Z 2011-04-03T11:58:01Z <p>As it has been said:</p> <ol> <li>if $p=\frac{1}{2}$ this is more or less the same thing as the absolute value of the standard symmetric random walk on $\mathbb{Z}$, wich is recurrent.</li> <li>if $p > \frac{1}{2}$, the law of large numbers immediately shows you that it tends to $+\infty$.</li> <li>if $p &lt; \frac{1}{2}$, you can even check the detailed balance equations and find the invariant distribution: the Markov chain is positive recurrent.</li> </ol>