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?
Best Answer
I agree with Mick A's response. We can confirm it by another method of finding the expected return.
This Markov chain is reducible. We can actually create a closed irreducible subset out of the full state chain. $$ \begin{bmatrix} \frac{1}{2}&\frac{1}{2}\\ \frac{1}{4}&\frac{3}{4} \end{bmatrix} $$
We can then find the stationary distribution for this matrix since it's aperiodic, finite, and irreducible. This stationary distribution is: $$ \pi_1=\frac{1}{3} \text{ and } \pi_2 = \frac{2}{3} $$
If you don't know how to find the stationary matrix, just know it can be solved by either $\lim_{n\to\infty}P^n$ (wolfram alpha will do this) if the chain is aperiodic, or solving for $\pi P=\pi$.
Next, there is a theorem which states that if a Markov chain is finite and if it has a stationary distribution then $\mathbb{E}_x[T_x]=\frac{1}{\pi_x}$. In our case, $\mathbb{E}_1[T_1]=\frac{1}{\frac{1}{3}}=3$.