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

### 6.4.2 Approximate Inference Through Stochastic Simulation

Many problems are too big for exact inference, and one must resort to approximate inference. One of the most effective methods is based on generating random samples from the (posterior) distribution that the network specifies.

**Stochastic simulation** is based on the idea that a set of samples can
be used to compute probabilities. For example, you could interpret the
probability *P(a)=0.14* as meaning that, out of 1,000 samples, about 140
will have *a* true. You can go from (enough) samples into
probabilities and from probabilities into samples.

We consider three problems:

- how to generate samples,
- how to incorporate observations, and
- how to infer probabilities from samples.

We examine three methods that use sampling to compute the posterior distribution of a variable: (1) rejection sampling, (2) importance sampling, and (3) particle filtering.