Skip to main navigation Skip to search Skip to main content

Information-preserving Markov aggregation

  • C. Bernhard Geiger
  • , C. Temmel

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We present a sufficient condition for a non-injective function of a Markov chain to be a second-order Markov chain with the same entropy rate as the original chain. This permits an information-preserving state space reduction by merging states or, equivalently, lossless compression of a Markov source on a sample-by-sample basis. The cardinality of the reduced state space is bounded from below by the node degrees of the transition graph associated with the original Markov chain. We also present an algorithm listing all possible information-preserving state space reductions, for a given transition graph. We illustrate our results by applying the algorithm to a bi-gram letter model of an English text. © 2013 IEEE.
Original languageEnglish
Title of host publicationInformation Theory Workshop (ITW)
DOIs
Publication statusPublished - 2013

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

  1. SDG 7 - Affordable and Clean Energy
    SDG 7 Affordable and Clean Energy

Fingerprint

Dive into the research topics of 'Information-preserving Markov aggregation'. Together they form a unique fingerprint.

Cite this