This work addresses the problem of the marginalization of the joint probability of a spin system.

These systems can be viewed in the framework of graphical models, which provide a convenient way of representing conditional dependence relations among large numbers of random variables. Specifically, each node s in an undirected graph is associated with a random variable σ_s, while the set of edges E is used to describe the conditional dependency structure of the variables.

Belief propagation is an increasingly popular method of performing approximate inference on arbitrary graphical models: the goal of belief propagation (BP), also called the sum-product algorithm, is to compute the marginal distribution p_s(σ_s) at each node s.

Graphical models and message-passing algorithms defined on graphs comprise a growing field of research. Great part of the appeal of belief propagation lies in its optimality for tree-structured graphical models (models which contain no loops). In fact, for tree-structured graphical models, belief propagation can be used to efficiently perform exact marginalization. Specifically, the iteration (1) converges in a finite number of iterations (at most the length of the longest path in the graph), after which the belief (2) equals the correct marginal p_s(σ_s).

Nevertheless, it is also widely applied to graphical models with cycles by following the same local message passing rules at each node and ignoring the presence of cycles in the graph; this procedure is typically referred to as loopy BP. In these cases it may not converge, and if it does its solution is approximate; however in practice these approximations are often good, as we will see.

The purpose of this work is to prove the goodness of BP in arbitrary sparse graphs representing famous spin systems (in particular we will con- sider the Ising model with positive and negative couplings, and a spin glass system). We will compare the results with a modification to the BP algorithm that we will call ”Site Belief Propagation”. The latter is an implementa- tion of BP that does not involve message exchanging but only an updating of some ”site-parameters”.