UP | HOME

(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:

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)\).

3 Useful links

Created: 2021-09-14 Tue 21:44