Results 1 to 2 of 2

Thread: Independent and irreducible time-homogenous Markov Chains

  1. #1
    Junior Member BrooketheChook's Avatar
    Joined
    Sep 2009
    From
    Gold Coast
    Posts
    27

    Independent and irreducible time-homogenous Markov Chains

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

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by BrooketheChook View Post
    Hi everyone
    Can someone please help me with the following problem?

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Markov Chains
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Feb 9th 2010, 04:58 PM
  2. Markov Chains
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: Aug 26th 2009, 08:22 AM
  3. Markov Chains
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Apr 26th 2009, 08:17 PM
  4. Markov Chains
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Mar 18th 2009, 10:53 AM
  5. Markov Chains
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Mar 6th 2009, 09:34 AM

Search Tags


/mathhelpforum @mathhelpforum