Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

Question

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I think about the problem?

Answer 1

How should I think about the problem?

I would think about the problem by considering a simpler problem and then considering how to adapt the solution to the simpler problem to the original problem.

I would start off by using a known result for the position $X_n$ after $n$ steps of a random walk beginning at $0$, without an absorbing barrier. With $s_-$ = number of steps to left, $s_+$ = number of steps to right, and $n$ = total number of steps: $$\begin{eqnarray*} X_n &=& s_+ - s_-\\ n &=& s_- + s_+ \\ X_n &=& 2s_+ - n \end{eqnarray*}$$

The probability of $i$ steps to the right, $\rm{Pr}(s_+ = i)$, in $n$ steps, is given by $$ \rm{Pr}(s_+ = i) = c(i,n) \; p^i (1-p)^{n-i},$$ where $p$ is the probability of a step to the right, and $c(i,n)$ is the number of $i$ positive steps in $n$ total steps. Clearly in this simple case: $$ c(i,n) = \left( \array{n\\i} \right) = \frac{n!}{i!(n-i)!}$$ i.e. $s_+$ follows the Binomial distribution $$ s_+ \sim B(n, p) $$

In general, in the case without an absorbing barrier, $$\rm{Pr}(X_n=i) = c((n+i)/2,n) \; p^{(n+i)/2}q^{n-(n-i)/2},$$ with $c$ defined as above, and $i=0,\pm2\ldots \pm n$ if $n$ even, and $i=\pm1,\pm3\ldots\pm n$ if $n$ odd.

To get an intuition for how this works, consider the case with a starting position $k=1$, number of steps $n=6$. Note only certain positions are possible: in this case after 6 steps the only possible end positions starting from 1 are $-5$, $-3$, $-1$, $1$, $3$, $5$, and $7$.

Consider $k=1, n=6$, and a target $m=3$, Here, $m-k = 2$ and we want the probability $\rm{Pr}(X_6=2)$. Solving $2 = 2s_+ - 6$ gives $s_+ 4$, i.e. we need 4 steps to the right -- and 2 steps to the left -- in any order. $$ P(X_6=2) = P(s_+=4) = \left( \array{6\\4} \right)p^4(1-p)^2 = \frac{6!}{4!2!}p^4(1-p)^2 = 15p^4(1-p)^2 $$

These 15 combinations are

--++++
-+-+++
-++-++
-+++-+
-++++-
+--+++
+-+-++
+-++-+
+-+++-
++--++
++-+-+
++-++-
+++--+
+++-+-
++++--

But what if there is an absorbing barrier at $0$? In this case, we still must have 4 steps to the right and 2 steps to the left, but some combinations of steps aren't valid. These combinations are those that touch the origin, I have marked these combinations with a *, below.

--++++ *
-+-+++ *
-++-++ *
-+++-+ *
-++++- *
+--+++ *
+-+-++
+-++-+
+-+++-
++--++
++-+-+
++-++-
+++--+
+++-+-
++++--

In this case in the modified problem with an absorbing barrier, $c(i,n) = 15 - 6 = 9$

$$ P(X_6=2) = (15 - 6)p^4(1-p)^2 = 9p^4(1-p)^2$$

So in my opinion you need to find some way of determining $c(i,n)$ by calculating the number of invalid combinations and subtracting from $ \left( \array{n\\i} \right) $, or calculating $c(i,n)$ directly.

Answer 2

Depends on the step size. for symmetric unit steps, the problem is still hard to solve but closed form answers exist.

You have a problem in which there are two conditions, the absorbing barrier at $0$ and the stopping point at $m$. This can be modeled as a system of equations like this:

$xr_1^{0}+yr_2^{0}=0$

$xr_1^{m}+yr_2^{m}=1$

in which $r_1$, $r_2$ are the roots of the characteristic function, $k^2-2k+z=0$,

solving for x,y gives the generating function for exact probabilities of hitting m within an arbitrary number of steps as some function of z conditional on not hitting zero:

$xr_1^{s}+yr_2^{s}=f(z)$ where $s$ is the starting position between $0$ and $m$

adding the $z$ coefficients of this polynomial gives the exact odds of hitting $m$ at some step

This can get messy cause you have square root functions in terms of z, but this can be handled with the binomial theorem.