Periodicity of a communicating class

Question

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with discrete state space $E$ and transition matrix $P$. Let $C\subseteq E$ be a communicating class. Prove or disprove the following statement. $C$ is periodic with period $p>1$ if $C$ can be decomposed into a disjoint union of sets $C_0\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$. Distinguish between the cases when (a) $E$ is finite, (b) $E$ is countably infinite.

--

Do not see why it is necesary to distinguish between (a) $E$ finite and (b) $E$ countably infinite.

Anyway:

Assume that $p(C)=1$. Then $p(i)=1$ for a $i\in C$. Fix $i\in C$ and use it as a reference point for the disjoint sets $$ C_k:=\left\{j\in C| \exists~m\equiv k\text{ mod }p: p_{ij}^{(m)}>0\right\}. $$ These sets build a decomposition as described in the task. Because of this decomposition there exists exactly one $k\in\left\{0,1,...,p-1\right\}$ so that $p_{ii}^{(m)}>0$ for a $m\equiv k\text{ mod }p$.

Moreover it exists a $\tilde{n}\in\mathbb{N}$ so that $p_{ii}^{(n)}>0$ forall $n\geqslant\tilde{n}$, i.e. $$ S:=\left\{\tilde{n},\tilde{n}+1,\tilde{n}+2,\ldots\right\}\subseteq R(i):=\left\{n>0|p_{ii}^{(n)}>0\right\}. $$ Write $S$ as $$ S=\bigcup_{k=0}^{p-1}\left\{\ell\in S|\ell\equiv k\text{ mod }p\right\}. $$ Then $p_{ii}^{(s)}>0$ for all $s\in S$ implies that $i\in C_t$ for all $t\in\left\{0,1,...,p-1\right\}\setminus\left\{k\right\}$ contradicting that the sets $C_j, j\in\left\{0,1,...,p-1\right\}$ are disjoint.

So $p(C)>1$.

--- Again: Why is it necessary to distinguish between $E$ finite and $E$ countably infinite?

Answer 1

The following hints might be useful (in case my interpretation of your proof is correct).

I'm afraid your approach is not ok and this is presumably the reason that it seems not necessary to distinguish between a finite state space $E$ and a countably infinite $E$.

First let us formulate the proposition conveniently and then analyse it's logical structure.

Proposition: Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with discrete state space $E$ and transition matrix $P$. Let $C\subseteq E$ be a communicating class. Assume

• (i) $\ C$ can be decomposed into a disjoint union of sets $C_0\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$.

• (ii) $\ C$ is periodic with period $p>1$

then

\begin{align*} (\text{i})\Rightarrow(\text{ii}) \end{align*} Distinguish between the cases when (a) $E$ is finite, (b) $E$ is countably infinite.

---

Since your proof starts with:

Assume that $p(C)=1$. Then $p(i)=1$ for a $i\in C\ldots$

It seems you want to proof the proposition indirectly by showing that

$$\neg (\text{ii}) \Rightarrow \neg (\text{i})$$

The final argument of your proof is pointing out a contradiction according to the sets $C_j,j\in\{0,1,\ldots,p-1\}$ by showing that they are not disjoint, although they should be disjoint.

I think there are two problems using this argumentation.

(1) Since (i) is of the form $\exists(\text{i}.0):(\text{i}.1 \Rightarrow \text{i}.2)$ with

• (i.$0$) $\ C$ can be decomposed into a disjoint union of sets $C_0\cup\ldots\cup C_{p-1}$ in such a way that

• (i.$1$) $\ $if $i\in C_n$ and $j\in C_m$ with $m\neq n+1\text{ mod }p$

• (i.$2$) $\ $then $p_{ij}=0$

Observe, the negation of $(\text{i})$ is the negation of $\exists(\text{i}.0):\left(\text{i.1}\Rightarrow\text{i.2}\right)$ and therefore we have to show

$$\forall(\text{i}.0):\left(\text{i.1} \wedge \neg \text{i.2}\right)$$

So, in order to show $\neg (\text{i})$ we have to show that:

For all decompositions of $C$ into a disjoint union of sets $C_0\cup\ldots\cup C_{p-1}$ there are $n_0,m_0\in\{0,1,\ldots,p-1\}$ with $m_0\neq n_0+1\text{ mod }p$ and $i_0,j_0\in E$ with $i_0\in C_{n_0}$ and $j_0\in C_{m_0}$ so that $p_{i_0j_0}>0$.

Conclusion: Since your argumentation is different, you do not show the negation of $(i)$.

(2) Your approach with $p=1$ gives right from the beginning

\begin{align*} C_k:=&\left\{j\in C| \exists~m\equiv k\text{ mod }p: p_{ij}^{(m)}>0\right\}\\ =&\left\{j\in C| \exists~m\equiv k\text{ mod }1: p_{ij}^{(m)}>0\right\}\\ =&\left\{j\in C| \exists~m\equiv 0\text{ mod }1: p_{ij}^{(m)}>0\right\}\\ =&C \end{align*}

So, in fact your proof analyses always only the trivial decomposition $C=C_0$ which was presumably not your intention.

---

Note: I was also curious why we should differ between the finite and the countably infinite state space $E$. One reason could be, that a constructive proof for the finite case dealing with a finite transition matrix $P$ can't be easily generalised to a countably infinite transition matrix.

I found in Finite Markov Processes and Their Applications section 2.4.5 from Marius Iosifescu an instructive example how to constructively determine the period of a Markov Chain.

There he points to a downloadable book from R.B.Ash: Basic Probability Theory. You might want to have a look at chapter 7, Theorem 10, which is strongly related to your question. You might also want to have a look at chapter 7, example 2, which determines the period for a Markov chain with a finite state space. Finiteness is necessary there in order to terminate the constructive approach.

Note: According to the comments to your question I had a look at Markov Chains from R. Norris. I think that Theorem 1.8.4 on page 43 is the only one, which has a strong connection to your question.