Let $S = \{1,2,3,4\}$ be a state space like this
$$\begin{array}\\
1 & – & 2 \\
| & & |\\
3 & – & 4 \end{array} $$
and let $P$ be the transition matrix given by
$$P = \begin{pmatrix} \frac{1}{4} & \frac{3}{8} & \frac{3}{8} & 0 \\
\frac{3}{8} & \frac{1}{4} & 0 & \frac{3}{8}\\
\frac{3}{8} & 0 &\frac{1}{4}&\frac{3}{8}\\
0&\frac{3}{8}&\frac{3}{8}&\frac{1}{4} \end{pmatrix}. $$
Let's say a particle starts at $1$. I want to determine:
- The mean number of steps before the particle returns to it's starting point
- The mean number of steps before the particle reaches the diagonally opposite state $4$.
I found the stationary distribution $\pi = (\pi_1, \pi_2, \pi_3, \pi_4 ) = (\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4})$ and therefore the answer to the first question is $\mu_1 = \tfrac{1}{\pi_1} = 4$.
I can't solve the second question with this approach. How can I solve the first and second question without using the stationary distribution? I tried something like this:
if $E_n$ is the mean number of mean number of steps before the particle starting at $1$ reaches $n \in S$ then $E_1 = 0$. But I don't know for sure what $E_2, E_3, E_4$ are. My guess is
\begin{cases}
E_1 &= 0\\
E_2 &= 1 + \tfrac{3}{8} E_4 + \tfrac{3}{8} E_1\\
E_3 &= 1 + \tfrac{3}{8} E_4 + \tfrac{3}{8} E_1\\
E_4 &= 1 + \tfrac{3}{8} E_2 + \tfrac{3}{8} E_2 \\
\end{cases}
Best Answer
The one-step analysis at the end of the question is the wrong way around. You need a fixed target, and the index on $E$ should index the states from which you're trying to reach that target.
But in the present case there are less cumbersome ways to get the expectation values you want.
For the first question, the stationary distribution is constant by symmetry, so $\mu_1=4$ is immediate. (Note that this counts staying at $1$ as a "return".)
For the second question, get rid of the self-loops and scale the number of steps by $\frac1{1-\frac14}=\frac43$ to compensate. Then you have a simple walk on the given graph, with equal probabilities $\frac12$ to go either way. Combine the steps into pairs. Each pair has probability $\frac12$ to return to $1$ and $\frac12$ to get you to $4$. Thus the expected number of pairs is the expected number of trials until the first success in a Bernoulli trial with success probability $\frac12$. So the expected number of steps from $1$ to $4$ is
$$\frac43\cdot2\cdot\frac1{\frac12}=\frac{16}3\;.$$
Here's the one-step analysis:
Let $E_n$ be the expected number of steps from state $n$ to state $4$. We're looking for $E_1$. The $E_i$ satisfy
\begin{align} E_1&=1+\frac14E_1+\frac38E_2+\frac38E_3\;,\\ E_2&=1+\frac14E_2+\frac38E_1+\frac38E_4\;,\\ E_3&=1+\frac14E_3+\frac38E_1+\frac38E_3\;,\\ E_4&=0\;. \end{align}
(I wrote it out in full since you wanted the general method; in the present case, we could use the fact that $E_2=E_3$ by symmetry to save a variable.) Solving this system of equations yields $E_1=\frac{16}3$, as derived above.