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.

As time goes to infinity, will your position tend to infinity? If not, to what finite value does it converge?

Edit: To be a bit more precise, what is the limit of the average position as time goes to infinity?

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 < 0.5 is what I'm after)

What is the probability of being at position x after an arbitrary amount of steps?

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.



closed as too localized by Yemon Choi, fedja, Peter Shor, Nate Eldredge, Pete L. Clark Apr 3 '11 at 15:12

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Random walks with barrier conditions ought to be covered in probability textbooks. My memory is hazy here, but have you tried Feller Volume I, or maybe even Grimmett and Stirzaker's book. $\endgroup$ – Yemon Choi Apr 3 '11 at 8:54
  • 6
    $\begingroup$ Maybe you should ask this on math.stackexchange.com; there are plenty of people on this website who can give you good answers, but they all seem to be ignoring your question because it's too elementary to belong on this website, and so it turns out that you're not getting that many good answers. To answer one of your questions, $$\lim_{n\rightarrow \infty} \mathrm{Pr}(\mathrm{at\ position\ }x) \cdot \sqrt{n}\rightarrow c$$ for some constant $c$, where $n$ is the number of steps taken. $\endgroup$ – Peter Shor Apr 3 '11 at 13:17

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

In other words, with probability one, the $\liminf$ is $0$. The $\limsup$ behaviour is the subject of the law of the iterated logarithm.


As it has been said:

  1. 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.
  2. if $p > \frac{1}{2}$, the law of large numbers immediately shows you that it tends to $+\infty$.
  3. if $p < \frac{1}{2}$, you can even check the detailed balance equations and find the invariant distribution: the Markov chain is positive recurrent.

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.

It is well-known 1 that $E R_n\sim\log_{1/p}((1-p)n)$ plus small correction terms (the variance is $O(1)$).

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

  • 1
    $\begingroup$ Why "This means that $S_n$"... ? $\endgroup$ – camomille Apr 3 '11 at 11:33
  • $\begingroup$ With high probability, after $n$ steps you'll see $O(\log n)$ contiguous heads, which will advance you $O(\log n)$ steps to the right. $\endgroup$ – Aryeh Kontorovich Apr 3 '11 at 11:45
  • 1
    $\begingroup$ Maybe I do not understand what you mean by "escape to \infty". If you mean that the walker goes arbitrarely far the the right with probability one this is obvious. If you mean that the walker tends to infinity with probability one this is false (see my answer below). Actually, many thinks are known on such a walk, this is really very standard (and maybe this should not be discussed here actually). $\endgroup$ – camomille Apr 3 '11 at 11:49
  • $\begingroup$ I wasn't being precise. The random walk visits 0 and every other natural number infinitely many times, as has been said here. $\endgroup$ – Aryeh Kontorovich Apr 3 '11 at 12:22
  • $\begingroup$ All right, but your argument is a sophisticated way to prove that the walker can reach any point (this is just irreducibility). $\endgroup$ – camomille Apr 3 '11 at 12:41

For any $p>0$ and any finite $N$, with probability one, eventually your random walk will exceed $N$.

  • $\begingroup$ True, but that's not quite what I'm after. $\endgroup$ – wjomlex Apr 3 '11 at 8:57
  • 3
    $\begingroup$ But that's not the same as saying one "almost surely tends to +infinity" ... $\endgroup$ – Yemon Choi Apr 3 '11 at 8:57
  • $\begingroup$ I'll elaborate. You are flipping a biased coin, with probability $p$ of heads. With probability 1, you will at some point observe a sequence of $p^N$ consecutive heads, which will necessarily take you to the right of $N$. $\endgroup$ – Aryeh Kontorovich Apr 3 '11 at 8:59
  • $\begingroup$ We understand what you mean, it's just that you're answering a different question :) $\endgroup$ – wjomlex Apr 3 '11 at 9:00
  • $\begingroup$ True, my answer does not imply almost-sure escape to infinity. Must think some more... $\endgroup$ – Aryeh Kontorovich Apr 3 '11 at 9:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.