
doi: 10.1137/1037083
Summary: This is an expository paper that presents various ideas related to nonasymptotic rates of convergence for Markov chains. Such rates are of great importance for stochastic algorithms that are widely used in statistics and in computer science. They also have applications to analysis of card shuffling and other areas. We attempt to describe various mathematical techniques that have been used to bound such rates of convergence. In particular, we describe eigenvalue analysis, random walks on groups, coupling, and minorization conditions. Connections are made to modern areas of research wherever possible. Elements of linear algebra, probability theory, group theory, and measure theory are used, but efforts are made to keep the presentation elementary and accessible.
Limit theorems in probability theory, stochastic algorithms, Markov chain, eigenvalue, rates of convergence, Probability measures on groups or semigroups, Fourier transforms, factorization, coupling, random walk on group, Markov chains (discrete-time Markov processes on discrete state spaces)
Limit theorems in probability theory, stochastic algorithms, Markov chain, eigenvalue, rates of convergence, Probability measures on groups or semigroups, Fourier transforms, factorization, coupling, random walk on group, Markov chains (discrete-time Markov processes on discrete state spaces)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 124 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
