Mixing time is a concept in probability theory that refers to the time it takes for a Markov chain to reach its steady state distribution. It is used to measure how long it takes for a system to reach equilibrium, such as the number of riffle shuffles needed to mix a deck of cards. Mixing times can be calculated using tools such as conductance and coupling, and are usually bounded by polynomial functions of the size of the underlying structure.
Stanford University
Autumn 2022
The course addresses both classic and recent developments in counting and sampling. It covers counting complexity, exact counting via determinants, sampling via Markov chains, and high-dimensional expanders.
No concepts data
+ 52 more concepts