Title :
On the entropy of a hidden Markov process
Author :
Jacquet, Philippe ; Seroussi, Gadiel ; Szpankowski, Wojciech
Author_Institution :
INRIA, Rocquencourt, France
Abstract :
In this paper 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 is studied. 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, and show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the difficulty in its explicit computation. 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 is applied. The accuracy of the approximation is validated against empirical simulation results and also extends the results to Renyi´s entropy of any order.
Keywords :
Lyapunov matrix equations; discrete time systems; entropy; hidden Markov models; memoryless systems; random sequences; telecommunication channels; HMP; Lyapunov exponent; Renyi entropy; binary hidden Markov process; binary symmetric channel; entropy rate; first order Taylor approximation; first-order binary Markov process; random matrix; Character recognition; Computational modeling; Data compression; Entropy; Hidden Markov models; Markov processes; Memoryless systems; Speech recognition; Symmetric matrices; USA Councils;
Conference_Titel :
Data Compression Conference, 2004. Proceedings. DCC 2004
Print_ISBN :
0-7695-2082-0
DOI :
10.1109/DCC.2004.1281481