State Space Reduction without Information Loss

Seminar Type: Bachelorarbeit Telematik (4 SP)
Student: Markus Mayerwieser

Short Description

In modeling a system, one typically desires a model as simple and as accurate as possible. Often, due to their simplicity, discrete Markov chains are used for these purposes.

Assume now that we wish to reduce the state space of such a Markov model by representing sets of states by a single state. Unfortunately, in most cases the aggregated model is not Markov anymore. Conditions for preserving the Markov property are defined under the term lumpability and are typically too restrictive to be of practical use. However, we recently found conditions for an information-preserving aggregation such that the resulting process is a second-order Markov process [1].

In this thesis an algorithm shall be designed which performs this aggregation for a given Markov chain.

Results and Full Text

The project has been completed successfully. The full text is available here, and a follow-up project was started.


[1]: Geiger, Bernhard C. and Temmel, Christoph: "Lumpings of Markov Chains and Entropy Rate Loss", submitted, arXiv.