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 [, 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.
Furthermore, inspired by the theory of graph limits @cite_27 , Coja-Oghlan, Perkins and Skubch @cite_6 put forward a limiting theory'' for discrete probability measures to go with the regularity concept from @cite_23 . They applied this concept to the Poisson factor graph model from under the assumption that ) holds and that the Gibbs measure converges in probability to a limiting measure (in the topology constructed in @cite_6 ). While these assumptions are stronger and more complicated to state than ), @cite_6 shows that the limiting Gibbs measure induces a geometric'' Gibbs measure on a certain infinite random tree. Moreover, this geometric measure satisfies a certain fixed point relation reminiscent of the Belief Propagation equations.
@cite_27 @cite_23 @cite_6
904137795 2266756552
A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few variables and either encourage or discourage certain value combinations. Examples include the k-SAT problem or the Ising model. Such models naturally induce a Gibbs measure on the set of assignments, which is characterised by its partition function. The present paper deals with the partition function of problems where the interactions between variables and constraints are induced by a sparse random (hyper)graph. According to physics predictions, a generic recipe called the “replica symmetric cavity method” yields the correct value of the partition function if the underlying model enjoys certain properties [, PNAS (2007) 10318–10323]. Guided by this conjecture, we prove general sufficient conditions for the success of the cavity method. The proofs are based on a “regularity lemma” for probability measures on sets of the form Ωn for a finite Ω and a large n that may be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016 Abstract Building upon the theory of graph limits and the Aldous–Hoover representation and inspired by Panchenko’s work on asymptotic Gibbs measures [Annals of Probability 2013], we construct continuous embeddings of discrete probability distributions. We show that the theory of graph limits induces a meaningful notion of convergence and derive a corresponding version of the Szemeredi regularity lemma. Moreover, complementing recent work (2015), we apply these results to Gibbs measures induced by sparse random factor graphs and verify the “replica symmetric solution” predicted in the physics literature under the assumption of non-reconstruction.