On classification of states in higher order Markov chains (Q6149173)

The paper analyses \textit{higher-order} Markov chains. Precisely, the future evolution of an \(m\)-th order Markov chain given its current state may depend on the previous \(m-1\) states. An example of a second-order Markov chain is the \textit{non-backtracking simple random walk} on a finite graph: that chain chooses its next state uniformly from its neighours except that it is not allowed to return to the state it was just at (ie, `backtrack'). The main contribution of the paper is to introduce a scheme to classify states in a general higher-order Markov chains, with classification being in the sense of being able to reach one state from another (see Definition 3.1). This concept of `reachability' is shown to be an equivalence relation (see Theorem 3.2). Some properties for each type of state are established, such as equivalent forms of ergodicity and definitions of recurrence and transience and some consequences. Finally, some interesting differences between the first- and higher-order cases -- in particular, in the sense of characterisations of recurrence -- are illustrated by examples (see Section 4).