# How to prove periodicity is a class property?

It is said that in a Markov chain, if state $i$ has period $d$ and state $i$ and $j$ are communicate, then state $j$ also has period $d$.

I wonder how to prove it?

-

One way to define the period of state $i$ is as the largest integer $p$ such that you can't go from $i$ to $i$ in any number of steps that isn't a multiple of $p$. Then you can show that you can go from $i$ to $i$ in $kp$ steps for all sufficiently large integers $k$.
Suppose state $i$ has period $p$ and communicates with state $j$. You can go from $i$ to $j$ in a certain number of steps, say $m$, and you can go from $j$ to $i$ in a certain number of steps, say $n$. But that means you can go from $i$ to $j$ and back to $i$ in $m+n$ steps, so $m+n$ must be a multiple of $p$, say $m+n = rp$. And then if you can go from $i$ to $i$ in $kp$ steps, you can go from $j$ to $j$ in $(k+r)p$ steps by going first from $j$ to $i$ in $m$ steps, then from $i$ to $i$ in $kp$ steps, then back to $j$ in $n$ steps. So the period of $j$ is at most $p$. Interchange $i$ and $j$ to see that the period of $j$ is at least $p$.
They are equivalent (assuming, of course, that it is possible to return from $i$ to $i$). Suppose $p$ is the period in my definition and $q$ is the period in your definition. Since any sufficiently large prime times $p$ is a return time, $q$ divides $p$. On the other hand, $q = gcd(t_1, \ldots, t_m)$ is a linear combination over the integers of $t_1, \ldots, t_m$ for some return times $t_1, \ldots, t_m$, from which you can show that every sufficiently large multiple of $q$ is a return time, and therefore $p$ divides $q$. –  Robert Israel Nov 22 '12 at 18:24
Hmm, that's a bit less obvious than I must have thought at the time. There is some return time, which must be a multiple of $p$, say $t = k_0 p$. Let $p_1, \ldots, p_m$ be the primes dividing $k_0$. For each $p_j$, there is a return time $k_j p$ such that $k_j$ is not divisible by $p_j$. So $gcd(k_0, k_1, \ldots, k_m) = 1$, which implies that every sufficiently large positive integer $k$ is the sum of nonnegative integer multiples of $k_0, \ldots, k_m$, and thus $kp$ is a return time. –  Robert Israel Nov 25 '12 at 7:07