AF: Small: Markov Chains and Mass Action Kinetics

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

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.