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

“吉布斯分布”的概念——在19世纪统计力学兴起期间由克劳修斯、麦克斯韦、玻尔兹曼、汉密尔顿和吉布斯提出——定义了基于局部相互作用控制的能量函数的粒子构型的概率分布。吉布斯分布不仅在描述物理系统的行为方面被证明是无价的，而且吉布斯分布的简单框架已经在统计物理学以外的领域中无处不在，这些领域包括贝叶斯统计、优化、机器学习、数学生物学、人工智能等。吉布斯分布非常有效，因为它们尊重复杂系统的底层结构：概率依赖关系由一个简单的网络结构指定，对应于指示系统哪些组件相互作用的网络。尽管吉布斯分布的说明非常简单，但得到的配置上的概率分布可能非常复杂。通常情况下，可能配置的数量作为系统大小的指数函数增长，因此在计算上无法枚举和计算系统的精确统计信息。然而，有时有可能用简单而有效的算法来理解系统的所有相关全局信息——宏观的“可观察物”，这就是为什么概率图形模型在实际应用中经常出现的原因。本研究计划旨在开发新的严格的分析和计算方法来理解吉布斯分布，特别是在两种相关算法，马尔可夫链蒙特卡罗和信念传播的基础上的物理启发式。该提案涉及三个相互关联的目标。第一个是从统计物理学中对随机网络或“平均场”网络上的吉布斯分布做出严格详细的预测。这种随机网络既可用作物理系统的近似，也可用作现实生活网络的模型，但其优点是更易于分析。第二个目标是从数学上证明流体的原始数学模型，即“硬球模型”，表现出从液体到固体的冻结转变。这个模型是纯几何的，除了排除体积之外，分子之间没有任何力，它至少可以追溯到玻尔兹曼的时代，但已被证明对严格的分析具有极强的抵抗性。第三个也是最后一个目标是研究吉布斯分布的极端情况：哪些网络使某些统计数据最大化或最小化？除了在给定的吉布斯分布中描绘可能的边界之外，这些问题还与组合学中长期存在的开放问题有关。

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.