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...

  • 3
    $\begingroup$ If $r\gt0$ there are simple exponential upper and lower bounds. Why do you say the expectation probably isn't exponential? $\endgroup$ Mar 27, 2013 at 11:48

1 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)}.$$

  • $\begingroup$ See also mathematica-journal.com/2012/03/… $\endgroup$ Mar 28, 2013 at 8:16
  • $\begingroup$ You have never defined death. The OP certainly has not defined it. The recursion equation of a[k] seems to suggest that you consider jumping back to k=0 makes a[0], presumably the probability of reaching either -1 or 1, zero. That is wrong. $\endgroup$
    – Hans
    Dec 11, 2013 at 2:18
  • $\begingroup$ The correct recursion for a is: a[k] = p a[k+1]+q a[k-1]+r a[0]. One can solve it with a generating function. $\endgroup$
    – Hans
    Dec 11, 2013 at 2:50
  • $\begingroup$ @Hansen: Death means jumping back to the start. I computed the probability that you make it to the boundary without dying, and the expected number of steps before you die or restart. If you calculate the recurrence you suggest, that's the probability of making it to the boundary at some point, which is $1$ when the system is not degenerate, hence not an interesting thing to compute. That $1$ is not what you need to compute the expected exit time from the expected value of the steps to reach the boundary or restart. $\endgroup$ Dec 11, 2013 at 7:05
  • $\begingroup$ If that is how you meant "death" to be, you should have stated it explicitly in your answer. Are you letting the particle disappear or die once it jumps back to the starting point? That is not what the original question asks. The original question stipulates that the point restarts once it comes back to the starting point, and it asks for the expected time to reach the boundary (one of the two barriers) rather than the question you modifies to which is the expected time to reach the boundary OR the starting point. So your answer does not answer the original question. $\endgroup$
    – Hans
    Dec 11, 2013 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.