## Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability.(English)Zbl 1309.60077

Summary: A lumping of a Markov chain is a coordinatewise projection of the chain. We characterise the entropy rate preservation of a lumping of an aperiodic and irreducible Markov chain on a finite state space by the random growth rate of the cardinality of the realisable preimage of a finite-length trajectory of the lumped chain and by the information needed to reconstruct original trajectories from their lumped images. Both are purely combinatorial criteria, depending only on the transition graph of the Markov chain and the lumping function. A lumping is strongly $$k$$-lumpable, if and only if the lumped process is a $$k$$-th-order Markov chain for each starting distribution of the original Markov chain. We characterise strong $$k$$-lumpability via tightness of stationary entropic bounds. In the sparse setting, we give sufficient conditions on the lumping to both preserve the entropy rate and be strongly $$k$$-lumpable.

### MSC:

 60J10 Markov chains (discrete-time Markov processes on discrete state spaces) 60G17 Sample path properties 60G10 Stationary stochastic processes 94A17 Measures of information, entropy 65C40 Numerical analysis or methods applied to Markov chains
Full Text:

### References:

  Anderson, B. D. O. (1999). The realization problem for hidden Markov models. Math. Control Signals Systems 12, 80-120. · Zbl 0949.93015  Brown, P. F. et al. (1992). Class-based $$n$$-gram models of natural language. Comput. Linguist. 18, 467-479.  Blackwell, D. (1957). The entropy of functions of finite-state Markov chains. In Trans 1st Prague Conf. Inf. Theory, Statist. Decision Functions, (Liblice, 1956) . Publishing House of the Czechoslovak Academy of Sciences, Prague, pp. 13-20. · Zbl 0085.12401  Blackwell, D. and Koopmans, L. (1957). On the identifiability problem for functions of finite Markov chains. Ann. Math. Statist. 28, 1011-1015. · Zbl 0080.34901  Burke, C. J. and Rosenblatt, M. (1958). A Markovian function of a Markov chain. Ann. Math. Statist. 29, 1112-1122. · Zbl 0100.34402  Carlyle, J. W. (1967). Identification of state-calculable functions of finite Markov chains. Ann. Math. Statist. 38, 201-205. · Zbl 0171.16103  Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory , 2nd edn. John Wiley, Hoboken, NJ. · Zbl 1140.94001  Ephraim, Y. and Merhav, N. (2002). Hidden Markov processes. IEEE Trans. Inf. Theory 48, 1518-1569. · Zbl 1061.94560  Geiger, B. C. and Kubin, G. (2011). Some results on the information loss in dynamical systems. In Proc. IEEE Internat. Symp. Wireless Commun. Systems (ISWSC) , IEEE, New York, pp. 794-798, 2011. Extended version available at http://uk.arxiv.org/abs/1106.2404.  Geiger, B. C. and Temmel, C. (2013). Information-preserving Markov aggregation. In Proc. IEEE Information Theory Workshop (ITW) , IEEE, New York, pp. 258-262. Extended version available at http://uk.arxiv.org/ abs/1304.0920.  Gilbert, E. J. (1959). On the identifiability problem for functions of finite Markov chains. Ann. Math. Statist. 30, 688-697. · Zbl 0089.34503  Gray, R. M. (1990). Entropy and Information Theory . Springer, New York. · Zbl 0722.94001  Gurvits, L. and Ledoux, J. (2005). Markov property for a function of a Markov chain: a linear algebra approach. Linear Algebra Appl. 404, 85-117. · Zbl 1077.15017  Heiner, M., Rohr, C., Schwarick, M. and Streif, S. (2010). A comparative study of stochastic analysis techniques. In Proc. 8th Internat. Conf. Comput. Meth. Systems Biol. , ACM, New York, pp. 96-106.  Heller, A. (1965). On stochastic processes derived from Markov chains. Ann. Math. Statist. 36, 1286-1291. · Zbl 0139.34603  Henzinger, T. A., Mikeev, L., Mateescu, M. and Wolf, V. (2010). Hybrid numerical solution of the chemical master equation. In Proc. 8th Internat. Conf. Comput. Meth. Systems Biol. , ACM, New York, pp. 55-65.  Kemeny, J. G. and Snell, J. L. (1976). Finite Markov Chains . Springer, New York. · Zbl 0328.60035  Kieffer, J. C. and Rahe, M. (1981). Markov channels are asymptotically mean stationary. SIAM J. Math. Anal. 12, 293-305. · Zbl 0475.94008  Lindqvist, B. (1978). On the loss of information incurred by lumping states of a Markov chain. Scand. J. Statist. 5, 92-98. · Zbl 0377.62047  Parzen, E. (1999). Stochastic Processes (Classics Appl. Math. 24 ). Society for Industrial and Applied Mathematics, Philadelphia, PA.  Pinsker, M. S. (1964). Information and Information Stability of Random Variables and Processes . Holden-Day, San Francisco, CA. · Zbl 0125.09202  Rogers, L. C. G. and Pitman, J. W. (1981). Markov functions. Ann. Prob. 9, 573-582. · Zbl 0466.60070  Sarukkai, R. R. (2000). Link prediction and path analysis using Markov chains. Comput. Networks 33, 377-386.  Watanabe, S. and Abraham, C. T. (1960). Loss and recovery of information by coarse observation of stochastic chain. Inf. Control 3, 248-278. · Zbl 0094.32001  Wilkinson, D. J. (2006). Stochastic Modelling for Systems Biology . Chapman & Hall/CRC, Boca Raton, FL. · Zbl 1099.92004  Woess, W. (2009). Denumerable Markov chains. Generating Functions, Boundary Theory, Random Walks on Trees . European Mathematical Society, Zürich. · Zbl 1219.60001
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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.66282445,"math_prob":0.71703994,"size":6040,"snap":"2023-40-2023-50","text_gpt3_token_len":1851,"char_repetition_ratio":0.1355202,"word_repetition_ratio":0.057797164,"special_character_ratio":0.34139073,"punctuation_ratio":0.28089887,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9689221,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-10-04T06:25:03Z\",\"WARC-Record-ID\":\"<urn:uuid:9b316eb5-d426-4db7-8b2e-311aa60c53e1>\",\"Content-Length\":\"62626\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0060bc37-40de-4803-90e2-fb9f0ae3d528>\",\"WARC-Concurrent-To\":\"<urn:uuid:d8f749e9-44b1-47eb-9268-b4bc3bd817f6>\",\"WARC-IP-Address\":\"141.66.194.2\",\"WARC-Target-URI\":\"https://zbmath.org/?q=an:06408807\",\"WARC-Payload-Digest\":\"sha1:M3WYIXLWCWGKFD3TWKEJ5URLHTAPDB6O\",\"WARC-Block-Digest\":\"sha1:4KGWP232OMNAEBYOHESMXPFEW6XE64HZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233511361.38_warc_CC-MAIN-20231004052258-20231004082258-00684.warc.gz\"}"}