Approximations for the entropy rate of a hidden Markov process
Erik Ordentlich, Tsachy Weissman · 2005
Let {Xt} be a stationary finite-alphabet Markov chain and {Zt} denote its noisy version when corrupted by a discrete memoryless channel. We present an approach to bounding the entropy rate of {Zt} by the construction and study of a related measure-valued Markov process. To illustrate its efficacy, we specialize it to the case of a BSC-corrupted binary Markov chain. The bounds obtained are sufficiently tight to characterize the behavior of the entropy rate in asymptotic regimes that exhibit a "concentration of the support". Examples include the 'high SNR', 'low SNR', 'rare spikes', and 'weak dependence' regimes. Our analysis also gives rise to a deterministic algorithm for approximating the entropy rate, achieving the best known precision-complexity tradeoff, for a significant subset of the process parameter space