Appendix D — Proof of Reset Markov Chains Being Aperiodic

Given an irreducible Markov chain with transition matrix \(P\) with state space \(S\), \(s_r \in S\) and \(0 < \gamma < 1\), define the reset Markov chain to \(s_r\) w.p \(\gamma\) as the Markov chain given by the transition matrix \(P^* =(1-\gamma) P + \gamma R\), where \([R_{ij}] = \begin {cases} 1, & j = s_r\\ 0, & otherwise \end{cases}\) on state space \(S\). Note that this is a well-defined irreducible Markov chain.

Let the period of \(P^*\) be \(d\). Therefore, we can partition the state space into 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\). Let \(s \in C_k, s\neq s_r\) for some \(k\). Since \(p^*_{s s_r} = p_{s s_r} + \gamma > 0\), \(s_r\) must lie in \(C_{k+1}\). Since this holds for all \(k\), there can at most be two \(C\)s, one with \(s_r\) and the other with the rest of the nodes. Finally, if \(p_{ij} > 0\) for any \(i,j \in S/\{s_r\}\), they must lie in different classes, or there must be only one class. Since the former would create a contradiction, we must have that \(d=1\) and \(P^*\) is aperiodic.

If no such \(i,j\) exist, then \(P\) must be a star network. While in the current formalism, the self loop at \(s_r\) renders the proof almost trivial, we have provided a proof which shows aperiodicity even if \(P*\) be modified to remove the self loop. In such a case, barring the star network, all other irreducible graphs follow this proof.