On the entropy rate of hidden Markov processes observed through arbitrary memoryless channels

Jun Luo*, Dongning Guo

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

This paper studies the entropy rate of hidden Markov processes (HMPs) which are generated by observing a discrete-time binary homogeneous Markov chain through an arbitrary memoryless channel. A fixed-point functional equation is derived for the stationary distribution of an input symbol conditioned on all past observations. While the existence of a solution to the fixed-point functional equation is guaranteed by martingale theory, its uniqueness follows from the fact that the solution is the fixed point of a contraction mapping. The entropy or differential entropy rate of the HMP can then be obtained through computing the average entropy of each input symbol conditioned on past observations. In absence of an analytical solution to the fixed-point functional equation, a numerical method is proposed in which the fixed-point functional equation is first converted to a discrete linear system using uniform quantization and then solved efficiently. The accuracy of the computed entropy rate is shown to be proportional to the quantization interval. Unlike many other numerical methods, this numerical solution is not based on averaging over a sample path of the HMP.

Original languageEnglish (US)
Pages (from-to)1460-1467
Number of pages8
JournalIEEE Transactions on Information Theory
Volume55
Issue number4
DOIs
StatePublished - 2009

Funding

Manuscript received March 02, 2008; revised October 10, 2008. Current version published March 18, 2009. This work was supported in part by the National Science Foundation under Grant CCF-0644344 and by DARPA under Grant W911NF-07-1-0028. The material in this paper was presented in part at the 42nd Annual Conference on Information Sciences and Systems, Princeton, NJ, 2008. The authors are with the Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208 USA. Communicated by I. Kontoyiannis, Associate Editor for Shannon Theory. Color version of Figure 3 in this paper is available online at http://ieeexplore. ieee.org. Digital Object Identifier 10.1109/TIT.2009.2013030

Keywords

  • Blackwell's measure
  • Contraction mapping
  • Entropy rate
  • Filtering
  • Fixed-point functional equation
  • Hidden Markov process (HMP)

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'On the entropy rate of hidden Markov processes observed through arbitrary memoryless channels'. Together they form a unique fingerprint.

Cite this