Conditions for reversibility of higher order Markov chains

Question

Consider a discrete time dynamical system on states $\{0, 1, 2 \}$. The one step transitions are not Markovian, but the 3rd order transitions from triples of states $(s_{t-2}, s_{t-1}, s_{t}) \rightarrow (s_{t-1}, s_{t}, s_{t+1})$ are Markovian. How do we define and check for traditional properties like reversibility for this 3rd order Markov chain? If the probability of $(0, 1, 2) \rightarrow (1, 2, 2)$ has positive weight then it appears that the process cannot satisfy detailed balance because the reverse transition $(1, 1, 2) \rightarrow (0, 1, 2)$ is impossible and would involve "changing history," so to speak. Does the definition of reversibility for higher order Markov chains involve "reversing the arrow of time" so that the transitions $(0, 1, 2) \rightarrow (1, 2, 2)$ and $(2, 2, 1) \rightarrow (2, 1, 0)$ satisfy detailed balance? Or are higher order Markov chains just never reversible?

I would also greatly appreciate any pointers to references.

Answer 1

The reversibility in the Markov chain context means the following symmetry, under the stationary distribution, \begin{equation} \mathbb{P}(s_1=a_1,\dots,s_n=a_n)=\mathbb{P}(s_1=a_n,\dots,s_n=a_1).\tag{1} \end{equation} Let's generalize this to your situation. Consider the Markov chain on triples, and for a triplet $a=(a_1,a_2,a_3),$ denote by $\bar{a}$ its time reversal $\bar{a}=(a_3,a_2,a_1).$ Assume that for some probability distribution $\mu$ on these triplets, we have for all $a,b$ $$ \mu(a)P_{a,b}=\mu(b)P_{\bar{b},\bar{a}}.\tag{2} $$
This is not the same as the Markov reversibility condition for triplets, but the theory goes much in the same way. As in a Markovian case, $$\sum_a\mu(a)P_{a,b}=\mu(b)\sum_aP_{\bar{b},\bar{a}}=\mu(b),$$ so $\mu$ is in fact a stationary distribution. Also, $$\sum_a\mu(\bar{a})P_{a,b}=\mu(\bar{b})\sum_aP_{\bar{b},\bar{a}}=\mu(\bar{b}),$$ meaning that $\mu(\bar{a})$ is also a stationary distribution. Under the standard irreducibility condition, the stationary distribution is unique, so we in fact have $\mu(\bar{a})=\mu(a).$ Now, the desired property (1) directly follows from (2). Finally, as in the Markovian case, (2) can be solved by breadth-first search, which succeeds if and only if the analog $$ \prod_{i=0}^n P_{a^{(i)},a^{(i+1)}}=\prod_{i=0}^nP_{\overline{a^{(i+1)}},\overline{a^{(i)}}},\quad a^{(0)}=a^{(n+1)}. $$ of the cycle condition holds true.