I'm a researcher at Graz University of Technology working in applied information theory (with a data science flavor).
I love math, all things entropy, and working in small teams. Networking is the best part of academic conferences - I'm a people person!
When a Function of Markov Chain is Markov
Markov chains are popular models in science and engineering because of their analytical simplicity: The probability distribution of the future state depends only on the present state. This Markov property in general does not hold if we look at a function of the Markov chain. Indeed, a function of a Markov chain need not be a Markov chain of any (higher) order. The rare scenario in which the Markov property is preserved is called "lumpability", and characterizing conditions under which this scenario occurs is of both theoretical and practical interest.
Abstract: In the literature, the notions of lumpability and time reversibility for large Markov chains have been widely used to efficiently study the functional and non-functional properties of computer systems. In this paper we explore the relations among different definitions of lumpability (strong, exact and strict) and the notion of time-reversed Markov chain. Specifically, we prove that an exact lumping induces a strong lumping on the reversed Markov chain and a strict lumping holds both for the forward and the reversed processes. Based on these results we introduce the class of \(\lambda \rho \)-reversible Markov chains which combines the notions of lumping and time reversibility modulo state renaming. We show that the class of autoreversible processes, previously introduced in Marin and Rossi (Proceedings of the IEEE 21st international symposium on modeling, analysis and simulation of computer and telecommunication systems MASCOTS, pp. 151–160, 2013), is strictly contained in the class of \(\lambda \rho \)-reversible chains.
Pub.: 31 Mar '16, Pinned: 26 Sep '17
Abstract: A lumping of a Markov chain is a coordinate-wise 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, iff 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.
Pub.: 20 Apr '15, Pinned: 26 Sep '17
Abstract: Necessary and sufficient conditions for identifying strong lumpability in Markov chains are presented. We show that the states in a lump necessarily correspond to identical elements in eigenvectors of the dual transition matrix. If there exist as many dual eigenvectors that respect the necessary condition as there are lumps in the aggregation, then the condition is also sufficient. The result is demonstrated with two simple examples.
Pub.: 09 Apr '08, Pinned: 26 Sep '17
Join Sparrho today to stay on top of science
Discover, organise and share research that matters to you