Lifting Markov chains to speed up mixing

Abstract

There are several examples where the mixing time of a Markov chain can be reduced substantially, often to about its square root, by "lifting", i.e., by splitting each state into several states. In several examples of random walks on groups, the lifted chain not only mixes better, but is easier to analyze.