Markov chain mixing time

Markov chain mixing time

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

|\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 David Bayer and Persi Diaconis 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. 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 colorings 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.

See also

References

  • D. Bayer and P. Diaconis (1992), "Trailing the Dovetail Shuffle to its Lair", Annals of Applied Probability, volume 2, page 294–313.
  • A. Sinclair (1993), Algorithms for Random Generation and Counting: A Markov Chain Approach, Birkhäuser, Boston-Basel-Berlin.
  • David A. Levin, Yuval Peres and Elizabeth L. Wilmer (2008) Markov Chains and Mixing Times, Amer. Math. Soc., Providence, RI [1]

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Mixing time — may refer to: Blend time, the time to achieve a predefined level of homogeneity of a flow tracer in a mixing vessel Mixing (mathematics), an abstract concept originating from physics used to attempt to describe the irreversible thermodynamic… …   Wikipedia

  • Markov chain — A simple two state Markov chain. A Markov chain, named for 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 …   Wikipedia

  • Markov chain Monte Carlo — MCMC redirects here. For the organization, see Malaysian Communications and Multimedia Commission. Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods) are a class of algorithms for sampling from probability… …   Wikipedia

  • Mixing (mathematics) — In mathematics, mixing is an abstract concept originating from physics: the attempt to describe the irreversible thermodynamic process of mixing in the everyday world: mixing paint, mixing drinks, etc. The concept appears in ergodic theory the… …   Wikipedia

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Conductance (graph) — For other uses, see Conductance. In graph theory the conductance of a graph G=(V,E) measures how well knit the graph is: it controls how fast a random walk on G converges to a uniform distribution. The conductance of a graph is often called the… …   Wikipedia

  • Conductance (probability) — For 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 S of the capacity… …   Wikipedia

  • Dynamic Markov compression — (DMC) is a lossless data compression algorithm developed by Gordon Cormack and Nigel Horspool [1]. It uses predictive arithmetic coding similar to prediction by partial matching (PPM), except that the input is predicted one bit at a time (rather… …   Wikipedia

  • Shuffling — Shuffle redirects here. For other uses, see Shuffle (disambiguation). 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… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”