# 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!

• What is the kind of answer provided by "One Thousand Exercises in Probability" of Grimmett and Stiirzacker (I imagine they have given at least hints) ? Feb 28, 2016 at 5:48
• I am resisting the temptation to look at the answer in the book for now. I feel like if I could see where the mistake in the above argument is then I could find the correct solution.
– Raj
Feb 28, 2016 at 5:54
• @A.S., I think $n$ is not fixed. So this is not a random walk, but rather a Markov chain with transition probabilities $p_{ij} = 1/(i+2)$ for $i\ge 1$, $j=0,1,\dots,i+1$; $p_{00} = 1$. Feb 28, 2016 at 9:21
• Concerning (b). Assume that your first step is up. Then the probability that we hit $1$ before $0$ is $1/2$ thanks to the symmetry (we take for granted that we reach one of this numbers almost surely). Then the probability $q$ you are interested in solves $q = \frac13 + q\frac13 + \frac12\cdot q\cdot \frac13$ whence $q=\frac23$. Feb 28, 2016 at 9:47
• @zhoraster 's method is good and clever. Raj, your first equation for $p_n$ is only valid for $n\geq 2$ and the second equation for $p_{n-1}$ is then only valid for $n\geq 3$. This means your relation only reduces to $$\implies p_{n+1}-p_n=\dfrac{1}{6}(n+1)!(p_3-p_2)$$ Feb 28, 2016 at 14:20

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}