We study the entropy rate of a binary hidden Markov process (HMP) defined by observing the output of a binary symmetric channel whose input is a first-order binary Markov process. Despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. By presenting the probability of a sequence under the model as a product of random matrices, we show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the difficulty in its explicit computation. We apply the same product of random matrices to derive an explicit expression for a first order Taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel. The accuracy of the approximation is validated against empirical simulation results. We also extend our results to R?nyi's entropy of any order.
Citation:
Philippe Jacquet, Gadiel Seroussi, Wojciech Szpankowski, "On the Entropy of a Hidden Markov Process," dcc, pp.362, Data Compression Conference (DCC '04), 2004