Mixing times

Mixing times is an area on the interface of mathematics, statistical physics and theoretical computer science. In statistical physics, the mixing time represents how long it takes a physical system to reach equilibrium. In computer science, it is the main component in the running time of randomized algorithms for sampling, approximate counting and volume estimation.  Consequently, a discovery in this area can have impact in different directions. A fascinating phenomenon which can occur is cutoff. This means that the system goes abruptly from not looking random to a completely random state over a negligible period of time. Cutoff was first discovered by Diaconis in the context of analysing card shuffling techniques and since then it has been conjectured to hold for many natural chains. Establishing cutoff often requires obtaining very precise asymptotics for the mixing time. This can be challenging and it is a central question to understand the criteria for cutoff for general classes of graphs.

Who's involved

Software