Stopping time random walk in a circle I've been trying to solve this question for some time now, and I could not figure out the second part of the exercise. Here it is:
Consider a circle with five markings 0, 1, 2, 3, 4, in that order. Suppose that a particle starts at state 0 and moves to state 1 or 4 with probability 1/2 each. Subsequent movements are to one of its neighbors with equal probability. Let $X_{n}$ be the state of the particle at time $n \geq 0$. Let
$$ 
\tau = \min \{n \geq 1: X_{n}=0 \} \text{ and } V_{3} = \sum_{n=1}^{\tau}I(X_{n}=3)
$$
a) Compute $E(\tau)$
b) Compute $E(V_{3})$
For part (a) I'm using that $X_{n}$ is an irreducible Markov chain with finite number of states $S = \{0,1,2,3,4\}$. It follows this chain is positive-recurrent and has a unique stationary distribution, which is
$$
\pi = \left( \frac{1}{|S|},\dots,\frac{1}{|S|} \right)
$$
The mean recurrence time for any of the states is then
$$
\mu_{i} = \frac{1}{\frac{1}{|S|}} = |S|, i \in S
$$
From this I got $E[\tau] = |S| = 5$ since $\tau$ is the time it takes to go back to state 0 after the chain started there. I wonder how can I solve this using recurrence, like in similar Markov chain problems.
For part (b) I thought about using total expectation but I'm not sure how to move forward. This is what I have so far
$$
E[V_{3}] = E[E[V_{3}|\tau=t]] = E \left[E \left[ \left. \sum_{n=1}^{\tau}I(X_{n}=3) \right| \tau=t\right] \right] =  E\left[ \sum_{n=1}^{\tau}P(X_{n} = 3) \right]
$$
Any suggestions will be appreciated.
EDIT: I added my attempt for an answer using @Joe suggestions. Let me know if you have any comments.
 A: This is my attempt on a solution based on @Joe suggestions.
Rearranging the transition matrix with the transient states first, i.e., 1-4 and thinking about state 0 as an absorbing state we get
$$
P =
\begin{pmatrix}
 0 & 1/2 & 0 & 0 & 1/2 \\
 1/2 & 0 & 1/2 & 0 & 0 \\
 0 & 1/2 & 0 & 1/2 & 0 \\
 0 & 0 & 1/2 & 0 & 1/2 \\
 0 & 0 & 0 & 0 & 1 \\
\end{pmatrix}
$$
We need o compute the fundamental matrix $N = (I_{4}-Q)^{-1}$, where $I_{4}$ is the identity matrix and
$$
Q =
\begin{pmatrix}
 0 & 1/2 & 0 & 0 \\
 1/2 & 0 & 1/2 & 0 \\
 0 & 1/2 & 0 & 1/2 \\
 0 & 0 & 1/2 & 0 \\
\end{pmatrix}
$$
Computing the fundamental matrix we have
$$
N =
(I_{4}-Q)^{-1} =
\frac{2}{5}
\begin{pmatrix}
 4& 3 & 2 & 1 \\
 3 & 6 & 4 & 2 \\
 2 & 4 & 6 & 3 \\
 1 & 2 & 3 & 4 \\
\end{pmatrix}
$$
Now, since $N_{ij}$ is the expected number of times the chain will visit transient state $j$ if it started in transient state $i$ we have
$$
\begin{equation}
 \begin{aligned}
  E[V_{3}|X_{1}=1] = \frac{4}{5} \\
  E[V_{3}|X_{1}=4] = \frac{6}{5}
 \end{aligned}
\end{equation}
$$
Finally, since $P(X_{1}=1) = P(X_{1}=4) = 1/2$ we have
$$
E[V_{3}] = E[V_{3}|X_{1}=1] P(X_{1}=1) + E[V_{3}|X_{1}=4] P(X_{1}=4)
= \frac{4}{5} \left( \frac{1}{2}\right) + \frac{6}{5} \left( \frac{1}{2}\right) = 1
$$
I think it makes sense to expect the chain to visit state 3 just one time since the expected number of steps before being absorbed at 0 are just 5.
