AF: Small: Markov Chains and Mass Action Kinetics

AF：小：马尔可夫链和质量作用动力学

• 批准号: 2231095
• 负责人: Alistair Sinclair
• 金额: $ 60万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-01 至 2025-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2231095&HistoricalAwards=false
• 关键词: AF; Small; Markov; Chains; Mass

This project studies various types of dynamical processes that model computational and physical phenomena, including equilibrium and non-equilibrium statistical physics, genetic evolution via reproduction, and chemical reaction networks. The overarching goal is to leverage mathematical techniques and intuition developed for the analysis of algorithms in theoretical Computer Science to improve our understanding of these complex processes. Thus the project is an example of the application of a so-called “computational lens” to questions in other scientific fields, such as physics, chemistry and biology, which has proven very powerful in many cases. In addition to its scientific diversity, the project also affords ample opportunity for the training of graduate students, as well as curricular innovations at graduate and undergraduate levels.The project focuses on three major types of dynamics. The first type is classical reversible Markov chains, which are widely used to understand the evolution to equilibrium of systems in statistical physics, as well as algorithms for random sampling and approximate counting, and optimization methods such as simulated annealing. The second type is less classical “non-reversible” Markov chains, which describe the behavior of physical systems that are held out of equilibrium by an interaction with some external entity such as a heat-bath or particle reservoir. And the third type, known as "mass action kinetics”, capture the behavior of systems of species that repeatedly interact to produce new species, as in, for example, chemical reaction networks, genetic evolution via reproduction, genetic algorithms and Boltzmann’s model of an ideal gas. The project will add to our existing knowledge of reversible Markov chains, which are already well understood using sophisticated mathematical techniques, and will also develop the emerging theory of non-reversible Markov chains and mass action kinetics, both of which remain mathematically challenging and relatively far less well understood.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.

该项目研究模拟计算和物理现象的各种类型的动态过程，包括平衡和非平衡统计物理、通过繁殖的遗传进化和化学反应网络。总体目标是利用为算法分析而开发的数学技术和直觉。因此，该项目是将所谓的“计算镜头”应用于物理、化学和生物学等其他科学领域问题的一个例子，这已被证明是非常有效的。在很多情况下都很强大。除了科学多样性之外，该项目还为研究生的培养以及研究生和本科生的课程创新提供了充足的机会。该项目重点关注三种主要类型的动力学。第一类是广泛使用的经典可逆马尔可夫链。理解统计物理学中系统向平衡的演化，以及随机采样和近似计数的算法，以及模拟退火等优化方法。第二种类型是不太经典的“不可逆”马尔可夫链，它描述了系统的行为。物理系统通过与某些外部实体（例如热浴或粒子库）的相互作用而失去平衡，第三种类型称为“质量作用动力学”，捕捉物种系统的行为，这些系统反复相互作用以产生新物种，例如，化学反应网络、通过繁殖进行的遗传进化、遗传算法和理想气体的玻尔兹曼模型。该项目将增加我们对可逆马尔可夫链的现有知识，这些知识已经通过复杂的数学技术得到了很好的理解。还发展了新兴理论不可逆马尔可夫链和质量作用动力学，这两者在数学上仍然具有挑战性，并且相对而言还不太容易理解。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。