The Mean First Passage Time of a Markov Chain with Infinite Number of States 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.
 A: 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.)
