  We consider the problem of reducing a first-order Markov chain on a large
alphabet to a higher-order Markov chain on a small alphabet. We present
information-theoretic cost functions that are related to predictability and
lumpability, show relations between these cost functions, and discuss
heuristics to minimize them. Our experiments suggest that the generalization to
higher orders is useful for model reduction in reliability analysis and natural
language processing.
