# Belief propagation on replica symmetric random factor graph models

### Amin Coja-Oghlan

Goethe University, Frankfurt, Germany### Will Perkins

University of Birmingham, UK

## Abstract

According to physics predictions, the free energy of random factor graph models that satisfy a certain “static replica symmetry” condition can be calculated via the Belief Propagation message passing scheme [Krzakala et al., PNAS 2007]. Here we prove this conjecture for two general classes of random factor graph models, namely Poisson random factor graphs and random regular factor graphs. Specifically, we show that the messages constructed just as in the case of acyclic factor graphs asymptotically satisfy the Belief Propagation equations and that the free energy density is given by the Bethe free energy formula.

## Cite this article

Amin Coja-Oghlan, Will Perkins, Belief propagation on replica symmetric random factor graph models. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 5 (2018), no. 2, pp. 211–249

DOI 10.4171/AIHPD/53