将均匀分布转换为正态分布

1. Overview

In this tutorial, we’ll study how to convert a uniform distribution to a normal distribution.

We’ll first do a quick recap on the difference between the two distributions.

Then, we’ll study an algorithm, the Box-Muller transform, to generate normally-distributed pseudorandom numbers through samples from the uniform distribution.

At the end of this tutorial, we’ll know how to build a pseudorandom generator that outputs normally-distributed values.

2. Uniformity and Normality

The first point in this discussion is to understand how a uniform and normal distribution differ. This lets us concurrently understand what we need to transform one into the other and vice-versa.

2.1. The Uniform Distribution

The uniform distribution also takes the name of the rectangular distribution, because of the peculiar shape of its probability density function:

Rendered by QuickLaTeX.com

Within any continuous interval [a, b] , which may or not include the extremes, we can define a uniform distribution U(a, b) . This is the distribution for which all possible arbitrarily small intervals $\epsilon \in [a, b]$ , with or without extremes, have the same probability $P(\epsilon) = \frac {1} {b-a}$ of occurrence. We can verify that this is a proper probability desity function by calculating the area under the curve:

$Pr[a \leq x \leq b] = \int_a^b \text{PDF}(x) dx = (b-a) \times \frac {1} {b-a} = 1$

2.2. The Normal Distribution

The normal distribution, instead, is a distribution characterized by this probability density function:

$\text{PDF}(x|\sigma, \mu) = \frac {1} {\sigma \sqrt{2\pi}} \times e^{-\frac{1}{2} (\frac{x-\mu}{\sigma})^2}$

In here, $\sigma$ and $\mu$ indicate, respectively, the standard deviation and the mean of the distribution. This is its corresponding chart, for $\sigma=1$ and $\mu=0$ :

Rendered by QuickLaTeX.com

We can see that the values contained in a normal distribution aren’t equally likely, as the corresponding values of the uniform distribution were. This is due to two reasons.

The first reason is that the uniformly-distributed values with non-zero probability are all contained in a finite interval, while those of the normal distributions aren’t. We noted that the values with a non-zero probability in the normal distribution occupy the whole domain $(-\infty, \infty)$ . This isn’t true for the uniform distribution, so we’ll need some kind of transformation to convert the finite interval [a, b] to the other.

The second reason is that all values in discrete uniform distributions have the same probability of being drawn. For discrete normal distributions, instead, any two values $x_1 \neq x_2$ have corresponding probabilities $P(x_1) \neq P(x_2)$ different from one another. Of course, with the exception of the case in which $\frac {x_1 + x_2} {2} = \mu$ .

3. Box-Muller Transform

3.1. The Definition of the Algorithm

We can therefore identify an algorithm that maps the values drawn from a uniform distribution into those of a normal distribution. The algorithm that we describe here is the Box-Muller transform. This algorithm is the simplest one to implement in practice, and it performs well for the pseudorandom generation of normally-distributed numbers.

The algorithm is very simple. We first start with two random samples of equal length, u_1 and u_2 , drawn from the uniform distribution U(0,1) . Then, we generate from them two normally-distributed random variables z_1 and z_2 . Their values are:

$z_1 = \sqrt{-2 \ln (u_1)} \cos (2 \pi u_2)$
$z_2 = \sqrt{-2 \ln (u_1)} \sin (2 \pi u_2)$

3.2. Empirical Testing

We can empirically test whether the procedure grants us a normally distributed random variable or not. This is done, concretely, by plotting the histogram of a bivariate distribution u_1, u_2 drawn from the uniform distribution. Then, we can compare it with the histogram of the corresponding transformed distributions:

index

We made the charts above with two random samples u_1, u_2 of size 10,000. We can see that the corresponding distributions z_1, z_2 have the typical bell shape of a Gaussian distribution.

3.3. Deriving the Expression

We can understand how to derive the two expressions above if we imagine positioning the variables u_1, u_2 in the Cartesian plane. There, each of them corresponds to one of the two coordinates of a point:

Rendered by QuickLaTeX.com

Then, we can express the point in polar coordinates, identifying an angle $\theta$ and a distance of from the origin. This is because a bivariate normal distribution (X, Y) has a norm that corresponds to $\sqrt{-2 \ln u_1}$ . Instead, the angle $\theta$ in the polar coordinates corresponds to $2 \pi u_2$ .

Finally, this lets us map the two variables u_1, u_2 in the original cartesian system to the normally-distributed variables z_1, z_2 , as:

$z_1 = r \cos(\theta)$

$z_2 = r \sin(\theta)$

Lastly, we can easily notice how these expression are equivalent to the ones we gave above.

3.4. The Limitations of Box-Muller

This algorithm performs well if we use it to generate a relatively short sequence of normally-distributed values. For a sufficiently short sequence, in fact, we expect most of its numbers to be contained within three standard deviations of the distribution’s mean. If, however, the sequence is large, we expect $\boldsymbol{\approx} \textbf{0.2\%}$ of the values to be located outside of that interval.

In computers with finite accuracy for the representation of decimal digits, there’s a limit to how close to zero can we draw a number from the uniform distribution. This changes depending on whether we use double or floating-point precision, but still implies a non-zero resolution to our capacity to draw from a continuous uniform distribution.

As a consequence, we can’t represent all possible values from the normal distribution by using the Box-Muller algorithm, but only those in sufficient proximity of the mean. A good rule of thumb is to state that the tail of the distribution truncates at $\approx 6.5$ standard deviations if we use 32-bits precision. If we use 64-bit precision instead, we can expect the generated values to be located within $\approx 9.5$ standard deviations.

3.5. Alternatives to Box-Muller

Alternatively, we can use other, more complex algorithms if we need to obviate the limitations of Box-Muller.

The first is the Ziggurat Algorithm, which uses the rejection sampling principle and generates normally-distributed values on the basis of a random seed and a lookup table.

The second is the Ratio-of-Uniforms, which demands the storage in memory of several double-precision values, but is otherwise computationally fast and simple.

The third is to calculate the inverse function to the cumulative distribution function for a normal distribution. This corresponds to calculating the quantile function of a normal distribution which, for standard normal distributions, coincides with the probit function.

4. Conclusion

In this tutorial, we studied how to generate a pseudorandom variable that’s distributed normally.

We did so by sampling from a bivariate uniform distribution and then applying the Box-Muller transform on them.

Persistence

REST

Security

1. Overview

2. Uniformity and Normality

2.1. The Uniform Distribution

2.2. The Normal Distribution

3. Box-Muller Transform

3.1. The Definition of the Algorithm

3.2. Empirical Testing

3.3. Deriving the Expression

3.4. The Limitations of Box-Muller

3.5. Alternatives to Box-Muller

4. Conclusion