8.6 Stochastic Simulation

8.6.3 Rejection Sampling

Given some evidence e, rejection sampling estimates P(he) using the formula


This is computed by considering only the samples where e is true and by determining the proportion of these in which h is true. The idea of rejection sampling is that samples are generated as before, but any sample where e is false is rejected. The proportion of the remaining, non-rejected, samples where h is true is an estimate of P(he). If the evidence is a conjunction of assignments of values to variables, a sample is rejected when any variable is assigned a value different from its observed value.

Sample Tampering Fire Alarm Smoke Leaving Report
s1 false false true false
s2 false true false true false false
s3 false true true false
s4 false true false true false false
s5 false true true true true true
s6 false false false true false false
s7 true false false false
s8 true true true true true true
s1000 true false true false
Figure 8.29: Rejection sampling for P(tamperingsmoke¬report)
Example 8.41.

Figure 8.29 shows how rejection sampling is used to estimate P(tamperingsmoke¬report). Any sample with Smoke=false is rejected. The sample is rejected without considering any more variables. Any sample with Report=true is rejected. The sample average from the remaining samples (those marked with ✴) is used to estimate the posterior probability of tampering.

Because P(smoke¬report)=0.0128, we would expect about 13 samples out of the 1000 to have smoke¬report true; the other 987 samples would have smoke¬report false, and so would be rejected. Thus, 13 is used as n in Hoeffding’s inequality, which, for example, guarantees an error for any probability computed from these samples of less than 0.25 in about 86% of the cases, which is not very accurate.

The error in the probability of h depends on the number of samples that are not rejected, which proportional to P(e). Hoeffding’s inequality can be used to estimate the error of rejection sampling, where n is the number of non-rejected samples. Therefore, the error depends on P(e).

Rejection sampling does not work well when the evidence is unlikely. This may not seem like that much of a problem because, by definition, unlikely evidence is unlikely to occur. But, although this may be true for simple models, for complicated models with complex observations, every possible observation may be unlikely. Also, for many applications, such as in diagnosis, the user is interested in determining the probabilities because unusual observations are involved.