Probability of simple random walk ever reaching a point

1,287

Let $q=1-p$.

Method 1:

Let $r_k$ be the probability that $S_n$ ever reaches $k$. Then also $r_k$ is the probability that $S_n$ with $S_0=c$ ever reaches $k+c$. Consequently:

$$r_k=pr_{k-1}+qr_{k+1}$$

so that $r_k=c_1 \left ( \frac{1 + \sqrt{1-4pq}}{2q} \right )^k+c_2 \left ( \frac{1-\sqrt{1-4pq}}{2q} \right )^k$, from the usual theory of linear recurrence relations with constant coefficients.

In order to go to zero as $k \to \infty$, the first term must be zero. And certainly $r_0=1$, so $c_2=1$, and now we are done.

Method 2:

Let $r$ be the probability that $S_n$ ever net-moves to the right by $1$. Then $r=p+qr^2$: either the process immediately moves right, or else it initially moves left and then net-moves right at least twice. Thus $r=\frac{1-\sqrt{1-4pq}}{2q}$. Then by the same logic that got us $r^2$, we conclude that the probability to ever net-move to the right by $M$ steps is $r^M$.

As a side remark about simplification, $\sqrt{1-4pq}=|2p-1|=1-2p$ since $p<1/2$, so in fact $\frac{1-\sqrt{1-4pq}}{2q}=\frac{p}{q}$ and $\frac{1+\sqrt{1-4pq}}{2q}=1$. You could've figured this out without using the quadratic formula on $qx^2+p=x$ like I did. Note the coefficients sum to zero (after moving them all to one side), so $1$ is a root, then note that the product of the roots is $p/q$, so the other one is $p/q$.

Share:
1,287
oliverjones
Author by

oliverjones

Updated on August 01, 2022

Comments

  • oliverjones
    oliverjones over 1 year

    Let $S_n= \sum_{i =1}^n X_i$ where $P(X_i = 1) = p < \frac{1}{2}; P(X_i= -1) = 1-p$ Assume $S_0 = 0$ and $M > 0$ Find the probability that $S_n$ ever reaches $M$.

    My first question is am I calculating $P(S_n = M)$ or $P(S_n \ge M)$?

    If the former it should be $P(S_n = M) =$ $ {n \choose (n+M)/2}p^{(n+M)/2}(1-p)^{(n-M)/2}$

    But seems that maybe it is the latter I am after.

    • Ian
      Ian about 3 years
      You are calculating $P(\exists n : S_n=M)$, which because of the structure of the problem is the same as $P(\exists n: S_n \geq M)$.
    • oliverjones
      oliverjones about 3 years
      @Ian is this then something such as $\sum_{n =1}^{\infty} P(S_n = M \mid S_{n-1} = M-1 )$
    • Ian
      Ian about 3 years
      No, you might think it would be $\sum_{n=1}^\infty P(S_n=M)$ but that double counts paths that visit $M$ more than once.
    • oliverjones
      oliverjones about 3 years
      @Ian what about in terms of the maximum? I recall seeing a formula about the maximum somewhere.
    • Ian
      Ian about 3 years
      There's an easier way to do it, without getting the general probability distribution of the maximum after a finite number of steps.
    • oliverjones
      oliverjones about 3 years
      Hm the only other thing I can think of is the hitting time probability which I recall the formula for but I don't recall how to derive it immediately.
    • Ian
      Ian about 3 years
      The main idea is the total probability formula. Consider just $M=1$ for intuition. $P(\exists n : S_n=1 \mid S_0=0)=p P(\exists n : S_n=1 \mid S_0=0,S_1=1) + (1-p) P(\exists n : S_n=1 \mid S_0=0,S_1=-1)$. Now the first term is obviously just $p$. What's the second conditional probability? You can express it in terms of the desired quantity to get an equation for the desired quantity and then solve the resulting equation.
    • oliverjones
      oliverjones about 3 years
      The second conditional probability will be the same as the initial w.p. $p$ and w.p. (1-p) will be a similar to itself depending on if $S_2 = 0$ or $-2$, resp. I believe that is what would occur, so I see a bit of a pattern showing but it that must be slightly off because that pattern will continue repeating.
    • Ian
      Ian about 3 years
      So you can go one of two ways: either you can go by recursion or you can make an "intuitive leap". The recursion way is to say that the probability $r_n$ to ever arrive at a location $n$ steps to the right of where you started satisfies $r_n=p r_{n-1} + (1-p) r_{n+1}$ and solve that recursion.
    • Ian
      Ian about 3 years
      (Cont.) The "intuitive leap" way is to say that the probability $r_n$ to arrive at a location $n$ steps to the right of where you started must be $r^n$ where $r$ is the probability to ever arrive at a location $1$ step to the right of where you started; this is not so obvious, but you can prove it using the Markov property.