Random walk with single absorbing boundary

Question

There is a random walk on a linear lattice of size $\{0,N\}$, where $0$ is the origin and a reflecting boundary and $N$ is the absorbing boundary. It moves forward or backward one step at a time with $\frac12$ probability. The number of times a state/point $(p)$ inside the lattice being visited before it gets absorbed was calculated as $2(N-p)$, $2$ times the distance between the point and $N$. (I got this result in simulation, I don't know how to derive this mathematically.)

If I increase the step size (moving more than one step at a time) the walker can take $x+i$ or $x-i$ with $\frac{1}{2}$ probability, where $i=1,2,3,\dots,k$. That is if k is 2, then the walker can either take 1 step or 2 step forward/backward with equal probability ($\frac{1}{2k}$).

However, if the walker goes beyond the boundary [$<0$ or $>N$], then it'll be reflected back as follows, $$ \mbox{new x} = \begin{Bmatrix} 0+(0-x) & \mbox{if} \ x < 0\\ N-(x-N) & \mbox{if} \ x > N \end{Bmatrix} $$

How to derive the number of visits [i.e. $2(N-p)$] mathematically for single step random walk? And how the increase in step size $k$ will affect the same?

Thanks in advance.

Answer 1

Define $$e(x)=\mathbb{E}_x(\mbox{number of visits to state }p).$$ Then $e$ is the unique function that satisfies $e(N)=0$, $e(x)=(Pe)(x)$ for $x\neq p$, and $e(p)=1+(Pe)(p)$. That is, the function $e$ is harmonic at all points except $p$, where it is 1-harmonic. Here $$(Pe)(x)=\mathbb{E}_x(e(X_1))=\sum_y p_{xy} e(y).$$

The function $e$ can always be calculated, in principle, using linear algebra.

The case $k=1$ is particularly easy, since in this context "harmonic" means linear, and the chain is continuous, in the sense that it can't jump over states. In particular, the value of $e(x)$ is constant for all $x\leq p$.

On the right, $e$ is a straight line function from $e(p)$ at $p$ to zero at $N$, that is, it is of the form $e(x)=c(N-x)$ for $p\leq x\leq N$. Now, the 1-harmonicity of $e$ at $p$ gives $$e(p)= 1+ (1/2)e(p-1)+(1/2)e(p+1),$$ so that $e(p)=2+e(p+1)$ and so $c(N-p)=2+c(N-(p+1))$. Solving gives $c=2$ and we conclude that $$e(x)=2(N-(x\vee p))\mbox{ for } 0\leq x\leq N.$$

In general, with multisteps and your boundary conditions we lose the nice, explicit formula.

---

The function $e$ is the solution of $(I-\widetilde P)e=\delta_p$ where $I$ is the identity matrix,
$\widetilde P$ is $P$ modified by replacing the 1 in the bottom right hand corner by a 0, and $\delta_p$ is the vector with a one in position $p$, and zero elsewhere.

Here is a worked out example when $N=5$, $p=1$, and $k=2$. In this case, the transition matrix for the Markov chain is $$P=\pmatrix{0& 1/2& 1/2& 0& 0& 0\\ 1/4& 1/4& 1/4& 1/4& 0& 0\\ 1/4& 1/4& 0& 1/4& 1/4& 0\\ 0& 1/4& 1/4& 0& 1/4& 1/4\\ 0& 0& 1/4& 1/4& 1/4& 1/4\\ 0& 0& 0& 0& 0& 1}$$

The solution to $(I-\widetilde P)e= \delta_p$ is $$e=\left[{200\over 55},{236\over 55},{164\over 55},{124\over 55},{96\over 55},0\right] = [3.636, 4.291, 2.982, 2.255, 1.745, 0.000].$$

$\hskip2in$

The graph above compares the expected number of visits to state 1 under the single step ($k=1$) and the multistep ($k=2$) schemes. The multistep walk diffuses much faster and is absorbed sooner, hence making fewer visits to state 1.