Let's say I have a biased random walk over the integers in some interval [0, L] where the endpoints of the interval ('0' and 'L', respectively) are fully absorbing. The walker starts at some position x(i), and has a probability of taking a '+1' step and a '-1' step of 'p' & 'q', respectively. Here p + q = 1, there is no stationary step.

My question is: conditional on the walker eventually absorbing, specifically at one boundary, what is the probability that absorption will occur prior to some number of steps, 'M'?

Update - I would also be quite interested in tight lower-bound estimates!

  • $\begingroup$ conditional on the walker eventually absorbing at one of the boundaries We know for sure that absortion will happen eventually. Perhaps you mean conditioning on being absorbed at one particular boundary? $\endgroup$
    – leonbloy
    Jun 6 '11 at 3:44
  • $\begingroup$ @leonbloy, yes, that is what I meant... hopefully my question should be clearer with the rewrite! $\endgroup$
    – user8861
    Jun 6 '11 at 6:34

This addresses the first formulation of the question, asking for the probability of absorption at $0$ or $L$ before a given time, conditionally on absorption. See below for a solution to the second formulation of the question.

One can omit the conditioning by the event that one eventually hits one of the absorbing barriers, since this event happens with full probability. Now, an often fruitful approach of this kind of problem is to look for a quasi-stationary distribution.

In words, assume that a proportion $m(n)$ of particles is at site $n$ at time zero, for every $n$ between $1$ and $L-1$, and that all the particles start to move according to the specified dynamics. Particles disappear on hitting an absorbing barrier, otherwise they continue to move from site to site. Then our goal is to have a proportion $\alpha^tm(n)$ of particles on site $n$ at time $t$, for a suitable rate $a$. If $m$ is a probability distribution, this will yield $P_m(T\ge t)=\alpha^t$ where the subscript $m$ indicates that $P(X_0=n)=m(n)$ for every $n$ between $1$ and $L-1$.

The condition of quasi-stationarity with rate $\alpha$ reads as $m(0)=m(L)=0$ and, for every site $n$ between $1$ and $L-1$, $ \alpha m(n)=pm(n-1)+qm(n+1). $ The general solution of this linear system of equations is $m(n)=As^n+Bt^n$ for suitable values of $A$ and $B$, where $s$ and $t$ solve the characteristic equation $$ \alpha x=p+qx^2. $$ The condition that $m(0)=0$ yields $B=-A$. The condition that $m(L)=0$ yields $s^L=t^L$. This can only happen if the two roots $s$ and $t$ of the characteristic equation are conjugate complex numbers whose argument $u$ is a multiple of $\pi/L$. Hence, $s=r\mathrm{e}^{\mathrm{i}u}$ and $t=r\mathrm{e}^{-\mathrm{i}u}$ where $$ r^2=p/q,\qquad 2r\cos(u)=\alpha/q. $$ Then $m$ is proportional to the measure $m_\alpha$ defined, for every site $n$, by $$ m_\alpha(n)=r^n\sin(nu). $$ The condition that $m_\alpha(n)\ge0$ for every site $n$ implies that $Lu\le\pi$. Since $Lu$ must be a multiple of $\pi$, this forces $u=\pi/L$ and

$$ \alpha=\cos(\pi/L)\sqrt{4pq}. $$

As said at the beginning, the above proves that, for every time $t$, $$ \sum_{n=1}^{L-1}m_\alpha(n)P_n(T\ge t)=\alpha^t|m_\alpha|, $$ where $|m_\alpha|$ denotes the total mass of the measure $m_\alpha$. Thus, for every site $n$ and time $t$, $$ P_n(T\ge t)\le c_n\alpha^t,\qquad c_n=|m_\alpha|/m_\alpha(n). $$ In the other direction, one can show that, for every site $n$, there exists a positive $b_n$ such that, for every time $t$, $$ P_n(T\ge t)\ge b_n\alpha^t. $$ Finally, $P(T\ge t)\to0$ geometrically fast when $t\to+\infty$ with a known rate $\alpha$ of convergence. Hence, $$ P(T\le t)=1-\Theta(\alpha^t),\qquad \alpha=\cos(\pi/L)\sqrt{4pq}. $$ Note If $L=2$, $\alpha=0$ and one checks that $P_1(T\ge t)=0$ for every $t\ge2$. If $L=3$, $\alpha=\sqrt{pq}$ and one checks that $P_n(T\ge 2t+1)=(pq)^t$ for $n=1$ or $n=2$ and for every $t\ge0$.

This addresses the second formulation of the question, asking for the probability of absorption at $0$ before a given time, conditionally on absorption at $0$, and uses the solution above.

