Order estimation and sequential universal data compression of a hidden Markov source by the method of mixtures

We consider first the estimation of the order, i.e., the number of states, of a discrete-time finite-alphabet stationary ergodic hidden Markov source (HMS). Our estimator uses a description of the observed data in terms of a uniquely decodable code with respect to a mixture distribution, obtained by suitably mixing a parametric family of distributions on the observation space. This procedure avoids maximum likelihood calculations. The order estimator is shown to be strongly consistent with the probability of underestimation, decaying exponentially fast in the number n of observations, while the probability of overestimation does not exceed cn/sup -3/, where c is a constant. Next, we present a sequential algorithm for the uniquely decodable universal data compression of the HMS, which performs an on-line estimation of source order followed by arithmetic coding. This code asymptotically attains optimum average redundancy.>