In a recent result, Weitz [31] established equivalence between the marginal distribution of a node, say v, in any binary pair-wise Markov Random Field (MRF), say G, with the marginal distribution of the root node in the selfavoid walk tree of the G starting at v. In this paper, we exploit this remarkable connection to obtain insights in the performance of the widely popular Belief Propagation heuristic for computing marginal distribution (sum-product) and max-marginal distribution (max-product). We obtain a tight characterization of the size of self-avoiding walk tree for any connected graph as a function of number of edges. This may be of interest in its own right.