For every $n$, let $h(n)=P_n(T_0<T_L)$. Then $(h(n))$ is the unique solution of the linear system of equations $h(0)=1$, $h(L)=0$, and $h(n)=ph(n+1)+qh(n-1)$ for every site $n$ between $1$ and $L-1$. Let $P^0$ denote the probability $P$ conditioned by the event that the random walk hits $0$ (and as a consequence does not hit $L$). Under $P^0$, the random walk becomes the so-called Doob $h$-transform of the original random walk, in the sense that it is still a Markov chain, but with transition probabilities $$ P^0(X_{t+1}=n+1|X_t=n)=p^0_n=1-P^0(X_{t+1}=n-1|X_t=n), $$ where $$ p^0_n=ph(n+1)h(n)^{-1}. $$ As a consequence, under $P^0$, for every path $\gamma$ which starts from $\gamma(0)$, ends at $\gamma(T)$ and avoids $L$, the probability $P^0(\gamma)$ that the random walk follows $\gamma$ conditionally on $X_0=\gamma(0)$ is related to the equivalent probability $P(\gamma)$ under $P$ by the formula $$ P^0(\gamma)=P(\gamma)h(\gamma(T))h(\gamma(0))^{-1}. $$ Now, for every site $n$ between $1$ and $L-1$, $$ P^0_n(T_0\ge t)=\sum_\gamma P^0(\gamma)=\sum_\gamma P(\gamma)h(\gamma(T))h(n)^{-1}, $$ where the sum enumerates all the paths $\gamma$ of length $t$ which start from $n$ and end at a site between $0$ and $L-1$ (and, as a consequence, avoid $L$). That is, $$ P^0_n(T_0\ge t)=\sum_{k=0}^{L-1}P_n(T\ge t,X_t=k)h(k)h(n)^{-1}. $$ It happens that the sequence $(h(k))$ is nonincreasing hence $h(L-1)\le h(k)\le1$ for every $k$ between $0$ and $L-1$ and $$ P_n(T\ge t)h(L-1)h(n)^{-1}\le P^0_n(T_0\ge t)\le P_n(T\ge t)h(n)^{-1}. $$ We already know that $P_n(T\ge t)\to0$ geometrically fast when $t\to+\infty$ with rate $\alpha$, hence the same asymptotics holds for $P^0_n(T_0\ge t)$.

Note finally that, for every site $n$ between $0$ and $L$, $ h(n)=\displaystyle\frac{\left(p/q\right)^{L-n}-1}{\left(p/q\right)^L-1}, $ if $p\ne q$, and $h(n)=1-(n/L)$ otherwise, and that $$ P_n(T\ge t)h(L-1)\le P^0_n(T_0\ge t)\le P_n(T\ge t)h(L-1)^{-1}. $$

  • $\begingroup$ @Didier Piau, thanks for your characteristically fantastic and explanatory answers! I'm wondering though... I thought I stumbled on an exact solution to this problem years ago when I was looking through the literature for something unrelated. Was I most likely hallucinating? $\endgroup$
    – user8861
    Jun 6 '11 at 6:47
  • $\begingroup$ For a Brownian motion with drift, killed at a double barrier, the probability of surviving until a given time can be expressed as a series indexed by $\mathbb{Z}$ (but asymptotics are not so easy to deduce from this formula). For a random walk with drift starting from a single point and killed at a double barrier, I do not know. Which is why I find interesting this trick of choosing a suitable initial distribution. $\endgroup$
    – Did
    Jun 6 '11 at 9:12
  • $\begingroup$ Note that this answer does not take into account the OP's clarification about the conditioning... $\endgroup$
    – leonbloy
    Jun 6 '11 at 15:09
  • $\begingroup$ @Didier Piau, very nice answer! $\endgroup$
    – user8861
    Jun 6 '11 at 19:52
  • $\begingroup$ @Didier Piau, one quick question - you provided a theta bound in your original answer not assuming conditional absorption at '0', $1-\Theta(\alpha^t)$ - how close is this to a lower-bound? $\endgroup$
    – user8861
    Jun 6 '11 at 19:54
  1. The transition probabilities can be expressed a tridiagonal matrix.

  2. The left and right eigenvectors and eigenvalues can be written in terms of cosines and sines . This is unique to tridiagonal matrices and doesn't work for others.

  3. With this information, it is just basic operations to find the probabilities of of all of the entries at any starting position after any number of steps.

There are other ways to doing it. More information on a derivation : https://www.gwern.net/docs/statistics/1957-feller-anintroductiontoprobabilitytheoryanditsapplications.pdf

start at page 350


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.