MIXING TIMES FOR UNIFORMLY ERGODIC MARKOV CHAINS

David Aldous and Laszlo Lovasz and Peter Winkler

Consider the class of discrete time, general state space
Markov chains which satisfy a ``uniform ergodicity under sampling" condition.
There are many ways to quantify the notion of ``mixing time", that
is time to approach stationarity from a worst initial state.
We prove results asserting equivalence (up to universal
constants) of different quantifications of mixing time.
This work combines three areas of Markov theory which are rarely connected:
the potential-theoretical characterization of optimal stopping times,
the theory of stability and convergence to stationarity for general-state
chains, and the theory surrounding mixing times for finite-state chains.