Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 6.4.2.4 Rejection Sampling

Given some evidence *e*, rejection sampling estimates *P(h|e)*
using the formula

P(h|e) = (P(h ∧e))/(P(e)).

This can be 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(h|e)*. If
the evidence is a conjunction of assignments of values to variables, a
sample can be rejected when any of the variables assigned in the
sample are different from the observed value.

The error in the probability of *h* depends on the number of samples
that are not rejected. The number of samples that are not rejected is
proportional to *P(e)*. Thus, in Hoeffding's inequality, *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.

Sample | Tampering | Fire | Alarm | Smoke | Leaving | Report | |

s _{1} | false | true | true | true | ✘ | ||

s _{2} | false | false | false | false | false | false | ✘ |

s _{3} | false | true | true | true | ✘ | ||

s _{4} | false | false | false | false | false | true | ✔ |

s _{5} | false | false | false | false | false | false | ✘ |

s _{6} | false | false | false | false | false | false | ✘ |

s _{7} | true | false | false | true | ✘ | ||

s _{8} | true | false | false | false | false | true | ✔ |

... | |||||||

s _{1000} | true | false | true | true | ✘ |

**Example 6.24:**Figure 6.11 shows how rejection sampling can be used to estimate

*P(tampering | ¬smoke ∧report)*. Any sample with

*Smoke=true*is rejected. The sample can be rejected without considering any more variables. Any sample with

*Report=false*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.0213*, we would expect about
21 samples out of the 1,000 to not be rejected. Thus, 21 can be used as *n* in
Hoeffding's inequality, which, for example, guarantees an error for
any probability computed from these samples of less than *0.2*
in about 63% of the cases.