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 language | English (US) |
---|---|
Pages (from-to) | 1460-1467 |
Number of pages | 8 |
Journal | IEEE Transactions on Information Theory |
Volume | 55 |
Issue number | 4 |
DOIs | |
State | Published - 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