| In the theory of finite Markov chains, mixing times which measure the speed of convergence to the stationary distribution are very important. We study the techniques for obtaining bounds on mixing times.; We also study the behavior of mixing measures when we lift a chain, i.e. split each state into several states. In particular, there are examples where the mixing time of a Markov chain can be reduced substantially by lifting, often to about its square root.; We characterize the best mixing time achievable through lifting in terms of multicommodity flows. We show that for any chain, there exists a lifting which is optimal for the mixing time. If the lifted chain is time-reversible, then the gain is much smaller, at most a factor of log(1/pi0), where pi0 is the smallest stationary probability of any state. We give an example showing that a gain of a factor of log(1/pi0), log log(1/pi0), is possible, which disproves a conjecture of Aldous and Fill.; We apply the lifting technique to random walks on groups to reduce the mixing time. An application to uniformly generating a linear extension of some special posets is also presented. |
