(Countably) Infinite Markov Chain - Expected number of steps to reach the origin

Question

I am given a chain with state space $S=\{0, 1, 2, \ldots \}$, with transition probabilities $p(0,0)=3/4$, $p(0,1)=1/4$, $p(x, x-1)=3/4$, and $p(x,x+1)=1/4$ for $x \geq 1$.

For $x > 0$, let $e(x)$ denote the expected number of steps in the chain until it reaches the origin assuming that $X_0 = x$. Find $e(1)$. (Hint: first consider the expected return time starting at the origin and write $e(1)$ in terms of this.)

My attempt: Note that $e(0)$ is $0$ as we have started at the origin and thus we will end up there in 0 steps. Note that for $x>0$, $$e(x) = 1 + \frac{3}{4}e(x-1) + \frac{1}{4}e(x+1) \quad(*)$$

So $$e(1) = 1 + \frac{3}{4}e(0) + \frac{1}{4}e(2)=1+\frac{1}{4}e(2)$$ But now I am not sure how to proceed. Is my expression in $(*)$ even correct? I think $(*)$ is a linear difference equation which I do not know how to solve.

Furthermore, I am also asked to find $e(x)$ for all $x>0$.

Answer 1

A standard approach for return time is that if $\pi$ is the limiting distribution, then the expected return time to state $i$, starting from $i$, is $\frac1{\pi_i}$.

Here, we can work out the limiting distribution $\pi$ with very little effort by observing that $\frac14 \pi_i = \frac34 \pi_{i+1}$ for all $i \ge 0$. (Here, $\frac14 \pi_i$ is the limiting rate of transitions from $i$ to $i+1$, $\frac34 \pi_{i+1}$ is the limiting rate of transitions from $i+1$ to $i$, and these transitions must alternate so their rates are equal.)

Once we've done that, we know $e(0)$. By looking at where the first step from $0$ goes (either back to $0$, in which case we return in $1$ step, or to $1$, in which case we return in $1 + e(1)$ steps on average) we can solve for $e(1)$.

Finally, you can argue that the expected time to go from $i$ to $i-1$ is the same for all $i$, which should let you conclude that $e(x) = x \cdot e(1)$.