Lotus BlogTheory - [T18]
Introduction
There are several methods to generate a normal variate. In this post, we will overview some of these methods.
Marsaglia Method
The Marsaglia polar method is a method for generating a pair of independent standard normal random variables, $Z_0$ and $Z_1$.
This method works by choosing random points $(x,y)$ from the square $[-1,1]\times[-1,1]$ until a point is found that is within the unit circle.
or to express it mathematically, we generate $X$ and $Y$ from a uniform distribution on $[-1,1]$ until $x^2+y^2<1$.
Once this point is obtained, we can use its coordinates to generate the pair of random variables $(Z_0,Z_1)$, which will be independent and standard normal.
$$
s = x^2 + y^2 \\
Z_0 = x\sqrt{\frac{-2\ln(s)}{s}} \\
Z_1 = y\sqrt{\frac{-2\ln(s)}{s}}
$$
Box-Muller Method
A direct application of the Marsaglia polar method is the Box-Muller method.
This method is known to be efficient to compute, but has some limitations in the range of values it can generate.
In particular it has a limited domain and it cannot represent values that should be sampled at the very tails of the distribution.
The Box-Muller method works as follows:
As before we sample two independent uniform random variables $U_1$ and $U_2$ from the interval $[0,1]$.
We can then use a property of the two-dimensional cartesian system to generate two independent normal random variables $Z_0$ and $Z_1$.
$$ Z_0 = \sqrt{-2\ln(u_1)}\cos(2\pi u_2) \\ Z_1 = \sqrt{-2\ln(u_1)}\sin(2\pi u_2) $$
Inverse Transform Sampling
The inverse transform sampling method is a method for generating a random sample from a given probability distribution.
We can use this method to generate a normal variate starting from a uniform variate.
To do this we need to define the cumulative distribution function of the normal distribution, let’s call this function $\Phi(x)$.
Once we have defined $\Phi(x)$, we can now use the inverse transform sampling method to generate a normal variate from variate $U$ uniformly distributed on $[0,1]$.
We do this by sampling $U$ and then computing $X=\Phi^{-1}(u)$.
By applying the inverse function of the CDF of the normal distribution to a uniform variate, we obtain the PDF of the normal distribution, therefore $X$ represents a normal variate.