Applications where the mixing time of a Markov chain is important

Question

I was wondering what the importance of the mixing time of a Markov chain is. I understand that the mixing time is a measure of how long it takes the distribution to approach the stationary distribution. I was just wondering if someone could give some examples of applications where we care about the mixing time. I believe one application is algorithms, but I am not sure where exactly their importance there comes from. Many thanks!

Answer 1

In the context of monte carlo sampling, the mixing time of a markov chain affects the quality of the estimates you form using these samples. As an example, say we want to estimate an expectation using samples from the stationary distribution of the markov chain. If we ignore the mixing time, then we will end up using samples in our estimate which do not come from the distribution we are interested in. So our estimate will be worse than if we considered the mixing time.

However, as far as I know, there aren't great methods to determine if the markov chain has reached it's stationary distribution.

Answer 2

Markov chain Monte Carlo (MCMC) is a widely used algorithm in Mathematical Physics (starting from [1], see also [2]), Computer Science (see [3]) and Statistics (see, e.g. [4]), in order to sample from intractable distributions. Indeed, for many distributions that are important in these areas, such as Those arisning from the Potts model or the hard-core lattice gas, sampling via Markov chains is the only efficient method known. But how long should the Markov chain be run to achieve representative samples?

The main component in the running time of the MCMC algorithm is the ``mixing time'' of the underlying Markov chain. Theoretical bounds for the mixing time can be useful, though they are often too pessimistic. Exact sampling methods, such as "coupling from the past" (due to Propp and Wilson) have been invented for this purpose.

There are strong links between spectral and geometric properties of graphs and networks (such as their expansion properties), to the mixing time of random walks on these networks; the most famous is perhaps the "Cheeger inequality", inspired by a powerful analogy with Laplacians on Riemannian manifolds.

The modern mathematical theory of Markov chain mixing was initiated by Aldous and Diaconis in the 1980s. In their influential survey paper [5] they described the "cutoff phenomenon" where the distribution of the Markov chain approaches the limiting stationary distribution abruptly. They wrote "From a theoretical viewpoint, there are interesting questions concerning the cut-off phenomenon. This occurs in all the examples we can explicitly calculate, but we know no general result which says that the phenomenon must happen for all "reasonable" shuffling methods. " This phenomenon has been a key focus of study ever since, and a chapter is devoted to it in the book [6].

[1] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, (1953), “Equations of State Calculations by Fast Computing Machines,” Journal of Chemical Physics, 21, 1087–1092.

[2] Hastings, W. K. (1970), “Monte Carlo Sampling MethodsUsing Markov Chains and Their Applications,” Biometrika, 57, 97–109.

[3] Sinclair, A., 1993. Algorithms for Random Generation and Counting: A Markov Chain Approach: A Markov Chain Approach (Vol. 7). Springer Science & Business Media.

[4] Chib, S. and Greenberg, E., 1995. Understanding the Metropolis-Hastings algorithm. The American statistician, 49(4), pp. 327-335. (5453 citations according to Google Scholar).

[5] Aldous, David, and Persi Diaconis. "Shuffling cards and stopping times." The American Mathematical Monthly 93, no. 5 (1986): 333-348.

[6] Levin, David A., and Yuval Peres. Markov chains and mixing times. Vol. 107. second edition. American Mathematical Soc., 2017. (3346 citations according to Google Scholar.)