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.