<s>[INST] Random walk (Exercise 3.11.39 from Grimmett and Stirzaker) A particle performs a random walk on the non-negative integers as follows. When at the point $n\ (> 0)$ its next position is uniformly distributed on the set $\{0, 1, 2, \ldots, n + 1\}$. When it hits $0$ for the first time, it is absorbed. Suppose it starts at the point $a$.
(a) Find the probability that its position never exceeds $a$, and prove that, with probability $1$, it is absorbed ultimately.
(b) Find the probability that the final step of the walk is from $1$ to $0$ when $a = 1$.
(c) Find the expected number of steps taken before absorption when $a = 1$.
I completed part (a) and obtained the probability of not exceeding $a$ to be
$$
p = \frac{(a + 1)!}{1 + \sum_{n=1}^{a + 1} n!}.
$$
Now I am stuck on part (b). Here is what I have so far:
Let $p_n$ be the probability that the final step of the walk is from $1$ to $0$. Then
$$
p_n = \frac{1}{n + 2}(p_{n + 1} + p_{n - 1} + \cdots + p_1),
$$
and,
$$
p_{n - 1} = \frac{1}{n + 1}(p_n + p_{n - 1} + \cdots + p_1).
$$
From these two equations we obtain
\begin{align}
p_{n + 1} - p_n &= (n + 1)(p_n - p_{n - 1}), \\
\implies p_{n + 1} - p_n &= \frac{1}{2}(n + 1)!(p_2 - p_1).
\end{align}
Summing the above expression for $p_{n + 1} - p_n$ from $2$ to $n$ gives
$$
p_{n + 1} - p_2 = \frac{1}{2}(p_2 - p_1) \sum_{i = 3}^{n + 1} i!
$$
But we also know that
$$
p_1 = \frac{1}{3}(p_2 + p_1 + 1).
$$
Therefore $p_2 = 2 p_1 - 1$. Substituting for $p_2$ in the expression for $p_{n + 1} - p_2$ we obtain
$$
p_{n + 1} = p_1 + \frac{1}{2}(p_1 - 1) \sum_{i = 2}^{n + 1} i!
$$
Now I am stuck because the last expression does not make sense. This is because for all $p_1 \neq 1$, $p_n \rightarrow -\infty$ as $n \rightarrow \infty$. Where have I gone wrong? Please can you provide a hint on how to approach this problem in the correct way?
Edit (2016/02/28)
With help from the comments of @zhoraster and @mick-a below, the expression for $p_{n + 1}$ actually turns out to be
$$
p_{n + 1} = 5p_1 - 3 + \frac{3 p_1 - 2}{6}\sum_{i = 3}^n (i + 1)!
$$
For $p_{n + 1}$ to be a valid probability the coefficient of the factorial sum on the right hand side must be equal to $0$ as $n \rightarrow \infty$. This implies that $p_1 = 2/3$ and hence that $p_n = 5 \times 2/3 - 3 = 1/3$ for $n \geq 2$. I would never have expected that!
 [/INST] For completeness, here is the solution to part(c):
Assuming that a transition from $i$ to $j$ is always a step of length 1 (regardless of the values of $i$ and $j$) we can write the expected number of steps, $\lambda_n$, given that the particle starts at $n \geq 1$ as,
\begin{align}
\lambda_n &= \frac{1}{n + 2}((\lambda_{n + 1} + 1) + (\lambda_n + 1) + \cdots + (\lambda_1 + 1) + 1), \\
&= \frac{1}{n + 2}(\lambda_1 + \lambda_2 + \cdots + \lambda_{n + 1}) + 1.
\end{align}
And for $n \geq 2$,
$$
\lambda_{n - 1}  = \frac{1}{n + 1}(\lambda_1 + \lambda_2 + \cdots + \lambda_n) + 1.
$$
Subtracting these two equations gives for $n \geq 2$,
$$
(n + 1)(\lambda_n - \lambda_{n + 1}) = \lambda_{n + 1} - \lambda_n + 1.
$$
The next step is the crucial step which allows the recurrence relation to be solved (and I have to admit that I needed to peek into the solutions manual for this hint). Let $v_{n + 1}  = (\lambda_{n + 1} - \lambda_n) / (n + 1)!$. Then,
\begin{align}
v_{n + 1} - v_n &= \frac{\lambda_{n + 1} - \lambda_n}{(n + 1)!} - \frac{\lambda_n - \lambda_{n - 1}}{n!}, \\
&= -\frac{1}{(n + 1)!}.
\end{align}
Adding $v_{n + 1} - v_n$ from $n = 2$ to $\infty$ gives,
\begin{align}
-v_2 &= -\sum_{i = 3}^{\infty} \frac{1}{i!} \\
\implies v_2 &= -\frac{1}{0!} - \frac{1}{1!} - \frac{1}{2!} + \sum_{i = 0}^{\infty} \frac{1}{i!} \\
\implies v_2 &= -\frac{5}{2} + e.
\end{align}
But $v_2 = \frac{1}{2!}(\lambda_2 - \lambda_1)$ and $\lambda_1 = \frac{1}{3}(\lambda_1 + \lambda_2 + 3)$. Solving for $\lambda_2$ gives $\lambda_2 = 2 \lambda_1 - 3$. Therefore,
\begin{align}
v_2 = \frac{\lambda_2 - \lambda_1}{2} &= -\frac{5}{2} + e \\
\implies \frac{2 \lambda_1 - 3 - \lambda_1}{2} &= -\frac{5}{2} + e \\
\implies \lambda_1 &= 2 e - 2.
\end{align}
</s>