AF: Small: Collaborative Research: The Physics of Markov Chains: Closing the Gap Between Theory and Practice

点击翻译按钮获取中文摘要

Markov chain Monte Carlo (MC) algorithms are important tools throughout the physical and biological sciences, with applications ranging from simulating new materials to reconstructing phylogenetic trees. They explore a space of states of a physical system, or potential solutions to a problem, by making a series of small changes. One of our main challenges is knowing whether the algorithm has run long enough to reach equilibrium, i.e., if it has spread throughout the space enough to obtain good estimates of important quantities. Here, there is a major divide between theoreticians and practitioners. Physicists use non-rigorous techniques that are much more optimistic than what theorists know how to prove. On the other hand, they are often based on deep ideas about the physical properties of these systems and their asymptotic behavior, and are backed up by numerical experiments. The main theme of the research under this award is to answer the question: how can we bridge the divide between these two camps?The PIs will focus on three areas where stronger bridges can be built. In two-dimensional spin systems, they will use power-law decay of correlations to prove polynomial mixing times at critical points, and to show that we can efficiently "remix from equilibrium" even below phase transitions where worst-case mixing times are exponential. They will give a rigorous understanding of the efficiency of cluster algorithms widely used in physics, which are believed to avoid or reduce the phenomenon of "critical slowing down" as we approach a phase transition. Finally, the PIs will go beyond traditional Markov chain analysis techniques on discrete state spaces, and prove new results on systems whose states are continuous, such as the hard-sphere model in the plane.This work is cross-disciplinary between physics and computer science. MC algorithms also offer an excellent opportunity to involve undergraduates in the research process: they can implement algorithms used in physics and computer science, and gain a "hands-on" feeling for their performance in theory and practice. They can also produce educational applets to let other students, in turn, see these algorithms in action.