See for instan e Figure 1a{
. It is not ne essary, however, that Ssep denes a tight separation.

There an be a small number of other nodes, Soth, inside the separated area, but not in
luded by Smar (Figure 1d). A suÆ
ient 
ondition for the rest of the theory is that the size of the total state spa e, kSsep [ Smar [ Sothk, is small enough to do exa
t 
omputations.

Suppose that we know a parti ular setting of the separator nodes, ~ssep, then 
omputing the onditional distribution of Smar given Ssep is easy:

$$p\left(\vec{s}_{\mathrm{mar}}\mid\vec{s}_{\mathrm{rep}}\,\right)=\sum_{\vec{s}_{\mathrm{th}}\,\in\,S_{\mathrm{th}}}p\left(\vec{s}_{\mathrm{mar}}\,\vec{s}_{\mathrm{th}}\mid\vec{s}_{\mathrm{rep}}\,\right)$$
$$\left({\mathrm{3}}\right)$$

This expression is tra table to ompute sin e Ssep serves as the Markov blanket for the union of Smar and Soth. Thus the a
tual numbers are independent of the rest of the network and an be found either by expli itly doing the summation or by any other more sophisti ated method. Similarly, if we would know the exa t distribution over the separator nodes, we an easily ompute the marginal probability of Smar:

$$p\left({\vec{s}}_{\mathrm{max}}\right)=\sum_{{\vec{s}}_{\mathrm{sep}}\,\in\,S_{\mathrm{top}}}\,\sum_{{\vec{s}}_{\mathrm{th}}\,\in\,S_{\mathrm{th}}}\,p\left({\vec{s}}_{\mathrm{max}}\,{\vec{s}}_{\mathrm{th}}\mid{\vec{s}}_{\mathrm{sep}}\right)p\left({\vec{s}}_{\mathrm{sep}}\right)$$

Unfortunately, in general we do not know the distribution p (~ssep) and therefore we annot ompute p (~smar). We 
an, however, still derive 
ertain properties of the marginal distribution, namely upper and lower bounds for ea h state of Smar. For instan
e, an upper bound on ~smar 
an easily be found by 
omputing

$$p_{+}\left(\,\vec{s}_{\mathrm{mar}}\,\right)=\operatorname*{max}_{q\,\left(\,\vec{s}_{\mathrm{rep}}\,\right)}\,\sum_{\vec{s}_{\mathrm{rep}}\,\in\,S_{\mathrm{top}}}\,\sum_{\vec{s}_{\mathrm{th}}\,\in\,S_{\mathrm{th}}}\,p\,\left(\,\vec{s}_{\mathrm{mar}}\,\vec{s}_{\mathrm{ut}}\,\right|\,\vec{s}_{\mathrm{rep}}\,\right)q\,\left(\,\vec{s}_{\mathrm{rep}}\,\right)$$

$$(4)$$
$$\left({\bar{5}}\right)$$

under the onstraints 8~ssep2Ssep q (~ssep)  0 and P
~ssep2Ssep q (~ssep) = 1. The distribution q (~ssep) 
orresponds to kSsepk free parameters (under the given 
onstraints) used to 
ompute the worst ase (here: the maximum) marginal value for ea h ~smar. Obviously, if q (~ssep) =
p (~ssep) the upper bound 
orresponds to the exa
t value, but in general p (~ssep) is unknown and we have to maximize over all possible distributions. One may re ognize Equation 5 as a simple linear programming (lp) problem with kSsepk variables. With a similar equation we an nd lower bounds p (~smar).

Upto now we did not in lude any information about q (~ssep) we might have into the equation above. But suppose that we already omputed upper and lower bounds on the marginals of other nodes than Smar . How 
an we make use of this knowledge? We investigate our table of all sets of marginal nodes we bounded earlier and take out those that are subsets of Ssep. Obviously, whenever we nd already 
omputed bounds on S0 mar where S0 mar  Ssep 1

,

we 
an be sure that

$$\sum_{\vec{s}_{\mathrm{rep}}\,\in S_{\mathrm{rep}}/\,S_{\mathrm{mar}}^{\prime}}q\left(\,\vec{s}_{\mathrm{rep}}\,\right)=\,q\left(\,\vec{s}_{\mathrm{mar}}^{\prime}\,\right)\,\leq\,p_{+}\left(\,\vec{s}_{\mathrm{mar}}^{\prime}\,\right)$$
mar) (6)
and similarly for the lower bound. These equations are nothing more than extra ontraints on q (~ssep) whi
h we may in
lude in the lp-problem in Equation 5. There 
an be several S0 mar that are subsets of Ssep ea
h dening 2 kS0 mark extra 
onstraints.

$$\left({\mathfrak{h}}\right)$$
