Without loss of generality, we assume in this proof that all variables
are declared as evidence variables.
To prove this soundness theorem, all we need to show is that each Q-DAG
potential will evaluate to its corresponding probabilistic potential under
all possible evidence. Formally, for any cluster and variables ,
the matrices of which are assigned to , we need to show that
for a given evidence . Once we establish this, we are guaranteed that will evaluate to the probability because the application of and in the Q-DAG algorithm is isomorphic to the application of * and + in the probabilistic algorithm, respectively.
To prove Equation 1, we will extend the Q-DAG node evaluator
to mappings in the standard way. That is, if is a mapping
from instantiations to Q-DAG nodes, then is defined as follows:
That is, we simply apply the Q-DAG node evaluator to the range of mapping .
Note that will then be equal to .
Note also that by definition of , we have that equals . Therefore,