Markov chain mixing time
Encyclopedia
In probability theory
, the mixing time of a Markov chain
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 Diaconis
proved that the number of riffle shuffle
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 coloring
s of a given n vertex graph. 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 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 conductance and the method of Coupling (probability)
. 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.
Probability theory
Probability 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 chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
is the time until the Markov chain is "close" to its steady state
Steady state
A system in a steady state has numerous properties that are unchanging in time. This implies that for any property p of the system, the partial derivative with respect to time is zero:...
distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
.
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 Diaconis
Persi Diaconis
Persi 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 shuffle
Shuffle
Shuffling 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 help 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 coloring
Graph coloring
In 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 Carlo
Markov chain Monte Carlo
Markov 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 of 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 conductance and the method of Coupling (probability)
Coupling (probability)
In probability theory, 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
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
, rigorous justification of simulation results would require a theoretical bound on mixing time, and many interesting practical cases have resisted such theoretical analysis.