Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.