Spectral Properties, Cutoff, and Limit Profiles for Markov Chains

马尔可夫链的谱特性、截止和极限曲线

• 批准号: 2052659
• 负责人: Evrydiki Nestoridi
• 金额: $ 22.42万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2023-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2052659&HistoricalAwards=false
• 关键词: Spectral; Properties; Cutoff; Limit; Profiles

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.

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