Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs. This general result implies the conjecture on the information-theoretic threshold in the disassortative stochastic block model [: Phys. Rev. E (2011)] and allows us to pinpoint the exact condensation phase transition in random constraint satisfaction problems such as random graph coloring, thereby proving a conjecture from [: PNAS (2007)]. As a further application we establish the formula for the mutual information in Low-Density Generator Matrix codes as conjectured in [Montanari: IEEE Transactions on Information Theory (2005)]. The proofs provide a conceptual underpinning of the replica symmetric variant of the cavity method, and we expect that the approach will find many future applications.
Previously the validity of the physics formulas was known in any generality only under the assumption that the factor graph models satisfies the Gibbs uniqueness condition, a very strong spatial mixing assumption @cite_80 @cite_47 @cite_76 @cite_9 . Gibbs uniqueness typically only holds for very small values of @math . Additionally, under weaker spatial mixing conditions it was known that the free energy in random graph models is given by some Belief Propagation fixed point @cite_73 @cite_9 . However, there may be infinitely many fixed points, and it was not generally known that the correct one is the maximizer of the functional @math . In effect, it was not possible to derive the formula for the free energy or, equivalently, the mutual information, from such results. Specifically, in the case of the teacher-student scheme Montanari @cite_74 proved (under certain assumptions) that the Gibbs marginals of @math correspond to a Belief Propagation fixed point as in , whereas identifies the particular fixed point that maximizes the functional @math as the relevant one.
@cite_73 @cite_9 @cite_74 @cite_80 @cite_47 @cite_76
2963553740 2018836315 1677159791 904137795 2266756552 2963994072
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 a wide class of random factor graph models. 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. We consider homogeneous factor models on uniformly sparse graph sequences converging locally to a (unimodular) random tree T, and study the existence of the free energy density ϕ, the limit of the log-partition function divided by the number of vertices n as n tends to infinity. We provide a new interpolation scheme and use it to prove existence of, and to explicitly compute, the quantity ϕ subject to uniqueness of a relevant Gibbs measure for the factor model on T. By way of example we compute ϕ for the independent set (or hard-core) model at low fugacity, for the ferromagnetic Ising model at all parameter values, and for the ferromagnetic Potts model with both weak enough and strong enough interactions. Even beyond uniqueness regimes our interpolation provides useful explicit bounds on ϕ. In the regimes in which we establish existence of the limit, we show that it coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation (Bethe) recursions on T. In the special case that T has a Galton–Watson law, this formula coincides with the nonrigorous “Bethe prediction” obtained by statistical physicists using the “replica” or “cavity” methods. Thus our work is a rigorous generalization of these heuristic calculations to the broader class of sparse graph sequences converging locally to trees. We also provide a variational characterization for the Bethe prediction in this general setting, which is of independent interest. Let X 1 ,...., X n be a collection of iid discrete random variables, and Y 1 ,...., Y m a set of noisy observations of such variables. Assume each observation Y a to be a random function of a random subset of the X i s, and consider the conditional distribution of X i given the observations, namely μ i (x i ) = P X i = x i |Y (a posteriori probability). We establish a general decoupling principle among the X i s, as well as a relation between the distribution of μ i , and the fixed points of the associated density evolution operator. These results hold asymptotically in the large system limit, provided the average number of variables an observation depends on is bounded. We discuss the relevance of our result to a number of applications, ranging from sparse graph codes and multi-user detection, to group testing. 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. Many problems of interest in computer science and information theory can be phrased in terms of a probability distribution over discrete variables associated to the vertices of a large (but finite) sparse graph. In recent years, considerable progress has been achieved by viewing these distributions as Gibbs measures and applying to their study heuristic tools from statistical physics. We review this approach and provide some results towards a rigorous treatment of these problems. AMS 2000 subject classifications: Primary 60B10, 60G60, 82B20.