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

In this paper, we address whether a (probabilistic) function of a finite homogeneous Markov chain still enjoys a Markov-type property. We propose a complete answer to this question using a linear algebra approach. At the core of our approach is the concept of invariance of a set under a matrix. In that sense, the framework of this paper is related to the so-called geometric approach in control theory for linear dynamical systems. This allows us to derive a collection of new results under generic assumptions on the original Markov chain. In particular, we obtain a new criterion for a function of a Markov chain to be a homogeneous Markov chain. We 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 our criterion holds, is nowhere dense in the set of stochastic matrices. (c) 2005 Elsevier Inc. All rights reserved.