Consider the following Markov chain ($q = 1-p$):
I want to find the mean first passage time $m(i ,j) (i, j \geq 0)$, where $m(i, j)$denotes the expected number of steps to reach state $j$ when the Markov chain starts from state $i$.
But I'm not sure where to start, as there are an infinite number of states, and couldn't deduce a finite number of equations.
All of the following arguments are based around the recursive formula that comes from conditioning on the first step:
$$m(i,j) = 1 + (1-p) \cdot m(i-1,j) + p \cdot m(i+1, j)$$
Suppose $i > j$:
Let's simplify notation by recognizing that shifting $i$ and $j$ equally has no effect:
$$m(i,j) \equiv \hat{m}(i-j)$$
If $p\geq.5$, then the expectation is infinite. (This will follow from our solution to the $p<.5$ case.)
If $p < .5$, then: $$\hat{m}(k) = 1 + (1-p) \cdot \hat{m}(k-1) + p \cdot \hat{m}(k+1)$$ $$\Rightarrow \hat{m}(k)-\hat{m}(k-1) = 1 + p \cdot \big(\hat{m}(k+1)-\hat{m}(k-1) \big)$$ We can guess and verify that $\hat{m}(k) = \beta k$ is linear. $$\Rightarrow \beta k - \beta(k-1) = 1 + p(\beta(k+1) - \beta(k-1))$$ $$\Rightarrow \beta = 1 + 2p\beta$$ $$\Rightarrow \beta = \frac{1}{1-2p}$$ Note that $\beta$ does not depend on $k$, so we guessed correctly. Our equation is satisfied for any $k$ by: $$\Rightarrow \hat{m}(k) = \frac{k}{1-2p}$$ In particular, we can see for $k=1$:
$$\begin{align} \hat{m}(1) &= 1 + (1-p) \cdot \hat{m}(0) + p \cdot \hat{m}(2)\\ &= 1 + \frac{2p}{1-2p} \\ &= \frac{1}{1-2p} \end{align}$$
Note that our expression for $\hat{m}(k)$ has the correct boundary values: when $p=0$ it deterministically takes $k$ steps, and the expression gets arbitrarily large as $p$ goes to $.5$ from the left. In fact, this proves the expectation is infinite for the $p\geq .5$ case since $\hat{m}$ is monotonically increasing in $p$.
Suppose $i < j$:
For any fixed $j$, there are finitely many states to consider and an equal number of equations.
$$m(0,j) = 1 + (1-p)\cdot m(0,j) + p \cdot m(1,j)$$ $$\Rightarrow p \cdot m(0,j) = 1 + p \cdot m(1,j)$$ $$\Rightarrow m(0,j) = 1/p + m(1,j)$$
Now let's compute the next one: $$m(1,j) = 1 + (1-p)\cdot m(0,j) + p \cdot m(2,j)$$ $$\Rightarrow p \cdot m(1,j) = 1+(1-p)/p + p \cdot m(2,j)$$ $$\Rightarrow m(1,j) = (1+(1-p)/p)/p + m(2,j)$$
There is a pattern: $$m(i,j) = A_{i} + m(i+1, j)$$ Where: $$A_{i} = (1+(1-p)A_{i-1})/p$$ $$A_{0}=1/p$$ Thus: $$A_{i} = \sum_{k=0}^{i} \frac{(1-p)^{k}}{p^{k+1}}$$
Recursing forward until $j-1$, we get: $$m(j-1,j) = A_{j-1} + m(j,j)$$ $$\Rightarrow m(j-1,j) = A_{j-1}$$ Now, we can recurse backwards: $$m(i,j) = \sum_{n=i}^{j-1}A_{n}$$ $$\Rightarrow m(i,j) = \sum_{n=i}^{j-1}\sum_{k=0}^{n} \frac{(1-p)^{k}}{p^{k+1}}$$ This can be simplified further by noticing $A_n$ is the sum of a finite geometric series. There are three cases to consider depending on the value of $r = (1-p)/p$.
If $(1-p)/p = 1$, then $p=.5$ and $A_{n}=2(n+1)$, thus:
$$\begin{align} m(i,j) &= \sum_{n=i}^{j-1}2(n+1) \\ &= j(j+1) - i(i+1) \end{align}$$
If $(1-p)/p < 1$, then $p > .5$ and $A_{n}$ is a finite geometric series with $r = (1-p)/p$, thus:
$$\begin{align} A_{n} &= \frac{1}{p}\left( 1 - \frac{1-p}{p} \right)^{-1} \left( 1 - \left(\frac{1-p}{p}\right)^{n+1} \right) \\ &= (2p-1)^{-1} \left( 1 - \left(\frac{1-p}{p}\right)^{n+1} \right) \end{align}$$
Their summation is then: $$\begin{align} m(i,j) &= \sum_{n=i}^{j-1} (2p-1)^{-1} \left( 1 - \left(\frac{1-p}{p}\right)^{n+1} \right) \\ &= (2p-1)^{-1} \left( (j - i) - \sum_{n=i}^{j-1} \left(\frac{1-p}{p}\right)^{n+1} \right) \\ &= (2p-1)^{-1} \left( (j - i) - p(2p-1)^{-1} \left( \left(\frac{1-p}{p}\right)^{i+1} - \left(\frac{1-p}{p}\right)^{j+1} \right) \right) \end{align}$$
If $(1-p)/p > 1$, then $p < .5$ and $A_{n}$ is a finite geometric series.
We can do exactly as in the previous case but by reversing the finite geometric series and using $r = p/(1-p)$.
(I'll write this up at some point, but it's not mathematically harder than the previous case, just a bit messier notationally.)