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.