probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, the mixing time of a

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...

is the time until the Markov chain is "close" to its

steady state In systems theory, a system or a Process theory, process is in a steady state if the variables (called state variables) which define the behavior of the system or the process are unchanging in time. In continuous time, this means that for those p ...

distribution Distribution may refer to: Mathematics *Distribution (mathematics), generalized functions used to formulate solutions of partial differential equations * Probability distribution, the probability of a particular value or value range of a vari ...

. More precisely, a fundamental result about

Markov chains A Markov chain or Markov process is a stochastic process, stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought ...

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 the

total variation distance of probability measures In probability theory, the total variation distance is a distance measure for probability distributions. It is an example of a statistical distance metric, and is sometimes called the statistical distance, statistical difference or variational dist ...

is small: :

, \Pr(X_t \in A) - \pi(A),  \leq 1/4

for all subsets

A

of states and all initial states. This is the sense in which proved that the number of riffle

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. __TOC__ Techniques Overha ...

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_2 n

. The most developed theory concerns

randomized algorithms A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

for #P-Complete algorithmic counting problems such as the number of

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 o ...

s of a given

n

vertex graph. Such problems can, for sufficiently large number of colors, be answered using the

Markov chain Monte Carlo In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain ...

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 A coupling is a device used to connect two shafts together at their ends for the purpose of transmitting power. The primary purpose of couplings is to join two pieces of rotating equipment while permitting some degree of misalignment or end mov ...

. In broader uses of the Markov chain

Monte Carlo method Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...

, rigorous justification of simulation results would require a theoretical bound on mixing time, and many interesting practical cases have resisted such theoretical analysis.

References

*. *. *. *. *{{citation , last = Sinclair , first = Alistair , doi = 10.1007/978-1-4612-0323-0 , isbn = 0-8176-3658-7 , mr = 1201590 , publisher = Birkhäuser Boston, Inc., Boston, MA , series = Progress in Theoretical Computer Science , title = Algorithms for random generation and counting: A Markov chain approach , year = 1993. Markov processes

See also

References