Box-Muller transform

Since the normal distribution is ubiquitous, the need for simulating a normally distributed random variable is strongly felt. The most straightforward method for simulating a random variable is the Probability Integral Transform (PIT). The PIT requires the distribution function of the rv to be known explicitly. The distribution function of the standard normal distribution is

which has been extensively tabulated but which cannot be expressed using only elementary functions (log, exp, trigonometric functions etc...).

The Box-Muller transform

Standard normal r.v.

The Box-Muller tranform circumvents this difficulty by using a smart trick which is detailed in the Tutorial below. The net result is as follows :

It is remarkable that the normal distribution can this way be simulated using only uniformly distributed variables and simple formulas where the normal distribution is nowhere to be found.

This website makes an extensive use of the Box-Muller transform in interactive animations.

The basic Box-Muller transform can further be improved into the "Marsaglia method" that is also described in the Tutorial below.

General normal r.v.

By reporting to the properties of linear transformations of random variables, the reader will easily show that two independent normal rvs X and Y of common distribution N(µ, σ²) can be simulated as

Multivariate normal distribution

Let x be a random vector following a multivariate normal distribution. How can x be simulated ?

We mentioned that the Mahalanobis transformation is particularly useful for transforming an arbitrary multinormal distribution into a spherically symmetric standard multinormal distribution. The Box-Muller transform can then be used for simulating the (independent) marginal components of this standard distribution, and therefore for simulating a standard normal vector. The inverse Mahalanobis transformation then transforms this simulated vector back into a random vector with the desired mutinormal distribution.

More specifically, we show here that the key ingredient of the Mahalanobis transformation is a matrix G such that

where Σ is the covariance matrix of the multinormal distribution. Such a matrix is called a "square root" of a positive definite matrix.

G can be chosen in a number of ways but it is usual to assume G to be the (unique) symmetric square root of Σ. Although this assumption is needed when studying the distribution of the Mahalanobis distance, it is not necessary for our purpose. Actually, from a computational standpoint, it is more convenient to choose G as the Cholesky square root of Σ.

In this Tutorial, we first remind the reader of the method used for calculating the normalization coefficient of the normal distribution. This method is the starting point of the Box-Muller transform, as it shows that some problems about the normal distribution may be more easily solved by considering first a similar problem on the bivariate normal distribution.

In fact, we'll see that the Box-Muller transform amounts to simulating the standard binormal distribution expressed in polar coordinates.

We then describe an improvement of the Box-Muller transform sometimes called the "Marsaglia method", whose goal is to avoid having to calculate the sinus and cosinus that are found in the original method. The price to pay for reducing the load on the computer processor is that about 21% of the draws have to be rejected as inappropriate for the simulation, but the overall result is a speed-up of the basic Box-Muller transform.

Normal distribution
Probability Integral Transform

Download this Glossary

Why not the Probability Integral Transform ?

The Box-Muller transform

Standard normal r.v.

General normal r.v.

Multivariate normal distribution