422 8. GRAPHICAL MODELS
8.25 ( ) In (8.86), we verified that the sum-product algorithm run on the graph in
Figure 8.51 with nodex 3 designated as the root node gives the correct marginal for
x 2. Show that the correct marginals are obtained also forx 1 andx 3. Similarly, show
that the use of the result (8.72) after running the sum-product algorithm on this graph
gives the correct joint distribution forx 1 ,x 2.
8.26 ( ) Consider a tree-structured factor graph over discrete variables, and suppose we
wish to evaluate the joint distributionp(xa,xb)associated with two variablesxaand
xbthat do not belong to a common factor. Define a procedure for using the sum-
product algorithm to evaluate this joint distribution in which one of the variables is
successively clamped to each of its allowed values.
8.27 ( ) Consider two discrete variablesxandyeach having three possible states, for
examplex, y∈{ 0 , 1 , 2 }. Construct a joint distributionp(x, y)over these variables
having the property that the valuêxthat maximizes the marginalp(x), along with
the valuêythat maximizes the marginalp(y), together have probability zero under
the joint distribution, so thatp(̂x,̂y)=0.
8.28 ( ) www The concept of apendingmessage in the sum-product algorithm for
a factor graph was defined in Section 8.4.7. Show that if the graph has one or more
cycles, there will always be at least one pending message irrespective of how long
the algorithm runs.
8.29 ( ) www Show that if the sum-product algorithm is run on a factor graph with a
tree structure (no loops), then after a finite number of messages have been sent, there
will be no pending messages.
