1
$\begingroup$

We are given a random walk on $\mathbb{Z}$, where $p_{i, i+1}= p < \frac{1}{2}$ and $p_{i,i-1}=1-p > \frac{1}{2}$, starting at $0$.

Now we have to compute the probability that we eventually reach $k \in \mathbb{N}$.

How could one solve that?

For the recurrence equation $d_i=p d_{i+1} + (1-p) d_{i-1}$ I have no base cases (except $d_k=1$) and computing $P[\text{eventually reaching k}]=\sum_{i=1}^{\infty} P[\text{ reaching k in step i}]$ seems to be very nasty.

So do you have a hint how to solve this?

$\endgroup$
1
$\begingroup$

Consider some nonnegative integers $i$ and $j$. To reach $i+j$ starting from $0$, one must first reach $i$ starting from $0$ then reach $i+j$ starting from $i$.

The probability of the first event is $d_i$. By the Markov property and the invariance of the dynamics by the translations of $\mathbb Z$, the property of the second event conditionally on the first is $d_j$. Thus $d_{i+j}=d_id_j$ for every nonnegative integers $i$ and $j$, with $d_0=1$.

Using that $d_i\lt1$ for every $i\geqslant1$ since the random walk has a negative drift, and the identity in your post, this suffices to show that $d_i=r^i$ for every $i\geqslant1$, where $r=$ $____$.

$\endgroup$
  • $\begingroup$ Thank you for your answer. So I tried to understand what you've written and somehow it makes sense, but I would never be able to come up with such an idea. What I tried to do: $d_1= p d_2 + (1-p) d_0$ gives $r=pr^2+(1-p)$, which gives as solution $r_1=\frac{1-p}{p}$ or $r_2=1$. Clearly $r$ should not be $1$, hence $d_i=\left(\frac{1-p}{p}\right)^i$ is the correct solution? $\endgroup$ – user136457 Nov 26 '14 at 8:52
  • 1
    $\begingroup$ No, and it cannot be since $(1-p)/p\gt1$. This is because the identity is actually $d_i=p d_{i-1} + (1-p) d_{i+1}$, not what you wrote. $\endgroup$ – Did Nov 26 '14 at 8:54
  • $\begingroup$ I see that it is wrong, I didn't pay attention here. So you used another definition of $d_i$, you use $d_i:=P[\text{reaching i}]$ and what I used is $d_i:=P[\text{reaching k when starting from i}]$, so I have $d_k=1$, and you have with your definition $d_k \neq 1$. So what confused me before is that I mixed these two definitions up (so I should have been more precise what I mean with $d_i$ and then you should have possibly used another notation for this quantity). But then, it seems to make sense, then we actually have $r=1$ or $r=\frac{p}{1-p}$, and $d_i = \left(\frac{p}{1-p}\right)^i$? $\endgroup$ – user136457 Nov 26 '14 at 9:09
  • $\begingroup$ Yes. $ $ $ $ $ $ $\endgroup$ – Did Nov 26 '14 at 9:12
  • 1
    $\begingroup$ That we have visited $i$ "before" is irrelevant since $d_{i+1}$ is concerned about what happens "after". $\endgroup$ – Did Nov 30 '14 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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