Short Description

Recently, an information-preserving 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 information-preserving property, is inefficient: Specifically, by making use of a so-called 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 run-time compared to a MATLAB/Octave implementation.

The goal is to provide a well-documented tool for fellow researchers who are interested in Markov chain aggregation. Optionally, the implementation can be accompanied by a complexity analysis of the algorithm.

References

[1]: Geiger, Bernhard C. and Temmel, Christoph, “Information-Preserving Markov Aggregation”, in: Proc. IEEE Information Theory Workshop (ITW), Sevilla, September 2103, p. 258-262, 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.