On the Convergence of Belief Propagation Algorithm for Stochastic Networks With Loops

The belief propagation (BP) algorithm is a tool with which one can calculate beliefs, marginal probabilities, of stochastic networks without loops (e.g., Bayesian networks) in a time proportional to the number of nodes. For networks with loops, it may not converge and, even if it converges, beliefs may not equal to exact marginal probabilities although its application is known to give remarkably good results in the coding theory. We show a theoretical result of the convergence of the algorithm for stochastic netwrks with loops, which gives a su#cient condition of the convergence of the algorithm in terms of the theory of Markov random fields on trees. The present result shows the convergence of the algorithm is closely related to phase transition phenomenon of models on infinite trees called unwrapped networks.