Ed Crane

Lumpings and Couplings of Markov Chains

Let X_n be a discrete time homogeneous Markov chain with state space A, and let f be a function mapping A to another set B. Typically, the sequence f(X_n) is not a Markov chain. But in some interesting cases it is also homogeneous Markov chain, for certain choices of the distribution of X_0. In that case, we say that f is a weak lumping of X. In this talk I will discuss the theory of lumpings and two new applications.

The first application is joint work with Ander Holroyd and Erin Russell. Suppose you are given two homogeneous Markov chains with finite state spaces. You want to couple them subject to some constraints on the allowed coupled states and transitions, and you want the coupled process to be a homogeneous Markov chain. Can you decide whether this is possible, and if it is, how can you find such a coupling? We illustrate with examples involving forest fires, random walks on graphs, and queueing networks.

The second application is joint work with Alvaro Gutierrez, Erin Russell, and Mark Wildon. Define an irreducible random walk X_n on a finite group G, by letting X_0 be uniform on G and then setting

X_{n+1} = X_n g_n ,

where (g_n) is an i.i.d. sequence of elements of G, independent of X_0. We use representation theory to determine all the possible distributions of g_1 for which the sequence of left cosets (X_n H) is a homogeneous Markov chain. Such sequences arise naturally in problems about card shuffling and pop-o-matic dice rollers.