In
probability theoryProbability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, the
mixing time of a
Markov chainIn mathematics, a Markov chain, named after Andrey Markov, is a random process where all information about the future is contained in the present state . To be more exact, the process has the Markov property, meaning that future states depend only on the present state, and are independent of past...
is the time until the Markov chain is "close" to its steady state distribution.
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.
In
probability theoryProbability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, the
mixing time of a
Markov chainIn mathematics, a Markov chain, named after Andrey Markov, is a random process where all information about the future is contained in the present state . To be more exact, the process has the Markov property, meaning that future states depend only on the present state, and are independent of past...
is the time until the Markov chain is "close" to its steady state distribution.
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,
variation distance mixing time, is defined as the smallest
t such that
for all subsets
A of states and all initial states. This is the sense in which David Bayer and
Persi DiaconisPersi Warren Diaconis is an American mathematician and former professional magician. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University....
proved that the number of riffle
shuffleShuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to ensure that the shuffler has not manipulated the outcome.-Shuffling techniques:...
s 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. For an
n-card deck, the number of riffle shuffles needed grows as
1.5 log (n) / log (2). The most developed theory concerns randomized algorithms for #P-Complete algorithmic counting problems such as the number of
graph coloringIn graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
s of a given
n vertex graph. Such problems can, for sufficiently large number of colors, be answered using the
Markov chain Monte CarloMarkov chain Monte Carlo methods , are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample from the...
method and showing that the mixing time grows only as
n log (n). This example and the shuffling example possess the
rapid mixing property, that the mixing time grows at most polynomially fast in
log (number of states of the chain). Tools for proving rapid mixing include arguments based on
conductanceFor an ergodic reversible Markov chain with an underlying graph G, the conductance is a way to measure how hard it is to leave a small set of nodes. Formally, the conductance of a graph is defined as the minimum over all sets of the capacity of divided by the ergodic flow out of...
and the method of
Coupling (probability)In mathematics, coupling is a proof technique that allows one to compare two unrelated variables by "forcing" them to be related in some way.-Definition:...
. 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.