Understanding the rate of convergence to stationarity, or mixing time, of a Markov chain is of interest for problems from shuffling cards to providing rigorous bounds for the runtime of Monte Carlo algorithms. In this talk, we will explain how the probabilistic technique of coupling can be used to bound mixing times. We will also discuss the cutoff phenomenon, which describes how mixing occurs very abruptly at, and not before, a precise point for certain Markov chains.
Pure Maths Seminar
Fri, 20/11/2020 - 12:00pm