Factor models on locally tree-like graphs

Amir Dembo
Stanford University

Consider factor (graphical) models on sparse graph sequences that converge locally to a random tree T. Using a novel interpolation scheme we prove existence of limiting free energy density under uniqueness of relevant Gibbs measures for the factor model on T.
We demonstrate this for Potts and independent sets models and further characterize this limit via large-deviations type minimization problem and provide an explicit formula for its solution, as the Bethe free energy for a suitable fixed point of the belief propagation recursions on T (thereby rigorously generalize heuristic calculations by statistical physicists using ``replica'' or ``cavity'' methods).

This talk is based on a joint work with Andrea Montanari and Nike Sun.

Back to Mathematical Challenges in Graphical Models and Message-Passing Algorithms