0

In our reading about Markov chains we had the following theorem (including proof):

Let $(X_n)_{n\in\mathbb{N}_0}$ denote a Markov chain with state space $E$. A periodic communicating class $C\subseteq E$ with period $p$ can be decomposed into a disjoint union of sets $C_0\cup C_1\ldots\cup\ldots\cup C_{p-1}$ in such a way that, if $i\in C_n$ and$j\in C_m$ with $m\neq n+1\text{ mod }p$, then $p_{ij}=0$.

Now it is asked if this statement is an equivalence statement.

What would be the statement that would make the theorem an equivalence statement? I cannot see it clear. In other words: What do I have to prove or disprove?

mathfemi
  • 2,631

1 Answers1

0

The missing part of the equivalence statement would be:

If $p_{ij}=0$ then $i\in C_n$ and $j\in C_m$ with $m\neq n+1\text{ mod }p$.

This is wrong in general, consider the Markov chain on $\{0,1,2,3,4\}$ with $p_{01}=p_{02}=\frac12$ and $p_{13}=p_{24}=p_{30}=p_{40}=1$, for $i=2$ and $j=3$.

$\qquad\qquad\quad$enter image description here

Edit: A rough sketch of a Markov chain with period $3$:

$\qquad\qquad\quad$enter image description here

Did
  • 279,727
  • How do you set the sets $C_0, C_1$ and $C_2$? – mathfemi Nov 01 '14 at 10:15
  • ?? Tell me! Apparently you know that the period is 3 hence... – Did Nov 01 '14 at 10:17
  • I think $C_0=\left{0,1,4\right}, C_1=\left{2\right}, C_2=\left{3\right}$; it is $p_{23}=0$, but $2\in C_1, 3\in C_2$, i.e. $n=1, m=2$ and so $m=n+1\text{ mod 3}$. – mathfemi Nov 01 '14 at 10:41
  • These are not the sets $C_k$ at all. How do you understand the family $(C_k)$ in general? – Did Nov 01 '14 at 10:43
  • Unfortunately I do not know what do you mean with "in general". – mathfemi Nov 01 '14 at 10:44
  • For a general periodic Markov chain, which picture of the classes $C_k$ do you have in your head when you try to imagine them? – Did Nov 01 '14 at 10:47
  • In our reading we wrote: Without loss of generality assume that $1\in C$. For $n\in\left{0,1,...,p-1\right}$ define $C_n:=\left{j\in C| \exists~m=n\text{ mod }p: p_{j1}^{(m)}>0\right}$. This are the $C_n$ I am searching for I think. But I cannot handle it. – mathfemi Nov 01 '14 at 10:52
  • Develop the program outlined in your reading in the case of the second picture in my answer. This might be your problem, actually, to reach an understanding of what these formulas actually mean... – Did Nov 01 '14 at 10:55
  • Mh, very difficult for me. So my problem is to find the $C_0,...,C_{p-1}$. Can you give me a "general tutorial" how to find them? – mathfemi Nov 01 '14 at 11:02
  • In the case of my picture, the period is 3 (do you agree?). Then what are the formulas in your reading giving? Come! Five states, three classes, surely you can do it... – Did Nov 01 '14 at 11:04
  • I can only guess that $C_0=\left{0\right}, C_1=\left{1,2\right}, C_2=\left{3,4\right}$. But guessing is not enough. Sorry, I do not see how to get there by thinking. ;( – mathfemi Nov 01 '14 at 11:07
  • OK, I asked for my second picture and you came back to the first picture, why not. I am sorry but your "I can only guess" cannot be true. Look at the definition of $C_n$ in your comment. Say $n=1$ and $j=4$, is $p^{(3k+1)}{04}$ positive for some integer $k$? Yes? No? No! Hence $4$ is not in $C_1$. Is $p^{(3k+2)}{04}$ positive for some integer $k$? Yes? No? Yes! Hence $4$ is in $C_2$. Surely you can do the same for the states $1$, $2$, and $3$, no? – Did Nov 01 '14 at 11:12
  • Using the definition in my comment I get $C_0=\left{1,2\right}, C_1=\left{0\right}$ and $C_{2}=\left{3,4\right}$. – mathfemi Nov 01 '14 at 11:23
  • Perfect (you started from state $1$ instead of state $0$ as in my explanations, but this works equally well). This answers your first comment. – Did Nov 01 '14 at 11:26
  • For this way then $i=2, j=3$ is no counterexample, right? But for example it is $p_{04}=0$, i.e. $n=1, m=2$ and then $m\equiv n+1\text{mod} 3$. So this is a counterexample here. Right? – mathfemi Nov 01 '14 at 11:34
  • Sorry, the decomposition in your previous comment is wrong (how one can achieve a wrong one, looking at the diagram, is beyond me...), actually $C_0={1,2}$ yields $C_1={3,4}$ and $C_2={0}$. Hence $p_{14}=0$ is a counterexample since $1\in C_0$ and $4\in C_1$. – Did Nov 01 '14 at 13:54
  • Sorry, but using the definition $C_n:=\left{j\in C|\exists ~m\equiv n\text{ mod }p: p_{j1}^{(m)}>0\right}$ I again get $C_0=\left{1,2\right}, C_1=\left{0\right}, C_2=\left{3,4\right}$. – mathfemi Nov 01 '14 at 14:15
  • 1
    Ah, I see, your comment defines the classes backwards (the condition $p_{j1}^{(m)}\gt0$ should read $p_{1j}^{(m)}\gt0$), sorry to have missed that. Then you will never get the statement in the question. – Did Nov 01 '14 at 14:23
  • So there is a mistake in our lecture and the condition has to be $p_{1j}^{(m)}>0$? Indeed. if I would have $C_0=\left{1,2\right}, C_1=\left{0\right}, C_2=\left{3,4\right}$ then for $i=1, j=3$ the Theorem would not hold, because then $2\neq 1\text{ mod }3$ but $p_{13}=1\neq 0$. – mathfemi Nov 01 '14 at 14:28