messages from to and the messages from to are real-valued functions , whose domain is the set of values that can be taken by the random variable associated with , denoted . These messages contain the "influence" that one variable exerts on another. The messages are computed differently depending on whether the node receiving the message is a variable node or a factor node. Keeping the same notation: A message from a variable node to a factor node is defined by for , where is the set of neighboring factor nodes of . If is empty then is set to the uniform distribution. A message from a factor node to a variable node is defined to be the product of the factor with messages from all other nodes, marginalized over all variables except the one associated with ,for , where is the set of neighboring (variable) nodes to . If is empty, then , since in this case . As shown by the previous formula: the complete marginalization is reduced to a sum of products of simpler terms than the ones appearing in the full joint distribution. This is the reason that belief propagation is sometimes called sum-product message passing, or the sum-product algorithm. In a typical run, each message will be updated iteratively from the previous value of the neighboring messages. Different scheduling can be used for updating the messages. In the case where the graphical model is a tree, an optimal scheduling allows to reach convergence after computing each messages only once (see next sub-section). When the factor graph has cycles, such an optimal scheduling does not exist, and a typical choice is to update all messages simultaneously at each iteration. Upon convergence (if convergence happened), the estimated marginal distribution of each node is proportional to the product of all messages from adjoining factors (missing the normalization constant): Likewise, the estimated joint marginal distribution of the set of variables belonging to one factor is proportional to the product of the factor and the messages from the variables: In the case where the factor graph is acyclic (i.e. is a tree or a forest), these estimated marginal actually converge to the true marginals in a finite number of iterations. This can be shown by mathematical induction. Exact algorithm for trees In the case when the factor graph is a tree, the belief propagation algorithm will compute the exact marginals.