# Expected return time and limits in discrete time Markov chain

I have a discrete time Markov chain $\{X_n : n\geq 0\}$ with state space $\{1,2,3,4,5\}$ and transition matrix

$P=\begin{pmatrix}0.2&0&0&0.8&0\\ 0&0.5&0&0&0.5\\ 0.3&0.2&0.5&0&0\\0.3&0&0&0.7&0\\ 0&0.4&0&0&0.6\end{pmatrix}$

I have the following questions:

(a) Calculate $\lim_{n\to\infty}p_{11}^{(n)}$

(b) Calculate the mean recurrence time of state 2, given that $X_0 = 2$.

The first thing that strikes me is that this chain is aperiodic but not irreducible. However, it is easy to verify that $f_{11} = 1$, thus state 1 is recurrent and aperiodic. Then the limit in part (a) is equal to $\frac{1}{\sum_{n=1}^{\infty}nf_{11}(n)}$, which is, again, easy to work out. As for part (b), I would let $T$ denote the time of first return to state 2 and calculate $\sum_{n=1}^{\infty}P(T\geqslant n)$ to give the expectation.

Here is what I would like to ask:

1.) Is my above reasoning correct?

2.) Is there an easier approach to part (a)?

3.) Could you find the expectation in (b) using $\mu_i = \frac{1}{\pi_i}$? I am not sure if you can, since the chain is not irreducible and so the chain possesses infinitely many stationary distributions.

Well, I assume your second row is $[0, 0.5, 0, 0, 0.5]$.

Actually, the non-irreducibility of this Markov chain makes calculation much simpler, and I guess it is intentional.

Here are some hints:

for a), note that state 1 and 4 are communicating, so calculating $\lim_{n\to\infty}p_{11}^{(n)}$ for the whole matrix is same for the matrix: $$\hat P _{1,4}=\begin{pmatrix}0.2&0.8\\ 0.3&0.7\end{pmatrix}$$

some linear algebra will bring you to the answer of $3/11$.

for b) note that state 2 and 5 are also communicating, starting from state 2, we will never escape 2 and 5, and the transition matrix is $$\hat P _{2,5}=\begin{pmatrix}0.5&0.5\\ 0.4&0.6\end{pmatrix}$$

define the mean recurrence time of state 2 be $T_2$, similarly for $T_5$

then we have \begin{align} T_2&=0.5+0.5T_5\\ T_5&=1+0.4T_2+0.6T_5 \end{align}

the first line means that starting from state 2, you have 0.5 chance staying there which gives recurrence time of 1, and 0.5 chance moving to state 5, which results in.mean recurrence time of state 5. Similarly for the second line.

finally, some algebra will give you $T_2=3.5$.

• Nice answer. So what about my third point? Does the fact that it isn't irreducible mean that we cannot simply take the reciprocal of the stationary probability and get the mean time? – wrb98 Oct 8 '17 at 17:17
• @Will if we gonna use the stationary probability, then maybe a more complicated formula than the reciprocal, also involving some matrix algebra I guess. – vita nova Oct 9 '17 at 0:32
• Let $T_k = \min \{ n \ge 1 \mid X_n = k \}$. We want to find $\mathbb{E}_2[T_2] = \mathbb{E}[T_2 \mid X_0 = 2]$. The stationary distribution corresponding to $\hat P_{2,5}$ is $(\frac{4}{9}, \frac{5}{9})$, and thus $\mathbb{E}_2[T_2] = \frac{9}{4}$. To verify, note that first-step conditioning results in \begin{align} \mathbb{E}_2[T_2]&=1+0.5 \mathbb{E}_5[T_2]\\ \mathbb{E}_5[T_2]&=1+ 0.6\mathbb{E}_5[T_2] \end{align} which agrees with the above result from the stationary distribution. – user365239 Nov 6 '17 at 4:08