Mixing times and Cutoff

This research project concerns Markov chains, which are used in probability theory to generate random objects, such as random colorings of graphs, bases of vector spaces, and triangulations of a polygon. Markov chains play a pivotal role in theoretical computer science, enabling the development of sampling and approximate counting algorithms important in statistical physics and cryptography. Another important family of examples includes card shuffle sequences, which have intriguing connections to DNA rearrangements in biology. The main targets of study in this project are mixing times, cutoff, and limit profiles. The time it takes a physical system to reach equilibrium is an example of a mixing time. The cutoff phenomenon describes a phase transition during which the distance of a Markov chain from equilibrium very abruptly drops to near zero. The limit profile captures the limiting value of the distance to stationarity as the size of the state space grows to infinity. The research problems under investigation impact a spectrum of disciplines, including computer science, cryptography, physics, and biology, and the project also offers research opportunities for graduate students.

The current research program aims at developing techniques for studying the cutoff phenomenon and determining the limit profile for important Markov chains. Mixing phenomena will be explored using tools from representation theory, combinatorics, and probability theory. The program focuses on a range of models, including particle systems, exclusion processes, random walks on groups, and card shuffling. The primary goal of the research is to develop versatile techniques for bounding mixing times and establishing the occurrence of the cutoff phenomenon. A significant part of the proposal concerns exclusion processes. These processes have evolved into some of the most widely studied particle systems across mathematical physics, probability theory, and combinatorics. Their applications span various domains, from modeling traffic congestion to simulating the motion of molecules in gases.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Award Number: 2450510
Principal Investigator: Evrydiki Nestoridi
Funds Obligated: $240,000
State: NY