Over the past three decades, physicists have developed sophisticated non-rigorous techniques for accurately predicting the asymptotic behavior of large complex(random) systems. Mathematicians are making significant progress in developing the corresponding rigorous theories and proving these predictions. Probability theory is at the forefront of this convergence, starting with the theory of large deviations and continuing with the emerging vibrant activity in the study of stochastic dynamics of interacting particles, large random matrices, Gibbs measures and planar objects with conformal symmetries. A particular success story from a physics point of view are mean field(disordered) models, where two levels of randomness are often present, one of whom frozen (quenched), in the form of dependence graph or weights for the resulting stochastic process, whose distribution is exchangeable when averaged over the disorder. Specific directions we plan to pursue are (1) Rigorous study of large systems of discrete variables that are strongly interacting according to a mean field model determined by an ensemble of (randomly chosen) graphs, (2) novel connections between the asymptotic behavior of the spectrum of structured models of random matrices and properties of the corresponding random graphs and graph embeddings,(3) properties of stochastic dynamics for spin systems out of equilibrium, such as aging and the finite size scaling associated with their phase transitions.
This project is expected to yield new mathematical ideas and techniques that resolve challenging problems in probability theory, impact its interface with statistical physics, and provide insight to the analysis of typical behavior of large constraint satisfaction networks, thus advancing progress at the core of the NSF cyber-enabled discovery and innovation initiative. Long-term effects on graduate and post-graduate training of students in discrete probability and information theory are also expected.
A graph is defined by a set of nodes, or vertices, and a set of edges, or links, whereby each edge connects two vertices. Graphs form a simple yet universal language for expressing relationships between objects. In particular, they can be used to express statistical dependencies across a collection of variables. In the most basic case, a variable is associated to each node and their joint probability distribution factors into a product of terms, with each term associated to an edge that couples the adjacent vertices. This is technically referred to as a Markov Random Field, a Gibbs measure, or a pairwise graphical model, depending on the context. The PIs developed mathematically rigorous techniques to understand the qualitative properties of such probability distributions on very large graphs. In particular, they built on 'mean field' heuristics coming from statistical physics and characterized the large scale properties of certain type of graphical models involving commonly encountered random graph models. For example, they derived exact characterizations when each vertex variable takes only two values and all interactions are attractive, i.e. neighbors prefer taking the same value. This is known in physics as the ferromagnetic Ising model. The same techniques were also extended to treat specific classes of Potts models (q-ary valued variables, with attractive interactions). The study of graphical models is of interest both for pure mathematics and for a number of applications. From a mathematical point of view, classical probability theory provides a refined understanding of many properties of collections of independent random variables. Few, if any, general techniques can characterize large collection of strongly dependent random variables. The mean field methods studied by this project hold the promise of one such collection of general tools. From an application perspective, graphical models of the type studied here arise in a number of contexts: computer science and approximate counting; coding theory; statistical physics. This project has had direct implications and connections with each of these fields.
