The realization problem for hidden Markov models

If {X-t} is a finite-state Markov process, and {Y-t} is a finite-valued out put process with Yt+1 depending (possibly probabilistically) on X-t, then t he process pair is said to constitute a hidden Markov model. This paper con siders the realization question: given the probabilities of all finite-leng th output strings, under what circumstances and how can one construct a fin ite-state Markov process and a state-to-output mapping which generates an o utput process whose finite-length strings have the given probabilities? Aft er reviewing known results dealing with this problem involving Hankel matri ces and polyhedral cones, we develop new theory on the existence and constr uction of the cones in question, which effectively provides a solution to t he realization problem. This theory is an extension of recent theoretical d evelopments on the positive realization problem of linear system theory.