3
$\begingroup$

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 Answers 1

1

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

  • 0
    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.2012-11-25