The Box-Muller Transform

- 5 mins

Every statistician has a favorite way of generating samples from a distribution (not sure if I need a citation for this one). From rejection sampling to Hamiltonian Monte Carlo, there are countless methods to choose from (my personal favorite is rnorm).

One of the most interesting and counterintuitive sampling techniques is the Box-Muller transform. I’m not sure how widely it’s used today, but given two samples from a uniform distribution, it can generate two independent samples from a standard normal distribution.

The idea behind the Box-Muller transform is to imagine two independent samples plotted in the Cartesian plane, and then represent these points as polar coordinates. Recall, to transform to polar, we need the distance between and the origin along with , the angle this line segment makes with the x-axis.

We start with the distance from the origin, . For simplicity, we work with . The sum of two independent squared standard normals follows a chi-squared distribution with 2 degrees of freedom. It is also a known fact that a chi-squared distribution with 2 degrees of freedom is equivalent to a random variable, which is itself equivalent to a variable. Finally, we can express an exponential random variable as the log of a uniform. More succinctly,

where

What about the angle, ? If we write the joint density of and , we can see

Thus, once we have , the squared distance between and the origin, the joint distribution of and is uniform. That is, as long as is a pair satisfying , it can be any point on the circle with radius . As a result, we can simply take , where

Putting all these results together, if we take and for , we have the polar coordinates for two independent standard normal draws. Thus, converting back to Cartesian, we have

This is straightforward to implement in R:

nsims = 10000
samples = rep(NA,nsims*2)
for (sim in 1:nsims) {
  us = runif(2)
  R = sqrt(-2*log(us[1]))
  theta = 2*pi*us[2]
  samples[2*sim] = R*cos(theta)
  samples[2*sim-1] = R*sin(theta) 
}

Using the above code, I compared the histogram of Box-Muller samples to those using rnorm, which were nearly identical:

Box-Muller Samples

Interesting, but this is nothing more than a cool sampling trick, right? Wrong. If we represent normal random variables in Box-Muller form, it can become easier to prove results about the normal distribution.

For example, consider the problem of proving that for independent draws , is independent of , and both distributed as . A proof that doesn’t require the use of pdfs involves representing and in Box-Muller form (I first saw this solution in Joe Blitzstein’s class Stat 210, which I encourage any Harvard student who’s reading this to take). Let and , as in the representation above. Thus, , and . This form gives us

Note that we use the trigonometric identities for and in the derivation. The final form should look familiar – we’ve recovered the Box-Muller representation, albeit with some modifications. The in front scales the standard normal so it now has a variance of 2. Additionally, note that we are using as instead of . However, we do not have to worry about it as it still results in a uniform sample over the possible angles.

Thus, and are independent draws from the distribution .

Keyon Vafa

Keyon Vafa

Statistics PhD student focusing on machine learning

rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora