AF: Small: Markov Chains and Mass Action Kinetics

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.