2. Nonuniform distributions #

With the LCRNGs discussed so far, $\omega_i$ were sampled according to a uniform distribution $\Omega$. However, it is often desired to sample random numbers according to a different distribution. In the following, two methods are introduced to convert uniformly distributed samples into samples from a nonuniform distribution.

2.1 Inversion method #

Denote the desired nonuniform distribution $X$, with pdf (probability density function) $f(x)$. The inversion method works by drawing uniform samples $\omega \sim \Omega$, and applying the inverse cdf (cumulative density function) $F^\dagger$ to those. The resulting samples are distributed like $X$.

2.1.1 Method #

This leads to the following, simple, procedure. Generate a sample $\omega_i$ from the uniform distribution. Compute

$$
  x_i = F^\dagger(\omega_i).
$$

The samples $x_i$ are now distributed according to $X$.

2.1.2 Intuitive explanation #

The explanation of the method is the following. Recall the definition of a cdf $F$ of $f$:

$$
  F(x) := \int_{-\infty}^x f(t) \,\text{d}t. \tag{2.1}
$$

Note that, thanks to the properties of a pdf, $\text{ran}(F) = [0, 1]$. That is, $F(x)$ takes a number $x$, occurring with probability $f(x)$, and maps it to a unique number in $[0, 1]$. The inverse of $F$, which we denote by $F^\dagger$, instead, takes a number $\omega$ from $[0, 1$], and maps it to a number $x$ belonging to the probability $f(x)$.

2.1.3 Example distributions #

2.2 Rejection method #

The inversion method, explained before, may not always be feasible, for instance when an explicit formulation of the inverse cdf is not available. This is, for instance, the case for the normal distribution. In such situations, one may resort to a numerical alternative. Assume now that $Y$ is the desired distribution, with pdf $g(x)$. The rejection method draws samples from a distribution $X$ that is easy to sample from (for instance using the inversion method). By oversampling some numbers, and discarding others, a distribution $Y$ can be created through the transformation of $X$.

2.2.1 Method #

Choose an auxiliary distribution $X$ with pdf $f(x)$, as well as an oversampling factor $c \in \mathbb{R}$, such that

$$
  g(x) \leq cf(x) \tag{2.2}
$$

for all $x \in \mathbb{R}$. If this condition does not hold, or $X$ cannot be sampled from, the method will not work properly.

Generate samples using the following procedure. First generate a sample $x_i \sim X$. Next to that, generate a sample from a uniform distribution: $\omega_i \sim \Omega$. If

$$
  \omega_i c f(x_i) \leq g(x_i), \tag{2.3}
$$

holds, accept the sample. If it does not hold, reject (discard) the sample. The accepted samples $x_i$ are now distributed like $Y$.

2.2.2 Intuitive explanation #

The rationale of the rejection method is the following. A number $x_i \sim X$ is drawn, and it is known to occur with probability $cf(x_i)$. However, we would like it to occur only as often as $g(x_i)$. Therefore, $x_i$ must be accepted $g(x_i) / (cf(x_i))$ of the times. To make that decision, we randomly accept the number with probability $g(x_i) / (cf(x_i))$, using a draw from the uniform distribution. Note that the ratio is zero when $x_i$ does not occur at all, i.e., $g(x_i)=0$, and one when it occurs as often as $cf(x_i)$.

Another way of thinking is the following. Think of $g(x)$ as the desired histogram. For a number $x_i$, we expect $cf(x_i)$ samples falling into an infinitesimal small bin at $x_i$, however need only $g(x_i)$ samples. (And, by choosing $c$ appropriately, we made sure to always have a sufficient amount of samples.) Thus, when $x_i$ is drawn, it is allowed into its bin $g(x_i)/(cf(x_i))$ of the times. That is, $x_i$ is accepted if $\omega_i \leq g(x_i) / (cf(x_i))$, and rejected otherwise.