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 can grow at most polynomially fast in log(number of states).
Stanford University
Fall 2022
This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required.
No concepts data
+ 37 more concepts