findings. Almost all of these nodes were leaf nodes in the network. We believe that this constituted very realistic test cases for the algorithms. The distribution of the prior probability of evidence, Pr(E = e), across all test runs of our experiments is shown in Figure 4.

The least likely evidence was 5.54 × 10- 42 , the most likely evidence was 1.37 × 10- 9 , and the median was 7 × 10- 24

![0_image_0.png](0_image_0.png)

Figure 5: A typical plot of convergence of the tested sampling algorithms in our experiments
- Mean Square Error as a function of the execution time for a subset of the CPCS network with 20 evidence nodes chosen randomly among plausible medical observations (Pr(E = e) = 3.33 × 10- 26 in this particular case) for the AIS-BN,
the SIS, and the LW algorithms. The curve for the AIS-BN algorithm is very close to the horizontal axis.

Figures 5 and 6 show a typical plot of convergence of the tested sampling algorithms in our experiments.  The case illustrated involves updating the CPCS network with 20 evidence nodes. We plot the MSE after the initial 15 seconds during which the algorithms start converging. In particular, the learning step of the AIS-BN algorithm is usually completed within the first 9 seconds. We ran the three algorithms in this case for 150 seconds rather than the 60 seconds in the actual experiment in order to be able to observe a wider range of convergence. The plot of the MSE for the AIS-BN algorithm almost touches the X axis in Figure 5. Figure 6 shows the same plot in a finer scale in order to show more detail in the AIS-BN convergence curve. It is clear that the AIS-BN algorithm dramatically improves the convergence rate. We can also see that the results of AIS-BN converge to exact results very fast as the sampling time increases. In the case captured in Figures 5 and 6, a tenfold increase in the sampling time (after subtracting the overhead for the AIS-BN algorithm, it corresponds to a 21.5-fold increase in the number of samples) results in a 4.55-fold decrease