Hitting time probability in a Random Walk with possibility to die.

Question

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. The walker starts moving from $x=0$ at time $t=0$. Two barriers are located in $x=n$ and $x=-n$.

Let's call $\tau (n)$ the first time the random walk hits one of the two barriers. Is there a way to determine how does $E[ \tau ] (n)$, (i.e. the expected time the walker hits one of the two barriers) depend on $n$?

I would be happy if for some values of the parameters $p$, $q$, $r$, the expectation $E[ \tau ] (n)$ grows exponentially with $n$, but probably it's not like this...

Answer 1

First, let me elaborate on my comment. If $X$ occurs with probability $\rho$, then the expected waiting time before you first see a streak of length $\ell$ $X$s in a row in independent trials is exponential in $\ell$, $\frac{\rho^{-\ell}-1}{1-\rho}$. If you get $2n-1$ right steps in a row, then you must have hit the barrier, which gives an exponential upper bound for the expected first hitting time, $\frac{p^{1-2n}-1}{q+r}$. On the other hand, to reach a barrier, you need a streak of at least $n$ non-deaths. Again, the waiting time before you first see such a streak is exponential for $r\gt 0$, $\frac{(p+q)^{-n}-1}{r}$. If $q=0$ or $p=0$, the lower bound is sharp.

Imagine we release a particle at $0$ once, and watch it until it reaches a barrier or dies. Let the average number of steps it takes be $s$, and let the probability that it dies be $d$. Then the expected number of steps before some particle hits a barrier is $s(1+d+d^2+...) = \frac{s}{1-d}$. Both $s$ and $d$ can be calculated analytically, but I think it's easier to let Mathematica do it. Here are Mathematica commands which find them:

ProbReachesBarrier[k_] := Evaluate[a[k] /. 
    RSolve[{a[k] == p a[k + 1] + q a[k - 1], a[n] == 1, a[-n] == 1}, 
           a[k], k][[1]] ]
ProbDies = Simplify[1 - ProbReachesBarrier[0]]

Let $\alpha = \frac{1+\sqrt{1-4pq}}{p}, \beta = \frac{1-\sqrt{1-4pq}}{p}$.

$$d = - \frac{(2^n-\alpha^n)(2^n-\beta^n)}{2^n(\alpha^n + \beta^n)}$$

ESteps[k_] := Evaluate[b[k] /. 
      RSolve[{b[k] == 1 + p b[k + 1] + q b[k - 1], b[n] == 0, b[-n] == 0}, 
             b[k], k][[1]] ]
s = Simplify[ESteps[0]]

$$ s = - \frac{(2^n - \alpha^n)(2^n-\beta^n)}{r 2^n (\alpha^n + \beta^n)} = \frac{d}{r}$$

$$\frac{s}{1-d} = - \frac{(2^n-\alpha^n)(2^n-\beta^n)}{r (4^n + \alpha^n \beta^n)}.$$