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

Jun Luo; Dongning Guo

doi:10.1109/TIT.2009.2013030

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

Jun Luo^*, Dongning Guo

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	1460-1467
Number of pages	8
Journal	IEEE Transactions on Information Theory
Volume	55
Issue number	4
DOIs	https://doi.org/10.1109/TIT.2009.2013030
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

Access to Document

10.1109/TIT.2009.2013030

Cite this

@article{e294fbd4b0794b0588a45e05dea12afb,

title = "On the entropy rate of hidden Markov processes observed through arbitrary memoryless channels",

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.",

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

author = "Jun Luo and Dongning Guo",

note = "Funding Information: 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",

year = "2009",

doi = "10.1109/TIT.2009.2013030",

language = "English (US)",

volume = "55",

pages = "1460--1467",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "4",

}

TY - JOUR

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

AU - Luo, Jun

AU - Guo, Dongning

N1 - Funding Information: 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

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Blackwell's measure

KW - Contraction mapping

KW - Entropy rate

KW - Filtering

KW - Fixed-point functional equation

KW - Hidden Markov process (HMP)

UR - http://www.scopus.com/inward/record.url?scp=64249151746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=64249151746&partnerID=8YFLogxK

U2 - 10.1109/TIT.2009.2013030

DO - 10.1109/TIT.2009.2013030

M3 - Article

AN - SCOPUS:64249151746

SN - 0018-9448

VL - 55

SP - 1460

EP - 1467

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 4

ER -

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

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this