rejection sampling

(30 minutes to learn)


Rejection sampling (RS) is a monte carlo method for sampling from a potentially complex distribution p(x) given a simpler distribution q(x). RS is applicable when we can evaluate p(x) easily and sample from q(x) easily. The basic idea is to scale q(x) by some constant K such that K*q(x) >= p*(x) for all x, where p(x) = 1/Z p*(x) for some constant Z (that is, we only need to know p(x) up to a normalization factor, which is common in practice). RS operates by sampling a value x0 from q(x) and then generating a uniform random number, u, between [0, K*q(x0)]. If u <= p*(x0) we keep x0 as a valid sample from p(x), else we discard x0.


This concept has the prerequisites:

Core resources (read/watch one of the following)


Machine learning summer school: Markov chain Monte Carlo (2009)
A video tutorial on MCMC methods.
Location: 13:50 to 15:36
Author: Iain Murray
Information Theory, Inference, and Learning Algorithms
A graudate-level textbook on machine learning and information theory.
Author: David MacKay
Additional dependencies:
  • multivariate Gaussian distribution


Supplemental resources (the following are optional, but you may find them useful)


Bayesian Reasoning and Machine Learning
A textbook for a graudate machine learning course.
Author: David Barber

See also