How long does it take to shuffle a deck of cards? An introduction to mixing - Lecture 2

Many familiar random processes can be modelled as Markov chains. For example, repeatedly shuffling a deck of $n$ cards using a simple random rule defines a Markov chain whose states are the $n!$ possible orderings of the deck, and whose transition probabilities can be arranged into an $n!$ by $n!$ stochastic matrix $P$. A natural question is: how many shuffles are needed before the deck is well mixed?
The answer is given by the theory of mixing times, which quantify how quickly a random process approaches its long-term behaviour. Notably, the mixing time of many natural card shuffles will turn out to be polynomial in $n$, allowing to roughly uniformly sample one of a super-exponential number of possible orderings via a small number of simple operations. In this minicourse, we shall introduce the concept of mixing time via concrete examples and gradually develop key tools for estimating it, such as couplings, spectral methods and conductance. We shall see how this rich theory plays a central role in probability, theoretical computer science and statistical physics, and discuss recent developments as well as several beautiful open problems.