Rejection sampling example in Python

Author: Goran Trlin

In many machine learning tasks we need to draw some observations from a specific non-uniform probability distribution. For example, we want to draw 1000 observations from a discrete probability distribution defined by a probability mass function such as this one:

Value Probability
1 10%
5 70%
8 20%

This probability distribution is clearly not uniform, and the random() function in Python draws samples from a uniform distribution (all possible values have the same probability). So, how can we generate some observations from this target distribution using just the random() function? There are multiple ways of achieving this. One of the most popular techniques is a method known as "Rejection Sampling" (also called "Acceptance-Rejection Method").

Rejection Sampling is a three step process:

  1. Using a uniform distribution, pick a random value R on the X axis of the target distribution (so R can be either 1,5 or 8 in our example)
  2. Draw a new value S from a uniform distribution in the range between 0 and the maximum value of the target distribution (in our case S will be between 0.00 and 1.00)
  3. If the value S is less than or equal to the probability of R in the target distribution, keep (accept) the R, otherwise disacrd (reject) it (for example, if R=1 and S=0.44, R is rejected)

Our Python program draws 1000 observations from the non-uniform distribution. Any time the program is run, a new set of observations is generated and every time the number of observations for every possible value (1,5 and 8) is close to what's defined by the probability mass function.

The code for this project can be found on GitHub.

Related subjects

The following subjects are closely related to the methods presented in this article, and learning about them can be useful when playing with the softmax, cross-entropy and MLPs.