Project Type:
Student Project
Student:
Markus Mayerwieser
Mentor: Bernhard Geiger

Recently, an informationpreserving aggregation method for Markov chains has been developed and implemented [1]. One of the major drawbacks of this implementation is that the algorithm, which tests all partitions if they satisfy the informationpreserving property, is inefficient: Specifically, by making use of a socalled refinement property to reduce computational complexity, the algorithm tests several partitions multiple times.
This student project should overcome this problem by integrating the refinement property into standard, efficient partitioning algorithms, such as the one introduced in [2], thus guaranteeing that every possible partition is checked only once. For further reduction of computational complexity, the concept of admissible pairs from [1] should be included in the new algorithm too. Finally, the algorithm should be implemented in C++ or similar, to decrease runtime compared to a MATLAB/Octave implementation.
The goal is to provide a welldocumented tool for fellow researchers who are interested in Markov chain aggregation. Optionally, the implementation can be accompanied by a complexity analysis of the algorithm.
[1]: Geiger, Bernhard C. and Temmel, Christoph, "InformationPreserving Markov Aggregation", in: Proc. IEEE Information Theory Workshop (ITW), Sevilla, September 2103, p. 258262, arXiv.
[2]: Semba, Ichiro, "An Efficient Algorithm for Generating all Partitions of the Set {1, 2, ..., n}", in: Journal of Information Processing, vol. 7, no. 1, March 1984.