1
$\begingroup$

Suppose we start at State $1$, directly to the right of a State $0$. What's the probability that we ever get to State $0$, if we take n steps to the right with probability p, 1 step to the left with probability q, and stay forever at State i (the current state) with probability r.

I know how to construct the solutions to this question but I don't know the why. I would appreciate a basic, intuitive, and logical way to get these equations.

1 Answers 1

2

Let $P(n)$ be the probability that you get to $0$ from $n$. If you are at $k$ (as long as $k \gt 0$), you go to $k-1$ with probability $q$, to $k+n$ with probability $p$ and get frozen with probability $r=1-p-q$ Then write the recurrence $P(k)=pP(k+n)+qP(k-1)$ because you either go left (probability $q$) to $k-1$ or go right $n$ steps (probability $p$) to $k+n$ and the chance of success in each direction is the product of the chance you went that way times the chance you succeed when you get there.

  • 0
    great explanation thank you, but your p and q are flipped in the second sentence.2012-09-25
  • 0
    I wonder how one can set up a recursion where P(k) is expressed in terms of P(k) terms to some power (this is what I've seen so far in problems where one starts directly next to the absorbing state). e.g., P(2) = P(1)^22012-09-25
  • 0
    @WuschelbeutelKartoffelhuhn: p vs q fixed, two places. You would have $P(2)=P(1)^2$ in this walk if $p=0$, because starting from $2$ you have to move left twice in succession to get to $0$, but I don't think that is what you are asking.2012-09-25