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.