Topics in Markov Chains II
- Master Project
- Announcement date
- 09 Oct 2013
- Bernhard Geiger
- Research Areas
Recently, two papers treated state-space aggregation of Markov chains from an information-theoretic point-of-view: The work of Deng, Mehta and Meyn  minimizes a specific Kullback-Leibler divergence rate and connects the aggregation to graph-based methods, where the optimal bipartition turns out to coincide with the solution from spectral graph theory. Our work  minimizes a different Kullback-Leibler divergence rate and connects the aggregation with the phenomenon of lumpability and with the information bottleneck method. There are two projects/theses associated with this topic:
- It would be interesting to find out if also our proposed method in some way has a connection with spectral graph theory, at least in case of the bipartition problem. This topic will be a bit heavy on the theoretical side.
- It can be shown that the information bottleneck method is sub-optimal for the problem at hand. We have an idea to adapt the method to perform better; after implementation and testing of this method, a theoretical analysis shall investigate the possible improvements.
This work will be both theoretical and involves MATLAB simulations. A good background in probabilities would be good.
The work should be completed by August 2014.
: Deng, Mehta & Meyn: “Optimal Kullback-Leibler Aggregation via Spectral Theory of Markov Chains”, IEEE Trans. on Automatic Control, Link.
: Geiger, Petrov, Kubin & Koeppl: “Optimal Kullback-Leibler Aggregation via Information Bottleneck”, submitted, arXiv.