Problem:
You are standing at the position $0$ on the line of natural numbers $0, 1, 2, …, n$. From this position you go to $1$ with probability $1$,
but from any other position $i$ you go to $i+1$ with probability $p$ and respectively to $i-1$ with probability $1-p$. What is the expected number of steps to go from 0 to n?
Just to be clear. There is no way you can end up on the negative number. And once you reach $n$ the game stops, so you can not end up on any number bigger than $n$.
Here is my approach to tackle this problem:
Let $N_i$ is the expected number of steps to reach $n$ from a position $i$.
It is obvious that $N_n = 0$. Also $N_0 = 1 + N_1$. And if we select any number $i$ from $1$ to $n-1$, then $N_i = (1 – p) \cdot N_{i-1} + p \cdot N_{i+1} = 1 + (1-p) \cdot N_{i-1} + p \cdot N_{i+1}$.
Now I am trying to simplify things having these three equations:
$$N_0 = 1 + N_1\\
N_i = 1 + (1-p) \cdot N_{i-1} + p \cdot N_{i+1}\\
N_n = 0$$
Approach 1
Putting $i = 1$ in equation (2) I found that $N_1 = 2/p – 1 + N_2$, which I later put in (1) to get $N_0 = 2/p + N_2$
Doing the same with $i = 2$ I got $N_2 = 1 – 2/p + 2/p^2 + N_3$ and $N_0 = 1 + 2/p^2 + N_3$.
Just one more step with $i = 3$ gives me $N_3 = N_4 + 4/p – 4/p^2 + 2/p^3 – 1$ and $N_0 = 4/p – 2/p^2 + 2/p^3 + N_4$
I was doing all this in hope of finding some relationship which would allow me to guess what will be the relationship for the last or one before last step. But I fail to see any and therefore I gave up.
Approach 2
I noticed that:
$N_0 – N_1 = 1$ and $N_{i-1} – N_i = 1 + (1 – p) \cdot (N_{i-2} – N_i)$
Here if I will sum the left side, I will get $N_0 – N_n = N_0$ and this gave me hope that I can get some closed form expression if I will add the right side. But when I add them up I got $n + (1 – p)(N_0 + N_1 – N_{n-1} – N_{n})$. This gave me $N_0 = \frac{n + (N_1 – N_{n-1})(1-p)}{p}$ which leads me nowhere because of $N_1$ and $N_{n-1}$.
Approach 3 (similar to approach 2, but I expand the first element, not the second). I will not write it completely, not because I have not thought about, but because I value your time and I think that
the post is already too long.
So $N_0 – N_1 = 1$ and $N_i – N_{i+1} = -1 + p (N_i – N_{i+2})$. After the same summation idea as in approach 2 I ended up with $N_1$, $N_2$ and $N_{n-1}$ elements.
After this I gave up completely. Here I am not really sure that my starting idea
Let $N_i$ is the expected number of steps to reach $n$ from a position
$i$.
is correct or whether the close formula for expected value exist. So how should I approach this problem?
P.S. I know that for $p = 0.5$ (go left and right with equal probability) the close formula exists and expected number of steps one need to take from $0$ to $n$ is $n^2$.
Best Answer
Yes your recurrence is right, i.e., $$N_i = 1 + (1-p)N_{i-1} + pN_{i+1}$$ with $N_0 = 1+N_1$ and $N_n = 0$. This can be rearranged to give $$p(N_{i+1}-N_i) - (1-p)(N_i-N_{i-1}) = -1$$ with $N_1 - N_0 = -1$ and $N_n = 0$. Setting $v_i = N_{i+1} - N_{i}$, we obtain the equations to be $$pv_i - (1-p)v_{i-1} = -1$$ with $v_0 = -1$ and $N_n=0$. Setting $v_i = u_i + k$, we obtain $$pu_i - (1-p)u_{i-1} + k(2p-1) = -1$$ Hence, if set $k = -\dfrac1{2p-1}$, we obtain the recurrence $$u_i = \dfrac{1-p}p u_{i-1} \implies u_i = \left(\dfrac{1-p}p\right)^iu_0 = \left(\dfrac{1-p}p\right)^i \cdot \dfrac{2-2p}{2p-1}$$ Hence, $$v_i = \left(\dfrac{1-p}p\right)^i \cdot \dfrac{2-2p}{2p-1} - \dfrac1{2p-1}$$ Rewriting this in terms of $N_i$, we obtain $$N_{i+1} - N_{i} = \left(\dfrac{1-p}p\right)^i \cdot \dfrac{2-2p}{2p-1} - \dfrac1{2p-1} \text{ with }N_n = 0$$ Hence, summing from $i = {j}$ to $i=n-1$, we obtain $$N_n - N_{j} = \sum_{i=j}^{n-1}\left(\dfrac{1-p}p\right)^i \cdot \dfrac{2-2p}{2p-1} - \sum_{i=j}^{n-1}\dfrac1{2p-1}$$ Since $N_n = 0$, we obtain \begin{align} N_j & = \dfrac{n-j}{2p-1} + \dfrac{2(1-p)}{1-2p} \sum_{i=j}^{n-1} \left(\dfrac{1-p}p\right)^i = \dfrac{n-j}{2p-1} + \dfrac{2(1-p)}{1-2p} \left(\dfrac{1-p}p\right)^{j}\sum_{i=0}^{n-j-1} \left(\dfrac{1-p}p\right)^i\\ & = \dfrac{n-j}{2p-1} + \dfrac{2(1-p)}{1-2p} \left(\dfrac{1-p}p\right)^{j} \cdot \dfrac{\left(\dfrac{1-p}p\right)^{n-j}-1}{\dfrac{1-p}p-1}\\ & = \dfrac{n-j}{2p-1} + \dfrac{2p(1-p)}{(1-2p)^2} \left(\dfrac{1-p}p\right)^{j} \cdot \left(\left(\dfrac{1-p}p\right)^{n-j}-1 \right) \end{align}
Hence, $$N_0 = \dfrac{n}{2p-1} + \dfrac{2p(1-p)}{(1-2p)^2}\left(\left(\dfrac{1-p}p\right)^n-1\right)$$