Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
If $r\gt0$ there are simple exponential upper and lower bounds. Why do you say the expectation probably isn't exponential? –  Douglas Zare Mar 27 '13 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)}.$$

share|improve this answer
See also mathematica-journal.com/2012/03/… –  Douglas Zare Mar 28 '13 at 8:16
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. –  Hans Dec 11 '13 at 2:18
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. –  Hans Dec 11 '13 at 2:50
@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. –  Douglas Zare Dec 11 '13 at 7:05
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. –  Hans Dec 11 '13 at 16:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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