(markov chains) aperiodicity
Let \(P\) be the transition matrix. Then, the period of state \(i\) is: \[\gcd\{n \in \mathbb{N}^{+} \mid P^n_{ii} > 0\}\] (see greatest common denominator).
Or in different words: the smallest number \(d\) such that \(d \nmid n \Rightarrow P^n_{ii} = 0\).
A state \(i\) communicates with \(j\), \(i \leftrightarrow j\), if:
- \(i\) is reachable from \(j\), \(j \rightarrow i\). That is there is some \(n\) such that \(P_{ij}^n > 0\)
- \(j\) is reachable from \(i\) \(i \rightarrow j\)
1. Comments
Imagine a chain \(A\rightarrow B \rightarrow C \rightarrow A\). Then, if I start in \(A\), I will only return to \(A\) on steps that are divisible by 3. This is why such a chain can't reach a stationary distribution from any starting place.
2. Properties
All states which communicate are in a communicating class.
2.1. All states in a communicating class have the same period
Or, if \(x \leftrightarrow y\), then \(d(x) = d(y)\)
2.1.1. Proof
\(x\) and \(y\) communicate. So \(P(x,y)^n > 0\) and \(P(y,x)^m > 0\) for some \(m,n\). Then, \(P(x,x)^{m+n} \geq P(x,y)^nP(y,x)^m > 0\). For this step, remember that \(P(x,y)^n\) means "how much probability flows from \(x\) to \(y\) in \(n\) steps". So \(d(x) \mid (m+n)\). Now, let \(k\) be some number where \(P(y,y)^k > 0\). Then, \(P(x,x)^{m+k+n} \geq P(x,y)^nP(y,y)^kP(y,x)^m > 0\). So \(d(x) \mid k\). Then, \(d(x)\) divides every \(k\) where \(P(y,y)^k > 0\). So \(d(x) \mid d(y)\). By going the other way, we get \(d(y) \mid d(x)\), so \(d(x) = d(y)\).