New approaches to Gibbs measures at the interface of probability and computational complexity

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

The concept of a "Gibbs distribution" - developed during the rise of statistical mechanics in the 19th century by Clausius, Maxwell, Boltzmann, Hamilton, and Gibbs - defines a probability distribution over configurations of particles based on an energy function governed by local interactions. Not only have Gibbs distributions proved invaluable in describing the behaviour of physical systems, but the simple framework of Gibbs distributions has become ubiquitous in fields far from statistical physics under the name "probabilistic graphical models": these fields include Bayesian statistics, optimisation, machine learning, mathematical biology, artificial intelligence, and many others. Gibbs distributions are remarkably effective because they respect the underlying structure of a complex system: probabilistic dependencies are specified by a simple network structure, corresponding to the network indicating which components of the system interact. Although the specification of a Gibbs distribution is very simple, the resulting probability distribution on configurations can be staggeringly complex. Typically the number of possible configurations grows as an exponential function of the system size, and so it is computationally hopeless to enumerate and calculate exact statistics of the system. Nevertheless, it is sometimes possible to understand all of the relevant global information about the system - the macroscopic `observables' - with simple and efficient algorithms, and this is why probabilistic graphical models arise so often in practical applications. This research proposal aims to develop new rigorous analytic and computational methods for understanding Gibbs distributions, and in particular, the physical heuristics that underly two associated algorithms, Markov Chain Monte Carlo and Belief Propagation. The proposal involves three interrelated goals. The first is to make rigorous an detailed family of predictions from statistical physics about Gibbs distributions on random, or "mean-field", networks. Such random networks are used as both an approximation of physical systems and as a model of real-life networks, but have the advantage of being more amenable to analysis.The second goal is to prove mathematically that the original mathematical model of a fluid, the "hard sphere model", exhibits a freezing transition from liquid to solid. The model, which is purely geometric, without any forces between molecules except for excluded volume, dates back to at least Boltzmann's time but has proved extremely resistant to rigorous analysis. The third and final goal is to study the extremes of Gibbs distributions: which networks maximise or minimise certain statistics? Besides delineating the boundaries of what is possible in a given Gibbs distribution, these questions also have connections to long-standing open problems in combinatorics.