<s>[INST] Expected first return time of Markov Chain Given the following Markov Chain:
$$M = \left(
\begin{array}{cccccc}
 \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\
 \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 \\
 \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & 0 \\
 \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \\
 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\
 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\
\end{array}
\right)$$
I need to find $E(T_1 | X_0 = 1)$, with $T_1 = \inf\{ n \geq 1 : X_n = 1\}$, i.e. the expected first arrival time of M.
I know that I can recursively calculate the probability of arriving back at 1 after exactly n steps:
$$f_1(n) = P(X_n = 1, X_{n-1} \neq 1,...,X_1 \neq 1, X_0 = 1) $$
This can be done the following way: 
$$f_1(n) = p_{i,i}(n)-\sum_{k=1}^{n-1}f_1(k)p_{i,i}(n-k)$$
where $p_{i,i}(n) = (M^n)_{i,i}$ is the probability of going from state i to state i in n steps.
So I would say that $$E(T_1 | X_0 = 1)= \sum_{n=1}^\infty nf_1(n)$$
is the expected return time to step 1. However I have no idea how to actually evaluate the series, can anybody help me please?
 [/INST] I think Zoe's approach is the easiest but that she has the equations wrong.
Let 
$$T_{11} = E(T_1\mid X_0=1) \\
  T_{21} = E(T_1\mid X_0=2).$$
We want to find $T_{11}$. Considering the possible transitions between states $1$ and $2$ and their probabilities, we get equations:
$$T_{11} = 1+\dfrac{1}{2}T_{21}\qquad\qquad\qquad (1) \\
  T_{21} = 1+\dfrac{3}{4}T_{21}\qquad\qquad\qquad (2)$$
Solving these simultaneously gives $T_{11} = 3$.
Note: Derivation of Equation $(1)$:


*

*the $1$ is to count $1$ for the current state transition;

*we have probability $1/2$ to move from State $1$ to State $2$, from where the remaining steps to return to State $1$ is $T_{21}$.


Equation $(2)$ is derived similarly.
</s>