Foundations and Trends® in Theoretical Computer Science > Vol 1 > Issue 3

Mathematical Aspects of Mixing Times in Markov Chains

By Ravi Montenegro, University of Massachusetts Lowell, USA, ravi_montenegro@uml.edu | Prasad Tetali, Georgia Institute of Technology, USA, tetali@math.gatech.edu

 
Suggested Citation
Ravi Montenegro and Prasad Tetali (2006), "Mathematical Aspects of Mixing Times in Markov Chains", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 1: No. 3, pp 237-354. http://dx.doi.org/10.1561/0400000003

Publication Date: 07 Jul 2006
© 2006 R. Montenegro and P. Tetali
 
Subjects
Randomness in computation,  Computational learning
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Basic Bounds on Mixing Times 
3 Advanced Functional Techniques 
4 Evolving Set Methods 
5 Lower Bounds on Mixing Times and their Consequences 
6 Examples 
7 Miscellaneous 
8 Open Problems 
Acknowledgements 
References 

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.

DOI:10.1561/0400000003
ISBN: 978-1-933019-29-1
78 pp. $80.00
Buy book (pb)
 
ISBN: 978-1-933019-77-2
78 pp. $100.00
Buy E-book (.pdf)
Table of contents:
1 Introduction
2 Basic Bounds on Mixing Times
3 Advanced Functional Techniques
4 Evolving Set Methods
5 Lower Bounds on Mixing Times and Their Consequences
6 Examples
7 Miscellaneous
8 Open Problems

Mathematical Aspects of Mixing Times in Markov Chains

Mathematical Aspects of Mixing Times in Markov Chains begins with a gentle introduction to the analytical aspects of the theory of finite Markov chain mixing times and quickly ramps up to explain the latest developments in the topic. Several theorems are revisited and often derived in simpler, transparent ways, and illustrated with examples. The highlights include spectral, logarithmic Sobolev techniques, the evolving set methodology, and issues of nonreversibility. Mathematical Aspects of Mixing Times in Markov Chains is a comprehensive, well-written review of the subject that will be of interest to researchers and students in computer and mathematical sciences.

 
TCS-003