# Thread: Independent and irreducible time-homogenous Markov Chains

1. ## Independent and irreducible time-homogenous Markov Chains

Hi everyone
Can someone please help me with the following problem?

Let $\{X_n, n = 0,1,...\} \ \mbox{and} \ \{Y_n, n = 0,1,...\}$ be independent and irreducible time-homogenous Markov Chains with common state-space E, and transition matrices P and Q respectively.

(a) Show that the two-dimentsional process defined by $\mathcal{Z}_n = (X_n,Y_n), n = 0,1,....$ is a time-homogenous Markov chain with state space E $\times$ E.

(b) Prove that if $X_n$ and $Y_n$ are both periodic, then $\mathcal{Z}_n$ can be reducible.

(c) Show that $\mathcal{Z}_n$ is irreducible if both $X_n$ and $Y_n$ are aperiodic. Hint: Use the fact that if $X_n$ is irreducible and aperiodic, then for each $i,j \in E$ there exists some $M_{ij}$ such that $(P^m)_{ij} > 0$ for all $m \geq M_{ij}$

Thanks,
bye bye

2. Originally Posted by BrooketheChook
Hi everyone
Can someone please help me with the following problem?

Let $\{X_n, n = 0,1,...\} \ \mbox{and} \ \{Y_n, n = 0,1,...\}$ be independent and irreducible time-homogenous Markov Chains with common state-space E, and transition matrices P and Q respectively.

(a) Show that the two-dimentsional process defined by $\mathcal{Z}_n = (X_n,Y_n), n = 0,1,....$ is a time-homogenous Markov chain with state space E $\times$ E.
You should check the definition, i.e. compute the probability of "paths" of the process $(Z_n)_n$ and see that it matches the same probability for some Markov chain.

For all $n\geq 1$, for all $z_0=(x_0,y_0),z_1=(x_1,y_1),\ldots,z_n=(x_n,y_n)\i n E\times E$, we have:

$P(Z_0=z_0,Z_1=z_1,\ldots,Z_n=z_n) =$ $P(X_0=x_0,\ldots,X_n=x_n)P(Y_0=y_0,\ldots,Y_n=y_n)$

because of the independence between $(X_n)_n$ and $(Y_n)_n$. Then you can express each factor of the right hand side using the definition of a Markov chain (like $\pi_0(x_0)P(x_0,x_1)\ldots P(x_{n-1},x_n)$ where $\pi_0$ is the distribution of the initial location). And rewrite the formula so that it looks like $\nu_0(z_0)R(z_0,z_1)\cdots R(z_{n-1},z_n)$ for some $\nu_0$ and matrix $R$. That would answer the question.

Note that there are many different conventions of notation, and several ways to write the definitions; you may have to adapt the above, but the principle remains the same.

(b) Prove that if $X_n$ and $Y_n$ are both periodic, then $\mathcal{Z}_n$ can be reducible.
The idea is the following. The Markov chain $(\mathcal{Z}_n)_n$ is "reducible" if there are two states $(x_0,y_0),(x_1,y_1)\in E\times E$ such that $R^n((x_0,y_0),(x_1,y_1))=0$ for all $n$, i.e. if there is no "path" for $Z$ from $(x_0,y_0)$ toward $(x_1,y_1)$. On one hand, since both $X$ and $Y$ are irreducible, there is both a path for $X$ from $x_0$ to $x_1$, and a path for $Y$ from $y_0$ to $y_1$. But it may happen that there exist no two paths of the same length $n$ that satisfy these constraints, which is what it would require for $Z$ to connect $(x_0,y_0)$ to $(x_1,y_1)$.

Consider the following simple example: $X$ is a Markov chain with state space $\{0,1\}$ and transition matrix $P$ such that $P(0,1)=1$ and $P(1,0)=1$. What does $X$ look like? If $Y$ has same distribution as $X$, is $Z$ irreducible?

(You could look for a less singular example afterward)

(c) Show that $\mathcal{Z}_n$ is irreducible if both $X_n$ and $Y_n$ are aperiodic. Hint: Use the fact that if $X_n$ is irreducible and aperiodic, then for each $i,j \in E$ there exists some $M_{ij}$ such that $(P^m)_{ij} > 0$ for all $m \geq M_{ij}$
Let $(x_0,y_0),(x_1,y_1)\in E\times E$. You need to prove $R^n((x_0,y_0),(x_1,y_1))>0$ for some $n$.
Given the assumptions, we can apply the hint to both $X$ (with the states $x_0$ and $x_1$) and $Y$. The expression for $R$ obtained in (a) should then make it easy to conclude.

Tell me what you tried if you experience further difficulties.

Laurent.