LAUSR

We verify a key component of the replica symmetry breaking hypothesis put forward in the physics literature (Mézard and Montanari in Information, physics and computation. Oxford University Press, Oxford, 2009) on random factor graph models. For a broad class of these models we verify that the Gibbs measure can be decomposed into a moderate number of Bethe states, subsets of the state space in which both short and long range correlations of the measure take a simple form. Moreover, we show that the marginals of these Bethe states can be obtained from fixed points of the Belief Propagation operator. We derive these results from a new result on the approximation of general probability measures on discrete cubes by convex combinations of product measures.