Mixing times for uniformly ergodic Markov chains
Consider the class of discrete time, general state space Markov chains which satisfy a "uniform ergodicity under sampling" condition. There are many ways to quantify the notion of "mixing time", i.e., time to approach stationarity from a worst initial state. We prove results asserting equivalence (up to universal constants) of different quantifications of mixing time. This work combines three areas of Markov theory which are rarely connected: the potential-theoretical characterization of optimal stopping times, the theory of stability and convergence to stationarity for general-state chains, and the theory surrounding mixing times for finite-state chains.
Year of publication: |
1997
|
---|---|
Authors: | Aldous, David ; Lovász, László ; Winkler, Peter |
Published in: |
Stochastic Processes and their Applications. - Elsevier, ISSN 0304-4149. - Vol. 71.1997, 2, p. 165-185
|
Publisher: |
Elsevier |
Keywords: | Markov chain Minorization Mixing time Randomized algorithm Stopping time |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
When Can One Test an Explanation? Compare and Contras Benford’s Law and the Fuzzy CLT
Aldous, David, (2010)
-
Some interesting processes arising as heavy traffic limits in an M/M/[infinity] storage process
Aldous, David, (1986)
-
The 'birth-and-assassination' process
Aldous, David, (1990)
- More ...