Many problems are too big for exact inference, so 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 mapped to and from probabilities. For example, the probability $P(a)=0.14$ means that out of 1000 samples, about 140 will have $a$ true. Inference can be carried out by going from probabilities into samples and from samples into probabilities.

The following sections consider three problems:

• •

  how to generate samples,

• •

  how to infer probabilities from samples, and

• •

  how to incorporate observations.

These form the basis for methods that use sampling to compute the posterior distribution of a variable in a belief network, including rejection sampling, importance sampling, particle filtering and Markov chain Monte Carlo.