Thread: Independent and irreducible time-homogenous Markov Chains

1. Independent and irreducible time-homogenous Markov Chains

Hi everyone

Let $\displaystyle \{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 $\displaystyle \mathcal{Z}_n = (X_n,Y_n), n = 0,1,....$ is a time-homogenous Markov chain with state space E $\displaystyle \times$ E.

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

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

Thanks,
bye bye

2. Originally Posted by BrooketheChook
Hi everyone

Let $\displaystyle \{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 $\displaystyle \mathcal{Z}_n = (X_n,Y_n), n = 0,1,....$ is a time-homogenous Markov chain with state space E $\displaystyle \times$ E.
You should check the definition, i.e. compute the probability of "paths" of the process $\displaystyle (Z_n)_n$ and see that it matches the same probability for some Markov chain.

For all $\displaystyle n\geq 1$, for all $\displaystyle 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:

$\displaystyle P(Z_0=z_0,Z_1=z_1,\ldots,Z_n=z_n) =$ $\displaystyle 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 $\displaystyle (X_n)_n$ and $\displaystyle (Y_n)_n$. Then you can express each factor of the right hand side using the definition of a Markov chain (like $\displaystyle \pi_0(x_0)P(x_0,x_1)\ldots P(x_{n-1},x_n)$ where $\displaystyle \pi_0$ is the distribution of the initial location). And rewrite the formula so that it looks like $\displaystyle \nu_0(z_0)R(z_0,z_1)\cdots R(z_{n-1},z_n)$ for some $\displaystyle \nu_0$ and matrix $\displaystyle 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 $\displaystyle X_n$ and $\displaystyle Y_n$ are both periodic, then $\displaystyle \mathcal{Z}_n$ can be reducible.
The idea is the following. The Markov chain $\displaystyle (\mathcal{Z}_n)_n$ is "reducible" if there are two states $\displaystyle (x_0,y_0),(x_1,y_1)\in E\times E$ such that $\displaystyle R^n((x_0,y_0),(x_1,y_1))=0$ for all $\displaystyle n$, i.e. if there is no "path" for $\displaystyle Z$ from $\displaystyle (x_0,y_0)$ toward $\displaystyle (x_1,y_1)$. On one hand, since both $\displaystyle X$ and $\displaystyle Y$ are irreducible, there is both a path for $\displaystyle X$ from $\displaystyle x_0$ to $\displaystyle x_1$, and a path for $\displaystyle Y$ from $\displaystyle y_0$ to $\displaystyle y_1$. But it may happen that there exist no two paths of the same length $\displaystyle n$ that satisfy these constraints, which is what it would require for $\displaystyle Z$ to connect $\displaystyle (x_0,y_0)$ to $\displaystyle (x_1,y_1)$.

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

(You could look for a less singular example afterward)

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

Tell me what you tried if you experience further difficulties.

Laurent.