AF: Small: Markov Chains and Mass Action Kinetics

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

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.