5
$\begingroup$

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!

  • 0
    `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?2011-06-06
  • 0
    @leonbloy, yes, that is what I meant... hopefully my question should be clearer with the rewrite!2011-06-06

1 Answers 1

7

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

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

  • 0
    @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?2011-06-06
  • 0
    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.2011-06-06
  • 0
    Note that this answer does not take into account the OP's clarification about the conditioning...2011-06-06
  • 0
    @Didier Piau, very nice answer!2011-06-06
  • 0
    @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?2011-06-06
  • 0
    Not sure what you ask here, so let me try and if I go astray, do not hesitate to reformulate your question: Big-Theta notations mean that two sequences are of the exact same order. Here, the assertion that $P(T\le t)=1-\Theta(\alpha^t)$ is equivalent to the existence of two finite constants $A$ and $B$ such that $1-A\alpha^t\le P(T\le t)\le1-B\alpha^t$ for every $t$ large enough. You see that every Big-Theta assertion contains a lower bound **and** an upper bound. By contrast, Big-Oh assertions are one sided. Hope this helps.2011-06-06
  • 0
    @Didier Piau, thanks, I suppose I'm looking for a value for 'A', or Big-Omega[P(T<=t)]? Does that make sense?2011-06-06
  • 0
    @Didier Piau, if that's unfair to ask... I was hoping for a more intuitive understanding of what values of 'A' and 'B' would be reasonable, in practice, as a function of the size of 't'?2011-06-06
  • 0
    $A=c_n$. $ $ $ $2011-06-06
  • 0
    @Didier Piau, right, I see, thanks!2011-06-06