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