Box-Muller Method

We want to determine how to generate $X\sim N(0,1)$, the standard Normal. In particular, find $X$ that draws from the PDF

$$X\sim \frac{1}{\sqrt{2\pi }}\exp \left(-\frac{1}{2}{x}^2\right)$$

from $U[0,1]$? Inversion is computationally hard since there is no closed form for the CDF $F_X$.

The Box-Muller Method tells us to start with $X,Y\sim N(0,1)$ independent RVs and work backwards to $U[0,1]$ RVs. The joint PDF is

$$f_{X,Y}=\frac{1}{2\pi }\exp \left(-\frac{1}{2}(x^2+y^2)\right)$$

Set $R=\sqrt{x^2+y^2}$ and $\theta =\arctan (y/x)$. The transformation is then

$$\begin{array}{rl}(r,\theta )=T(x,y)& =\left(\sqrt{x^2+y^2},\arctan \left(\frac{y}{x}\right)\right)\\ (x,y)=T^{-1}(x,y)& =(r\cos \theta ,r\sin \theta )\end{array}$$

which gives us the Jacobian:

$$\left|\begin{array}{cc}{\partial }_{r}x& {\partial }_{\theta }x\\ {\partial }_{r}y& {\partial }_{\theta }y\end{array}\right|=\left|\begin{array}{cc}\cos \theta & -r\sin \theta \\ \sin \theta & r\cos \theta \end{array}\right|=r$$

Then, the joint PDF form the transformation is

$$f_{R,\Theta }(r,\theta )=f_{X,Y}(x,y)\cdot \left|\frac{\partial (x,y)}{\partial (r,\theta )}\right|=\frac{1}{2\pi }\exp \left(-\frac{1}{2}{r}^2\right)r$$

By factoring, w can show that both $R,\Theta$ are independent.

$$(\star )f_{R,\Theta }=f_{\Theta }(\theta )\cdot f_R(r)$$

where

$$f_{\Theta }(\theta )=\frac{1}{2\pi }{f}_R(r)=r\exp \left(-\frac{1}{2}{r}^2\right)$$

are PDFs. This tells us that

$$\Theta \sim U[0,2\pi ]R\sim F_R={\int }_0^{r}u\exp \left(-\frac{1}{2}{u}^2\right)du=1-\exp \left(-r^2/2\right)$$

Let $U_1,U_2\sim U[0,1]$ be two independent RVs. Then

$$\begin{array}{rlrl}2\pi U_1& \sim U[0,2\pi ]& & \text{(which represents Θ)}\\ {\left[-2\ln (1-U_2)\right]}^{1/2}& \sim F_R& & \text{(which represents R)}\end{array}$$

We can further simplify this; since we have a $1-U_2$ term, and as $U_2\sim U[0,1]$ then $1-U_2\sim U[0,1]$.

---

Finally, that gives us the Box-Muller Method.

Let $U_1,U_2\sim U[0,1]$ be independent RVs. Then $X,Y$ defined below are $\sim N(0,1)$ and independent by

$$\begin{array}{rl}X& ={\left(-2\ln U_2\right)}^{1/2}\cos 2\pi U_1\\ Y& ={\left(-2\ln U_2\right)}^{1/2}\sin 2\pi U_1\end{array}$$

In particular, we use $(\star )$ to get the $\cos ,\sin$ terms in the inverse operation. Indeed,

$$\begin{array}{rl}X& =R\cos \Theta \\ Y& =R\sin \Theta \end{array}$$

This lets us recover $(X,Y)$ from

$$(U_1,U_2)\to (R,\theta )\to (X,Y)$$