# 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?

-

## 1 Answer

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$.

-

I know there is another definition of period using the GCD of all returning times. I don't think this two definition is equivalent. – hxhxhx88 Nov 22 '12 at 12:57
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
why 'any sufficiently large prime times p is a return time'? Why can we have the multiple is a prime? – hxhxhx88 Nov 25 '12 at 5:17
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 76, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9661269783973694, "perplexity_flag": "head"}