2
$\begingroup$

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!

$\endgroup$
13
  • $\begingroup$ 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) ? $\endgroup$
    – Jean Marie
    Feb 28, 2016 at 5:48
  • $\begingroup$ 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. $\endgroup$
    – Raj
    Feb 28, 2016 at 5:54
  • $\begingroup$ @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$. $\endgroup$
    – zhoraster
    Feb 28, 2016 at 9:21
  • 2
    $\begingroup$ 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$. $\endgroup$
    – zhoraster
    Feb 28, 2016 at 9:47
  • 1
    $\begingroup$ @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)$$ $\endgroup$
    – Mick A
    Feb 28, 2016 at 14:20

1 Answer 1

0
$\begingroup$

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}

$\endgroup$

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.