zbMATH — the first resource for mathematics

Mixing times. (English) Zbl 0908.60065
Aldous, David (ed.) et al., Microsurveys in discrete probability. DIMACS workshop, Princeton, NJ, USA, June 2–6, 1997. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 41, 85-133 (1998).
A Markov chain is constructed from whose stationary distribution one wishes to sample, and then the chain is run for a fixed number of steps after which the distribution of the current state is “nearly” stationary. This number of steps is “the mixing time” and there are many ways to define it, but they fall into a small number of classes. The parameters in each class lie within constant multiples of one another, independent of the chain. Furthermore, there are interesting connections between these classes related to time reversal.
For the entire collection see [Zbl 0892.00045].

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G50 Sums of independent random variables; random walks
60G40 Stopping times; optimal stopping problems; gambling theory
62L15 Optimal stopping in statistics
PDF BibTeX Cite