Spectral Properties, Cutoff, and Limit Profiles for Markov Chains

点击翻译按钮获取中文摘要

Markov chains are random processes that retain no memory of the past. Over a hundred years since they were firstly introduced, the study of Markov chains is critical to mathematics, physics, computer science, statistics, engineering, and bioinformatics. This project focuses on the study of the rate of convergence of a Markov chain to the stationary distribution. The study of specific examples of Markov chains has proven to be very useful in finding deep connections between rapid mixing and spatial properties of spin systems, in sampling, approximate counting algorithms and card shuffling.The project has five broad aims all directed towards understanding cutoff, developing old and new techniques, and on studying specific examples of Markov chains that could help develop a theory. The first program focuses on the study of random walks on random graph models via understanding their geometry. The second program concerns the study of interacting particle systems, such as the asymmetric exclusion process with open boundaries. The third program is focusing on the existence of cutoff for random walks on trees. The fourth program concerns the properties of Glauber dynamics for the Potts model and its differences from the Ising model. The fifth program addresses several questions about the mixing properties of random walks on matrix groups and general configuration spaces that consist of matrices.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.