Short Description

Recently, we analyzed sufficient conditions for a Markov chain X and a function g, such that the projected process Y=g(X) not only has the same entropy rate (a measure of information) as X, but that it is also a Markov chain of second order [1,2]. The application of these results lies in state space reduction for Markov chains: Preserving the Markov property is desirable from a computational point-of-view, since Markov chains are simple to identify and simulate. Preserving the entropy rate is desirable too, since it ensures that the reduced model does not suffer from information loss. There are two projects/theses associated with this topic:

1. We identified a second condition, which is sufficient only for preserving the entropy rate. We believe that this second condition can be interpreted as a condition on a graph: Let X have N states, and build the set of N² tuples of states. Depending on whether the sufficient condition is fulfilled for a pair of tuples, these two tuples are connected via an edge. The cliques in this graph then should correspond to functiongs g for which the given Markov chain X can be aggregated without information loss. This allows for a relatively easy way to look for information-preserving reductions.
2. There are different, sufficient conditions for preserving the Markov property (although these do not preserve the entropy rate). It is interesting to find out how these sufficient conditions play together: If a set of states satisfies one, another set of states satisfies the other sufficient condition, is the output process Y still Markov?

Your Requirements

This work will be more on the theoretical side, MATLAB simulations will only be used for verification. Thus, a good background in probabilities would be good.

Additional Information

This work should be completed by August 2014.

References

[1]: Geiger, Bernhard C. and Temmel, Christoph: “Lumpings of Markov Chains and Entropy Rate Loss”, submitted, arXiv.
[2]: Geiger, Bernhard C. and Temmel, Christoph: “Information-Preserving Markov Aggregation”, presented at the IEEE Information Theory Workshop, arXiv.