×

zbMATH — the first resource for mathematics

Entropy at a weight-per-symbol and embeddings of Markov chains. (English) Zbl 0705.28012
Given a finite directed graph and a vector-valued labelling f of its edges, we give a formula for the growth rate of the number of cycles whose average f-value equals a prescribed number. We use this to prove a generalization of Krieger’s imbedding theorem (a coding theorem for topological Markov chains) to probabilistic Markov chains.
Reviewer: B.Marcus

MSC:
28D20 Entropy and other invariants
94A17 Measures of information, entropy
94A24 Coding theorems (Shannon theory)
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Adler, R., Marcus, B.: Topological entropy and equivalence of dynamical systems. Mem. Am. Math. Soc.219 (1979) · Zbl 0412.54050
[2] Boyle, M.: Lower entropy factors of sofic systems. Ergodic Theory and Dyn. Syst.4, 541-557 (1984) · Zbl 0529.28014
[3] Csisz?r, I., K?rner, J.: Information theory: coding theorems, for discrete memorless systems. New York: Academic Press 1981
[4] McEliece, R., Popovi?, L.: The capacity-cost function of a noiseless channel with several cost constraints. (Preprint)
[5] Fellgett, R., Parry, W.: Endomorphisms of a Lebesgue space II. Bull. Lond. Math. Soc.7, 151-158 (1975) · Zbl 0305.28009 · doi:10.1112/blms/7.2.151
[6] Friedland, S.: Limit eigenvalues of nonnegative matrices. Linear Algebra Appl.74, 173-178. · Zbl 0588.15015
[7] Handelman, D.: Positive polynomials, convex integral polytopes, and a random walk problem. (Lecture Notes in Math., vol. 1282) Berlin-Heidelberg-New York: Springer 1987 · Zbl 0654.46059
[8] Justesen, J., Hoholdt, T.: Maxentropic Markov chains. IEEE Trans. Inf. Theory30 665-667 (1984) · Zbl 0545.60064 · doi:10.1109/TIT.1984.1056939
[9] Karabed, R., Neuhoff, D., Khayrallah, A.: The capacity of costly noiseless channels. Preprint
[10] Kitchens, B., Tuncel, S.: On measures induced on subsystems. (Lectures Notes in Math. vol. 1342, pp. 455-464). Berlin-Heidelberg-New York: Springer 1988 · Zbl 0659.28012
[11] Krieger, W.: On the subsystems of topological Markov chains. Ergodic Theory and Dyn. Syst.2, 195-202 (1982) · Zbl 0508.54032
[12] Krieger, W., Marcus, B., Tuncel, S.: On automorphism of Markov chains. (Preprint) · Zbl 0763.28013
[13] Lalley, S.: Distribution of periodic orbits of symbolic and Axiom A flows. Adv. Appl. Math.8, 154-193 (1987) · Zbl 0637.58013 · doi:10.1016/0196-8858(87)90012-1
[14] Lanford, O.: Entropy and equilibrium states in classical statistical mechanics. (Lecture Notes in Physics, vol. 20, pp. 1-113). Berlin-Heidelberg-New York: Springer 1973
[15] Lind, D.: Perturbations of shifts of finite type. Preprint · Zbl 0676.58045
[16] Marcus, B., Tuncel, S.: The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains. Ergodic Therory and Dyn. Syst. (to appear) · Zbl 0725.60071
[17] Parry, W., Schmidt, K.: A note on cocycles of unitary representations. Proc. Am. Math. Soc.55, 185-190 (1976) · Zbl 0329.22008 · doi:10.1090/S0002-9939-1976-0393336-0
[18] Parry, W., Schmidt, K.: Natural coefficients and invariants for Markov shifts. Invent. Math.76, 15-32 (1984) · Zbl 0563.28008 · doi:10.1007/BF01388488
[19] Parry, W., Tuncel, S.: On the classification of Markov chains by finite equivalence. Ergodic Theory and Dyn. Syst.1, 303-335 (1981) · Zbl 0485.60063
[20] Parry, W., Tuncel, S.: On the stochastic and topological structure of Markov chains. Bull. Lond. Math. Soc.14, 16-27 (1982) · Zbl 0481.28015 · doi:10.1112/blms/14.1.16
[21] Parry, W., Tuncel, S.: Classification Problems in Ergodic Theory. (LMS Lecture Notes, vol. 67). Cambridge: Cambridge Univ. Press 1982 · Zbl 0487.28014
[22] Rockafellar, T.: Convex analysis. Princeton: Princeton Univ. Press 1970 · Zbl 0193.18401
[23] Ruelle, D.: Thermodynamic formalism. Reading, MA: Addison-Wesley 1978 · Zbl 0401.28016
[24] Seneta, E.: Non-negative matrices and Markov chains. Berlin-Heidelberg-New York: Springer 1981 · Zbl 0471.60001
[25] Tuncel, S.: Conditional pressure and coding. Isr. J. Math.39, 101-112 (1981) · Zbl 0472.28016 · doi:10.1007/BF02762856
[26] Tuncel, S.: A dimension, dimension modules, and Markov chains. Proc. Lond. Math. Soc.46, 100-116 (1983) · Zbl 0544.28011 · doi:10.1112/plms/s3-46.1.100
[27] Walters, P.: An introduction to ergodic theory. (GTM vol. 79). Berlin-Heidelberg-New York: Springer 1982 · Zbl 0475.28009
[28] Williams, R.: Classification of shifts of finite type. Ann. Math.98, 120-153 (1973); (Errata) Ann. Math.99, 380-381 (1974) · Zbl 0282.58008 · doi:10.2307/1970908
[29] Csiszar, I., Cover, T., Choi, B.: Conditional limit theorems under Markov conditioning, IEEE-Information Theory,33, 788-801 (1987) · Zbl 0628.60037 · doi:10.1109/TIT.1987.1057385
[30] Davisson, L., Longo, G., Sgarro, A.: The error exponent for the noiseless encoding of finite ergodic Markov sources. IEEE-Information Theory,27, 431-438 (1981) · Zbl 0492.94006 · doi:10.1109/TIT.1981.1056377
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.