Exact formula for computing n-step transition probability of random walks with self-transitions

Question

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$. Assume that $P_{00}=1-p$ and $P_{ii-1}=q>0$, $P_{ii}=r>0$, $P_{ii+1}=p$ for $i\geq1$; $p+q+r=1$. Consider that the process starts at state $i$ at time $0$. Let $P_{ij}^{n}$ be the probability that the process is at state $j$ at time $n$. I would like to know whether there is an exact formula for computing the $n$-step transition probability $P_{ij}^n$? Or at least $P_{00}^n$? I need an explicit formula rather than the asymptotic analysis of the random process as $n\rightarrow \infty$.

I came across the Karlin-McGregor representation formula in [1] which shows that

\begin{equation} P_{ij}^n=\pi_j\int_{-1}^1x^nQ_i(x)Q_j(x)\mathrm{d}\psi(x) \end{equation} for some polynomials $Q_n(x)$ ($Q_0(x)=1$) and measure function $\psi(x)$. But I was not able to find an explicit formula of $Q_n(x)$ and $\psi(x)$ for the case the self-transition probability $r>0$. Does anyone know whether $P_{ij}^n$ can be explicitly calculated for this case?

[1] Karlin, Samuel; McGregor, James. Random walks. Illinois J. Math. 3 (1959), no. 1, 66--81. http://projecteuclid.org/euclid.ijm/1255454999.

Answer 1

If we ignore the "boundary condition" at 0 for a moment, the answer will be a sum over paths from i$\rightarrow$j of the product of the transition probabilities along the path. This is just $\sum_{k\ell} \frac{n!}{k!\ell!(n-k-\ell)!} q^k r^\ell p^{n-k-\ell}$, where the sum is over $k$, $\ell$ such that $0\le k\le n$, $0\le \ell\le n$, $n-2k-\ell=j-i$. We'll call this the free solution.

If $q=r$, then treating the boundary is also straightforward. We change the initial condition to be 1 unit of probability at i plus another 1 unit of probability at -i. This is like the method of image charges in electromagnetics. You can think of the second unit of probability as just a reflection in a mirror. If the real probability passes into the mirror, an equal amount of mirror probability will pass out at the same time, so the flux of probability across the mirror at 0 is made to be zero by symmetry. Then the final probability is just $P_{ij}^n + P_{-ij}^n$ in terms of the free solution. If $j=0$ you will need to divide by 2.

If $q\ne r$, there are cases where the free solution is correct, like when $(n-|i-j|)/2 < \min(i,j)$. Otherwise, perhaps you can come up with a combinatorial answer by counting paths that bump up against the boundary.