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!
Best Answer
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
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}. $$