Our task is to compute 
in a BN. According to
Proposition 6, we can do this in the
deputation of the BN.
An elimination ordering consisting of the variables outside 
is legitimate if
each deputy variable 
appears before the corresponding
new regular variable e.
Such an ordering can be found using, with minor adaptations,
minimum deficiency search or
maximum cardinality search.
The following algorithm computes 
in the deputation BN.
It is called VE1 because it is an extension of
VE .
Procedure VE1
- Inputs:
--- The list of homogeneous factors
in the deputation BN;
--- The list of heterogeneous factors
in the deputation BN;
X --- A list of query variables;
Y --- A list of observed variables;
--- The corresponding list of observed values;
--- A legitimate elimination ordering.
- Output:
.
- Set the observed variables in all factors to their observed values.
- While
is not empty,
- Remove the first variable z from
.
. Endwhile
- Set h=multiplication of all factors in
combination (by
) of all factors in
.
/* h is a function of variables in X. */- Return
. /* renormalization */
Proof: Consider the following modifications to the
algorithm.
First remove step 1. Then the factor h produced at step 3 is
a function of variables in X and Y. Add a new step
after step 3 that sets the observed variables in
h to their observed values.
We shall first show that the modifications do not change the output of
the algorithm and then show that the output of the modified algorithm is
.
Let 
, 
, and 
be three functions of y and other variables.
It is evident that
If y is a regular variable, we also have
Consequently, the modifications do not change the output of the procedure.
Since the elimination ordering 
is legitimate, it is always the case
that if a deputy variable 
has not been summed out, neither has
the corresponding new regular variable e.
Let 
, ..., 
be the remaining variables in 
at any time
during the execution of the algorithm.
Then, 
implies 
.
This and the fact
that the factorization represented
by a deputation BN is tidy enable us to
repeatedly apply Theorem 3 and conclude
that, after the modifications, the factor created at step 3
is simply the marginal probability 
. Consequently, the
output is 
.
