EUVIMEDEUVIMED entdecken
Crossref

Mathematical Aspects of Mixing Times in Markov Chains

Ravi Montenegro, Prasad Tetali

Foundations and Trends® in Theoretical Computer Science · 2006

DOI: 10.1561/0400000003 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, 2006. Verfasst von Ravi Montenegro und 1 weiteren Autor:innen. Die Arbeit wurde bisher 181-mal zitiert (Crossref) und nennt 74 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Montenegro, R., & Tetali, P. (2006). Mathematical Aspects of Mixing Times in Markov Chains. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000003

Vancouver

Montenegro R, Tetali P. Mathematical Aspects of Mixing Times in Markov Chains. Foundations and Trends® in Theoretical Computer Science. 2006. doi:10.1561/0400000003

BibTeX
@article{Montenegro2006,
  author = {Montenegro, Ravi and Tetali, Prasad},
  title = {Mathematical Aspects of Mixing Times in Markov Chains},
  journal = {Foundations and Trends® in Theoretical Computer Science},
  year = {2006},
  doi = {10.1561/0400000003}
}
Kostenlos starten →