Spectral Properties, Cutoff, and Limit Profiles for Markov Chains

马尔科夫链是不保留过去记忆的随机过程。自从马尔可夫链被首次提出以来，一百多年来，对马尔可夫链的研究对数学、物理、计算机科学、统计学、工程学和生物信息学都是至关重要的。本课题主要研究马尔可夫链向平稳分布的收敛速度。对马尔可夫链的具体例子的研究已被证明在快速混合和自旋系统的空间性质、采样、近似计数算法和洗牌之间的深层次联系方面非常有用。该项目有五个广泛的目标，都指向了解截止，发展新旧技术，以及研究马尔可夫链的具体例子，以帮助发展一种理论。第一个程序专注于通过了解随机图模型的几何来研究随机图模型上的随机游动。第二个程序涉及相互作用粒子系统的研究，例如具有开放边界的非对称排斥过程。第三个项目是关于在树上随机行走的截止点的存在。第四个程序涉及Potts模型的Glauber动力学性质及其与Ising模型的区别。第五个方案解决了矩阵群和由矩阵组成的一般配置空间上的随机游动的混合性质的几个问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.