State Space Reduction without Information Loss
- Bachelor Project
- Announcement date
- 15 Feb 2012
- Markus Mayerwieser
- Bernhard Geiger
- Research Areas
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 .
In this thesis an algorithm shall be designed which performs this aggregation for a given Markov chain.
Results and Full Text
: Geiger, Bernhard C. and Temmel, Christoph: “Lumpings of Markov Chains and Entropy Rate Loss”, submitted, arXiv.