×

Entropy of hidden Markov processes via cycle expansion. (English) Zbl 1163.94005

Summary: Hidden Markov Processes (HMP) is one of the basic tools of the modern probabilistic modeling. The characterization of their entropy remains however an open problem. Here the entropy of HMP is calculated via the cycle expansion of the zeta-function, a method adopted from the theory of dynamical systems. For a class of HMP this method produces exact results both for the entropy and the moment-generating function. The latter allows to estimate, via the Chernoff bound, the probabilities of large deviations for the HMP. More generally, the method offers a representation of the moment-generating function and of the entropy via convergent series.

MSC:

94A17 Measures of information, entropy
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Rabiner, L.R.: Proc. IEEE 77, 257–286 (1989) · doi:10.1109/5.18626
[2] Ephraim, Y., Merhav, N.: IEEE Trans. Inf. Theory 48, 1518–1569 (2002) · Zbl 1061.94560 · doi:10.1109/TIT.2002.1003838
[3] Crouse, M., Nowak, R., Baraniuk, R.: IEEE Trans. Signal Process. 46, 886 (1998) · doi:10.1109/78.668544
[4] Koski, T.: Hidden Markov Models for Bioinformatics. Kluwer Academic Publishers, Dordrecht (2001) · Zbl 0983.92001
[5] Baldi, P., Brunak, S.: Bioinformatics. MIT Press, Cambridge (2001) · Zbl 0992.92024
[6] Ash, R.: Information Theory. Interscience Publishers, New York (1965) · Zbl 0141.34904
[7] Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (1991) · Zbl 0762.94001
[8] Blackwell, D.: The entropy of functions of finite-state Markov chains. In: Trans. First Prague Conf. Inf. Theory, Statistical Decision Functions, Random Processes, p. 13. Pub. House Chechoslovak Acad. Sci., Prague (1957) · Zbl 0085.12401
[9] Stratonovich, R.L.: Information Theory. Sovietskoe Radio, Moscow (1976). (in Russian)
[10] Rezaeian, M.: Hidden Markov process: a new representation, entropy rate and estimation entropy. arXiv:cs.IT/0606114 (2006)
[11] Birch, I.J.: Ann. Math. Stat. 33, 930 (1962) · Zbl 0109.36301 · doi:10.1214/aoms/1177704462
[12] Jacquet, P., Seroussi, G., Szpankowski, W.: On the entropy of a hidden Markov process. In: Int. Symp. Inf. Theory, p. 10. Chicago, IL, 2004 · Zbl 1142.94004
[13] Holliday, T., Goldsmith, A., Glynn, P.: IEEE Trans. Inf. Theory 52, 3509 (2006) · Zbl 1309.94062 · doi:10.1109/TIT.2006.878230
[14] Ordentlich, E., Weissman, T.: IEEE Trans. Inf. Theory 52, 19 (2006) · Zbl 1317.94029 · doi:10.1109/TIT.2005.860432
[15] Egner, S. et al.: On the entropy rate of a hidden Markov model. In: Int. Symp. Inf. Theory, p. 12. Chicago, IL, 2004
[16] Zuk, O., Kanter, I., Domany, E.: J. Stat. Phys. 121, 343 (2005) · Zbl 1090.60079 · doi:10.1007/s10955-005-7576-y
[17] Zuk, O., Kanter, I., Domany, E., Aizenman, M.: IEEE Signal Process. Lett. 13, 517 (2006) · doi:10.1109/LSP.2006.874466
[18] Chigansky, P.: The entropy rate of a binary channel with slowly varying input. arXiv:cs/0602074
[19] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New Jersey (1985) · Zbl 0576.15001
[20] Kingman, J.F.C.: Ann. Probab. 1, 883 (1973) · Zbl 0311.60018 · doi:10.1214/aop/1176996798
[21] Steele, J.M.: Ann. de l’I.H.P. B 25, 93 (1989)
[22] Crisanti, A., Paladin, G., Vulpiani, A.: Products of random matrices in statistical physics. In: Springer Series in Solid State Sciences, vol. 104. Springer, Berlin (1993) · Zbl 0784.58003
[23] Goldsheid, L.Y., Margulis, G.A.: Russ. Math. Surv. 44, 11 (1989) · Zbl 0705.60012 · doi:10.1070/RM1989v044n05ABEH002214
[24] Orszag, S.A., Sulem, P.L., Goldirsch, I.: Physica D 27, 311 (1987) · Zbl 0656.34045 · doi:10.1016/0167-2789(87)90034-0
[25] Kontorovich, L.: Measure concentration of hidden Markov processes. arXiv:math/0608064 (2006)
[26] Artuso, R., Aurell, E., Cvitanovic, P.: Nonlinearity 3, 325 (1990) · Zbl 0702.58064 · doi:10.1088/0951-7715/3/2/005
[27] Cvitanovic, P.: Phys. Rev. Lett. 61, 2729 (1988) · doi:10.1103/PhysRevLett.61.2729
[28] Ruelle, D.: Statistical Mechanics, Thermodynamic Formalism. Addison-Wesley, Reading (1978) · Zbl 0401.28016
[29] Mainieri, R.: Chaos 2, 91 (1992) · Zbl 1055.82518 · doi:10.1063/1.165903
[30] Aurell, E.: J. Stat. Phys. 58, 967 (1990) · Zbl 0713.58045 · doi:10.1007/BF01026559
[31] Nielsen, J.: Lyapunov exponents for products of random matrices. Available at http://citeseer.ist.psu.edu/438423.html
[32] Arnold, L., Gundlach, V.M., Demetrius, L.: Ann. Appl. Probab. 4, 859 (1994) · Zbl 0818.15015 · doi:10.1214/aoap/1177004975
[33] Peres, Y.: Ann. Inst. H. Poincare Probab. Statist. 28, 131 (1992)
[34] Han, G., Markus, B.: IEEE Trans. Inf. Theory 52, 5251 (2006) · Zbl 1309.62021 · doi:10.1109/TIT.2006.885481
[35] Gurvits, L., Ledoux, J.: Linear Algebra and Applications 404, 85 (2005) · Zbl 1077.15017 · doi:10.1016/j.laa.2005.02.007
[36] Petersen, K.: Lectures on Ergodic Theory. Available from http://www.math.unc.edu/Faculty/petersen/lecturespdf.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.