期刊
THEORETICAL COMPUTER SCIENCE
卷 395, 期 2-3, 页码 203-219出版社
ELSEVIER
DOI: 10.1016/j.tcs.2008.01.012
关键词
hidden Markov process; Shannon entropy; Renyi entropy; product of random matrices; top Lyapunov exponent; spectral representation of matrices
资金
- NIGMS NIH HHS [R01 GM068959, R01 GM068959-01] Funding Source: Medline
We study the entropy rate of a 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, one can see that the entropy rate sought is equal to a top Lyapunov exponent of the product. This offers an explanation for the elusiveness of explicit expressions for the HMP entropy rate, as Lyapunov exponents are notoriously difficult to compute. Consequently, we focus on asymptotic estimates, and apply the same product of random matrices to derive an explicit expression for a 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 higher-order Markov processes and to Renyi entropies of any order. (c) 2008 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据