Appendix A — Markov Chains
The following are some definitions related to Markov chains, which can be found in any introductory textbook to the topic1.
States \(i, j \in S\), are connected if \(\exists n > 0, m > 0 | P^n_{ij} > 0 \text{ and } P^m_{ji} > 0\). Note that this is an equivalence relation.
If \(C\) is such that \(\sum_{j \in C} p_{ij} = 1 \forall i \in C\), then it is called a closed communicating class.
If a chain has only one closed communicating class, it is called irreducable.
If \(i \in S, \sum_{n=1}^\infty P^n_{ii} \to \infty\), then the state is called recurrent. Equivalently, \(\sum_n F_n \to 1\) for recurrent nodes. If a chain is irreducible and one of its states is recurrent, all its states are recurrent, and thus the chain is called recurrent. If a chain is recurrent, then it has a stable measure \(\pi\) such that \(P\pi = \pi\). If \(\pi\) can be normalized to a stable distribution, the chain is called null recurrent.
A random variable \(T : \Omega \to {0, 1, ...} \cup {\infty}\) is a stopping time the event \(\{T=n\}\) depends only on \(X_0, X_1, \dots X_n\) for \(n = 0, 1, 2, \dots\)
For a state \(i \in S\), the Period is \(\gcd \{n\ge 0: p_{ii}^{(n)} > 0\}\). If the Period of the state is 1, then it is called aperiodic. For an irreducible chain, if one state is aperiodic, then all states are aperiodic, and the chain is referred to as aperiodic.
The state space of all irreducible chains can be partitioned into \(p\) disjoint sets
\[S = C_0 \cup C_1 \cup \dots \cup C_{d-1}\]
and set \(C_{nd+r} = C_r\), such that
- \(p^{(n)}_{ij} > 0\) only if \(i \in C_r\) and \(j \in C_{r+n}\) for some \(r\).
- \(p^{(nd)}_{ij} > 0\) for all sufficiently large \(n\), for all \(i, j \in C_r\), for all \(r\).
For a Markov chain \(P\) with stable distribution \(\pi\), \(P^*\) given by \(p^*_{ji} = \dfrac{\pi_{i}p_{ij}}{\pi_j}\) is the transition matrix of the time reversed Markov chain.
A positive recurrent, aperiodic chain is called an ergodic chain.