More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and, regardless of the initial state, the time-t distribution of the chain converges to π as t tends to infinity.
Mixing time refers to any of several variant formalizations of the idea: how large must t be until the time-t distribution is approximately π?
One variant, total variation distance mixing time, is defined as the smallest t such that the total variation distance of probability measures is small: Choosing a different
, can only change the mixing time up to a constant factor (depending on
This is the sense in which Dave Bayer and Persi Diaconis (1992) proved that the number of riffle shuffles needed to mix an ordinary 52 card deck is 7.
Mathematical theory focuses on how mixing times change as a function of the size of the structure underlying the chain.
-card deck, the number of riffle shuffles needed grows as
Such problems can, for sufficiently large number of colors, be answered using the Markov chain Monte Carlo method and showing that the mixing time grows only as
Tools for proving rapid mixing include arguments based on conductance and the method of coupling.
In broader uses of the Markov chain Monte Carlo method, rigorous justification of simulation results would require a theoretical bound on mixing time, and many interesting practical cases have resisted such theoretical analysis.