Identifiability of Hidden Markov Information Sources and Their Minimum Degrees of Freedom

If it is observed only a function of the state in a finite-state Markov chain, then the stochastic process is no longer Markovian in general. This type of information source is found widely and the basic problem of their identifiability has remained open, that is, the problem of showing when two different Markov chains generate the same stochastic process. The identifiability problem is completely solved by linear algebra, where a block structure of a Markov transition matrix plays a fundamental role, and from which the minimum degree of freedom for a source is revealed.