# Simple Markov Chain: Random Walk on $\mathbb{Z}$

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?

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=$ $____$.
• 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? – user136457 Nov 26 '14 at 8:52
• 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. – Did Nov 26 '14 at 8:54
• 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$? – user136457 Nov 26 '14 at 9:09
• Yes.    – Did Nov 26 '14 at 9:12
• That we have visited $i$ "before" is irrelevant since $d_{i+1}$ is concerned about what happens "after". – Did Nov 30 '14 at 15:23