On the entropy rate of a hidden Markov model

In this article, the computation of the entropy rate H(y) of a binary-valued stochastic process (Y₁, Y₂,...) which is a function of a stationary, time-invariant and irreducible Markov chain (X₁, X₂,..) is considered. The central idea of this article is to replace the summation over all words of length n by a summation over a complete set of prefixes (or prefixset for brevity). A prefixset W is a finite set of words (not necessarily of equal length) containing a unique prefix for each word of sufficient length. The method of prefixsets is of interest beyond computing the entropy rate. For the problem of estimating the next state of a Markov chain from observed output sequences, we can precompute a prefixset W of these sequences and associate a unique estimate of the state with each of the elements of W. The method also has a strong relation with variable-to-fixed length (Tunstall) codes. It replaces the set of all words of a given length by a prefixset of "more typical" words, effectively balancing the contributions of all words in the bounds.