Bounds on Convergence of Entropy Rate Approximations in Hidden Markov Processes

ABSTRACT: There is no general closed form expression for the entropy rate of a hidden Markov process. However, the finite length block estimates h(t) often converge to the true entropy rate h quite rapidly. We establish exponential bounds on the rate of convergence of the block estimates for finite hidden Markov models under several different conditions, including exactness, unifilarity, and a flag-state condition. In the case of unifilar hidden Markov models, we also give exponential bounds on the L₁ and a.s. decay of the state uncertainty U_t.