Markov property for a function of a Markov chain: A linear algebra approach (Q2484388)

The article addresses whether a probabilistic function of a finite homogeneous Markov chain still enjoys a Markov-type property, and gives a complete answer to this question using a linear algebra approach. The core of the approach is the concept of invariance of a set under a matrix, and the framework of this article is related to the so-called ``geometric approach'' in the control theory of linear dynamic systems. This allows the authors to derive a collection of new results under generic assumptions on the original Markov chain. In particular, they obtain a new criterion for a function of a Markov chain to be homogeneous. The authors also provide a deterministic polynomial-time algorithm for checking this criterion. Moreover, a non-standard notion of observability for a linear system will be used. This allows one to show that the set of all stochastic matrices for which the criterion holds is nowhere dense in the set of stochastic matrices.