TITLE: Random walk with single absorbing boundary
QUESTION [2 upvotes]: 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.

REPLY [3 votes]: 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.
{"set_name": "stack_exchange", "score": 2, "question_id": 641765}