We have state space $E = \{0,1,2,3,4,5\}$ and a Markov chain denoted by
$$(X_n)_{n\in \{0,1,2,\dotsc\}}$$
The transition probabilities are such that if we are in state $0$,
$$p_{01}=1$$
if we are in state $1,2,3,4$, we will go left and right with equal probability. If we are in state $5$ we stay there (with probability $1$, absorbing state). What is the first passage time to state $5$ if we start from state $0$ (i.e. what is the probably that the first time we visit state 5 is at time n)?
At first it looks like a simple random walk question to me but the tricky bit is that state $0$ goes to state $1$ with probability $1$ which sort of makes it asymmetric. Could anybody give their insight on this problem? Thanks.
Let $T = \inf\{n \geq 0 : X_n = 5\}$ be the first hitting time and consider the generating function
$$ F(z) = \sum_{n=0}^{\infty} z^n f_{05}(n).$$
Let us consider the process $\tilde{X}_n$ which is obtained by killing $(X_n)$ after its visit to the state $5$. Then its transition matrix $\tilde{P} = (\tilde{p}_{ij})$ satisfies
$$ \tilde{p}_{ij} = \begin{cases} p_{ij}, & i \neq 5 \\ 0, & i = 5 \end{cases}.$$
With this process, we can write
$$ f_{05}(n) = \Bbb{P}^{0}(T = n) = \Bbb{P}^{0}(\tilde{X}_n = 5) = [\tilde{P}^n]_{05}, $$
where the notation $[\cdot]_{ij}$ reads out the $(i,j)$-component of the the given matrix. Plugging this to $F(z)$, we have
$$ F(z) = \sum_{n=0}^{\infty} [(z\tilde{P})^n]_{05} = [(\operatorname{id}-z\tilde{P})^{-1}]_{05}.$$
In our case, $\tilde{P}$ can be written as
$$ \tilde{P} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$
with $\tilde{P}_{ij}$ corresponding to the $(i+1, j+1)$-component of the right-hand side. Now it is not hard to compute that
$$ F(z) = [(\operatorname{id}-z\tilde{P})^{-1}]_{05} = \frac{z^5}{5z^4-20z^2+16}. $$
So it suffices to identify the series expansion of the right-hand side.
Method 1. Notice that $f_{05}(0) = \cdots = f_{05}(4) = 0$ and that
\begin{align*} 1 &= (5z^{-1} - 20z^{-3} + 16z^{-5})F(z) \\ &= \sum_{n=0}^{\infty} [5f_{05}(n+1) - 20 f_{05}(n+3) + 16f_{05}(n+5)] z^n. \end{align*}
So we may solve the recurrence relation
$$ 5f_{05}(n) - 20 f_{05}(n+2) + 16f_{05}(n+4) = \delta_{\{n = 1\}} $$
subject to the initial condition $f_{05}(0) = \cdots = f_{05}(4) = 0$.
Method 2. Expanding $F(z)$ amounts to finding the partial fraction decomposition of it. Brutal force will work of course, though this can be done more easily if we notice that
$$ F(z) = \frac{1}{T_5(1/z)}, $$
where $T_n$ is the Chebyshev polynomial of the 1st kind. Therefore, with $\theta_k = \frac{2\pi k}{5} + \frac{\pi}{10}$ we have
$$ F(z) = \sum_{k=0}^{4} \frac{1}{T_5'(\cos \theta_k)} \cdot \frac{z}{1 - z \cos \theta_k} = \sum_{n=1}^{\infty} \bigg( \sum_{k=0}^{4} \frac{1}{T_5'(\cos \theta_k)} \cos^{n-1} \theta_k \bigg) z^n. $$
Using the relation $T_n'(\cos\theta) = n \frac{\sin n\theta}{\sin \theta}$, this can be simplified further and we get
$$ f_{05}(n) = \frac{1}{5} \sum_{k=0}^{4} \sin\theta_k \cdot \cos^{n-1} \theta_k. $$