1
$\begingroup$

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.

Thanks!

$\endgroup$
2
  • $\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, 2011 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, 2011 at 13:17

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Why "This means that $S_n$"... ? $\endgroup$
    – camomille
    Apr 3, 2011 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$ Apr 3, 2011 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, 2011 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$ Apr 3, 2011 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, 2011 at 12:41
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ True, but that's not quite what I'm after. $\endgroup$
    – wjomlex
    Apr 3, 2011 at 8:57
  • 3
    $\begingroup$ But that's not the same as saying one "almost surely tends to +infinity" ... $\endgroup$
    – Yemon Choi
    Apr 3, 2011 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$ Apr 3, 2011 at 8:59
  • $\begingroup$ We understand what you mean, it's just that you're answering a different question :) $\endgroup$
    – wjomlex
    Apr 3, 2011 at 9:00
  • $\begingroup$ True, my answer does not imply almost-sure escape to infinity. Must think some more... $\endgroup$ Apr 3, 2011 at 9:00

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