# Irreducible markov chain problem

Let $$P$$ be a stationary transition probability matrix of the markov chain $$\{X_n , n \ge 0\},$$ which is irreducible and every state has a period 2. Further suppose that the markov chain $$\{Y_n , n \ge 0\}$$ on the same state space has transition probability matrix $$P^2$$ . Both chains are assumed to have the same initial distributions.

then state how the chain $$\{Y_n , n \ge 0\}$$ is irreducible ?

i am very new to the concept of markov chains and found this question beyond my level , please tell how and why $$\{Y_n , n \ge 0\}$$ should be irreducible ?

## 2 Answers

Check out proposition 5.4.3 on page 119 of Meyn and Tweedie. If you sample an irreducible chain at its period, the resulting chain is irreducible only when you restrict the state space to a cyclic class. What’s more is that these cyclic classes are absorbing, so with every step of the sampled chain, it stays in there with probability 1. The counterexample mentioned in the comment is a perfect example of this: the one-step 2x2 transition matrix with zeroes on the diagonal and ones on the off-diagonal.

A markov chain is irreducible if it is possible to get to any state from any state. The fact that $$\{X_n,n\geq 0\}$$ is periodic of period $$2,$$ let me think, $$\{Y_n,n\geq 0\}$$ is not irreductible

In fact, for two states $$i,j$$, there exists $$n>0$$, such as $$p_{ij}^{(n)} = \mathbb{P}(X_n=j\mid X_0=i) = (P^n)_{ij} > 0.$$

As $$\{X_n,n\geq 0\}$$ is periodic of period $$2,$$ $$\mathbb{P}(X_2=i\mid X_0=i)>0$$

if $$n=2k$$ is even $$p_{ij}^{(n)}=(P^n)_{ij} = (P^{2k})_{ij} = \left((P^2)^{k}\right)_{ij} = \mathbb{P}(Y_k=j\mid Y_0=i) > 0.$$

if $$n=2k+1$$ is odd fail to prove that.

• I agree to your facts but then why this counter example comes ? $let P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$, this irreducible but then $P^2=\begin{bmatrix}1&0\\0&1\end{bmatrix}$ is not irreducible – ANUJ NAIN Jun 11 '19 at 1:54
• That's right, $n$ will always be odd. And when $n$ is odd, ${Y_n, n\eq 0\}$ can not be irréductible. Maybe it's not true. But I fail to prove that – Abdoul Haki Jun 11 '19 at 14:25
• Just because a chain has period two doesn’t mean that it’s possible to return to places in two steps. – Taylor Jun 11 '19 at 16:45
• It mean the gcd of the possible times of step you can return is two. In other word, you can return only in 2, 4, 6, ... step. – Abdoul Haki Jun 11 '19 at 17:50
• @AbdoulHaki or 4,6,... – Taylor Jun 11 '19 at 19:29