the Box-Muller transform
/ BOKS-MYOO-ler /
The normal distribution is the one everyone needs to simulate, yet its cdf has no closed-form inverse, so the easy inverse-transform recipe stalls. The Box-Muller transform is the clever workaround: it turns a pair of independent uniform random numbers directly into a pair of independent standard normal numbers, with nothing but a square root, a logarithm, and sine and cosine.
The trick is to think in two dimensions. Two independent standard normals (Z_1, Z_2) form a point in the plane whose joint density is rotationally symmetric — it depends only on the distance from the origin. In polar coordinates, the angle is uniform around the circle and the squared radius turns out to be exponential. Both of those are easy to generate from uniforms. So the recipe runs the multivariate change of variables backwards: take U_1 and U_2 uniform on (0, 1), set R = sqrt(-2 ln U_1) and angle = 2 pi U_2, and return Z_1 = R cos(angle), Z_2 = R sin(angle). Out come two independent standard normals at once.
Box-Muller is exact (not an approximation), simple to code, and a textbook showcase of how a smart change of variables solves a problem that the direct method cannot. Practical notes: it produces normals in pairs, and U_1 must be strictly positive so the logarithm is defined. A faster cousin, the polar (Marsaglia) form, avoids the trigonometric functions by sampling a point in the unit disc instead.
Suppose U_1 = 0.5 and U_2 = 0.25. Then R = sqrt(-2 ln 0.5) approx sqrt(1.386) approx 1.177, and the angle = 2 pi (0.25) = pi/2. So Z_1 = 1.177 cos(pi/2) = 0 and Z_2 = 1.177 sin(pi/2) approx 1.177. Two uniforms have produced two standard normals in one shot.
A radius from an exponential and a uniform angle combine into two independent normals.
It generates normals in pairs and needs U_1 strictly above 0 (else ln U_1 blows up). To get Normal(mu, sigma^2), scale and shift: mu + sigma times Z.