Digital scan back

2013-03-17T07:07:09Z

50.14.143.5: Erroneous. Bayer filter images are not "downsampled to improve quality" Downsampling is preferable to upsampling, but both reduce image quality.

In [[probability theory]], the '''mixing time''' of a [[Markov chain]] is the time until the Markov chain is "close" to its [[steady state]] [[probability distribution|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
:<math>|\Pr(X_t \in A) - \pi(A)| \leq 1/4 </math>
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 [[Sharp-P-complete|#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)''{{Citation needed|date=June 2013}}. 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 (probability)|conductance]] and the method of [[Coupling (probability)|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.

== See also==
* [[Mixing (mathematics)]] for a formal definition of mixing

==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 Aldous and Jim Fill, [http://stat-www.berkeley.edu/users/aldous/RWG/book.html ''Reversible Markov Chains and Random Walks on Graphs'']

*David A. Levin, Yuval Peres and Elizabeth L. Wilmer (2008) ''Markov Chains and Mixing Times'', Amer. Math. Soc., Providence, RI [http://darkwing.uoregon.edu/~dlevin/MARKOV/]

[[Category:Markov processes]]

formulasearchengine - User contributions [en]

Digital scan back