Contents

Markov chain mixing time

${\displaystyle t_{\operatorname {mix} }(\varepsilon )=\min \left\{t\geq 0:\max _{x\in S}{\Big [}\max _{A\subseteq S}\left|\Pr(X_{t}\in A\mid X_{0}=x)-\pi ($A)\right|{\Big ]}\leq \varepsilon \right\}.}

Choosing a different ${\displaystyle \varepsilon }$, as long as ${\displaystyle \varepsilon <1/2}$, can only change the mixing time up to a constant factor (depending on ${\displaystyle \varepsilon }$) and so one often fixes ${\displaystyle \varepsilon =1/4}$ and simply writes ${\displaystyle t_{\mathrm {mix} }}$.

This is the sense in which Dave Bayer and Persi Diaconis (1992) 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 ${\displaystyle n}$-card deck, the number of riffle shuffles needed grows as ${\displaystyle 1.5\log _{2}n}$. The most developed theory concerns randomized algorithms for #P-complete algorithmic counting problems such as the number of graph colorings of a given ${\displaystyle 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 ${\displaystyle n\log($n)} (Jerrum 1995). This example and the shuffling example possess the rapid mixing property, that the mixing time grows at most polynomially fast in ${\displaystyle \log }$(number of states of the chain). Tools for proving rapid mixing include arguments based on conductance and the method of 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[edit]

• Mixing (mathematics) for a formal definition of mixing

References[edit]

• Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs, archived from the original on 2004-09-21.
• Bayer, Dave; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair" (PDF), The Annals of Applied Probability, 2 (2): 294–313, doi:10.1214/aoap/1177005705, JSTOR 2959752, MR 1161056.
• Jerrum, Mark (1995), "A very simple algorithm for estimating the number of k-colorings of a low-degree graph", Random Structures & Algorithms, 7 (2): 157–165, doi:10.1002/rsa.3240070205, MR 1369061.
• Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. (2009), Markov chains and mixing times, Providence, Rhode Island: American Mathematical Society, ISBN 978-0-8218-4739-8, MR 2466937.
• Sinclair, Alistair (1993), Algorithms for random generation and counting: A Markov chain approach, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, doi:10.1007/978-1-4612-0323-0, ISBN 0-8176-3658-7, MR 1201590.