|
|
|
|
Mathematical Aspects of Mixing Times in Markov Chains
Foundations and Trends® in
Theoretical Computer Science
Volume 1 Issue 3
DOI: 10.1561/0400000003
Mathematical Aspects of Mixing Times in Markov Chains
R. Montenegro
University of Massachusetts Lowell, Lowell, Massachusetts 01854, USA,
ravi montenegro@uml.edu
P. Tetali
Georgia Institute of Technology, Atlanta, Georgia 30332, USA,
tetali@math.gatech.edu
Abstract
In the past few years we have seen a surge in the theory of finite Markov
chains, by way of new techniques to bounding the convergence to
stationarity. This includes functional techniques such as logarithmic Sobolev
and Nash inequalities, refined spectral and entropy techniques, and
isoperimetric techniques such as the average and blocking conductance and
the evolving set methodology. We attempt to give a more or less
self-contained treatment of some of these modern techniques, after
reviewing several preliminaries. We also review classical and modern lower
bounds on mixing times. There have been other important contributions to
this theory such as variants on coupling techniques and decomposition
methods, which are not included here; our choice was to keep the
analytical methods as the theme of this presentation. We illustrate
the strength of the main techniques by way of simple examples,
a recent result on the Pollard Rho random walk to compute the
discrete logarithm, as well as with an improved analysis of the Thorp
shuffle.
|
|
|
|
|
|
|
|
|