Generating a random value with a custom distribution
To generate random values according to a custom distribution using a function that generates uniform random values between 0 and 1 you can use the inverse transform sampling method.
- First we create a cumulative distribution function (CDF for short)
- We then mirror the CDF along y = x
- The resulting function can be applied to a random value between 0 and 1
Suppose we want to generate a random point with the following distribution:
- 1/5 of the points uniformly between 1 and 2, and
- 4/5 of the points uniformly between 2 and 3.
The probability density function (PDF) in this case would look like this:
For such simple distribution, inverse transform sampling is a bit of an overkill, but let's go with this since a simple example makes it easier to understand the general idea.
Step 1: Create the CDF
The CDF is, as the name suggests, the cumulative version of the PDF. Intuitively: While PDF(x) describes the number of random values at x, CDF(x) describes the number of random values less than x.
Since we're working with reals, the CDF is expressed as the integral of the PDF. In this case the CDF would look like:
To see why the CDF is useful, imagine that we shoot bullets from left to right at uniformly distributed heights. As the bullets hit the line, they drop down to the ground:
See how the density of the bullets on the ground corresponds to our desired distribution! We're almost there!
Step 2: Mirror the CDF along y = x
The problem is that for this function, the x axis is the input and the y axis is the output. We can only “shoot bullets from the ground straight up”! We need the inverse function!
This is why we mirror the whole thing; x becomes y and y becomes x:
We call this CDF-1.
Step 3: Apply the resulting function to a uniform value between 0 and 1
With the CDF-1 we have all we need. We now simply feed it with uniformly random values between 0 and 1:
The result is random values with the desired distribution.
A Real World Example
This technique is used to derive the algorithm for generating a uniformly random point on a disc. See article Generating a random point within a circle (uniformly).