Exponential Bounds for Convergence of Entropy Rate Approximations in Hidden Markov Models Satisfying a Path-Mergeability Condition

Abstract

A hidden Markov model (HMM) is said to have path-mergeable states if for any two states i,j there exists a word w and state k such that it is possible to transition from both i and j to k while emitting w. We show that for a finite HMM with path-mergeable states the block estimates of the entropy rate converge exponentially fast. We also show that the path-mergeability property is asymptotically typical in the space of HMM topolgies and easily testable.

arXiv comment23 pages, 1 figure