Box-Muller Algorithm

Description

$x_1$ and $x_2$ are two independent $uniform(0,1)$ random variables, and let

$r = \sqrt{-2 \log{x_1}}, \quad \theta = 2 \pi x_2$

Then

$z_1 = r \cos{\theta}, \quad z_2 = r \sin{\theta}$

are independent $normal(0,1)$ random variabls.

Proof

$p(z_1,z_2) = \frac{1}{2\pi} e^{\frac{-(z_1^2 + z_2^2)}{2}}$

$f(r,\theta) = \frac{1}{2\pi} e^{\frac{-r^2}{2}}$

$\theta = 2 \pi x_2.$

$\int \int p(z_1,z_2) dz_1 dz_2 = \int \int rf(r,\theta) dr d\theta$

$p(r) = r e^{\frac{-r^2}{2}}$

$F(r) = 1 - e^{\frac{-r^2}{2}}$

$F^{-1}(y) = \sqrt{-2\log(1-y)}$

$r = \sqrt{-2\log(x_1)}$

Polar form

$s = x^2 + y^2, sin(\theta) = y/\sqrt{s}, cos(\theta) = x/\sqrt{s}$

$r = \sqrt{-2 \log{s}} \\ z_1 = r y/\sqrt{s} \\ \quad z_2 = r x/\sqrt{s}$

do
$x,y \sim U(0,1)$
while $x^2 + y^2 > 1$