# Prove the 2 definitions of the periodicity of Markov Chain are equivalent.

In many textbooks, there are basically 2 ways of defining the periodicity of Markov Chain. One is by partitioning the graph in to subgraph such that transition in one group of state leads to the other group of states; and the other definition is that $k=\gcd\{n:\mathbb{P}(X_n=i|X_0=i)>0\}$. How can you prove that these 2 definitions are actually equivalent?

For example, consider a finite irreducible Markov chain with period $\tau=2$. How can we show that the state space of the chain can be partitioned as $S=S_0\bigcup S_1$ such that $p_{ij}=0$ if $i,j\in S_0$ or $i,j\in S_1$?

I'll really appreciate if you can help me out, because I have thought it for a long time and couldn't come up with a good idea. :)

-
Look at Theorem 1.8.4 in section 1.8 of Norris's book on Markov chains here: statslab.cam.ac.uk/~james/Markov – Byron Schmuland Apr 18 '13 at 19:11
@ByronSchmuland +1. Excellent. – Did Apr 18 '13 at 20:49
@Did Thanks. Pointing to Norris's book is easier than typing out the answer. :) – Byron Schmuland Apr 18 '13 at 20:53
Byron,sorry for the late reply, thanks! It really helped me! – Cancan Apr 22 '13 at 20:08