Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 · Sampling Methods

Sampling the Normal Distribution: Box–Muller

Generate normal random numbers with the Box–Muller transform and the polar method, then build correlated normals with a Cholesky factor.

The normal distribution (the bell curve) is everywhere: measurement errors, heights, noise in finance and physics. The inverse transform method is awkward for it, because its CDF has no closed-form inverse. Two classic tricks avoid the problem. In this lesson you will build Box–Muller and the polar method from scratch, then extend to several correlated variables.

The standard normal

The standard normal Z has mean 0 and standard deviation 1. Any normal variable is a shift and scale of it:

Text
X = μ + σ·Z   has mean μ and standard deviation σ.

So it is enough to sample Z.

The Box–Muller transform

Take two independent uniform numbers U₁ and U₂ on (0, 1). Then

Text
Z₁ = √(−2 ln U₁) · cos(2π U₂)
Z₂ = √(−2 ln U₁) · sin(2π U₂)

are two independent standard normals.

Why does it work? Picture the point (Z₁, Z₂) in the plane. Its squared distance from the origin, R² = Z₁² + Z₂², equals −2 ln U₁, which is exponential with mean 2; the angle 2πU₂ is uniform on a circle. The two-dimensional bell surface is rotation-symmetric, so a uniform angle and an exponential R² is exactly the right recipe. The cosine and sine then read off the x and y coordinates.

flowchart LR
  U1["U1 uniform"] --> R["R = sqrt(-2 ln U1)"]
  U2["U2 uniform"] --> T["angle = 2 pi U2"]
  R --> Z["Z1 = R cos(angle)<br/>Z2 = R sin(angle)"]
  T --> Z

Box–Muller: a radius from one uniform, an angle from the other.

Python Box–Muller from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each call to the function produces 2n normals from 2n uniforms. The code uses 1 - rng.random(n) so that u1 cannot be exactly 0.

The polar (Marsaglia) method

Box–Muller needs sine and cosine, which are slowish. The polar method avoids them with a rejection step:

  1. Draw V₁, V₂ uniform on (−1, 1).
  2. Let S = V₁² + V₂². If S ≥ 1 or S = 0, throw the pair away and try again (the point is outside the unit circle).
  3. Otherwise set f = √(−2 ln S / S) and return Z₁ = V₁·f, Z₂ = V₂·f.

About π/4 ≈ 78.5% of pairs are accepted, which echoes the pi experiment from Chapter 1.

Python Polar method and its acceptance rate

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which should you use?

In day-to-day work, call rng.normal or rng.standard_normal. NumPy uses a very fast method called the Ziggurat algorithm. Box–Muller is still valuable to know: it appears in textbooks, in languages without a good built-in, and as a simple way to see how transformations of uniform numbers work.

Correlated normals

Real problems often need several variables that move together, such as the returns of two stocks. To produce a pair with correlation ρ:

Text
Y₁ = Z₁
Y₂ = ρ·Z₁ + √(1 − ρ²)·Z₂

For many variables, use the Cholesky factorization of the covariance matrix Σ: find a lower-triangular matrix L with L Lᵀ = Σ, then X = μ + L Z has mean μ and covariance Σ.

Python Correlated normals with Cholesky

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sample statistics should match the targets to two or three decimals. This recipe is the basis of simulating correlated asset prices, correlated measurement errors and multivariate Gaussian models.

When correlated normals fail with LinAlgError, your covariance matrix is not positive definite (for example, a correlation larger than 1 or two perfectly redundant variables). Check the matrix before sampling.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How do you get a normal variable with mean 10 and standard deviation 3 from a standard normal Z?

    X = μ + σZ shifts by the mean and scales by the standard deviation.
  2. 2. In the Box–Muller transform, what role does U₂ play?

    U₁ determines the radius √(−2 ln U₁); U₂ determines the uniform angle.
  3. 3. About what fraction of pairs does the polar method accept?

    Points accepted lie inside the unit circle, whose area ratio to the square is π/4.
  4. 4. In the Cholesky method, X = μ + L Z has covariance equal to

    Cov(LZ) = L I Lᵀ = L Lᵀ = Σ.

Summary

  • Any normal variable is μ + σZ with Z standard normal.
  • Box–Muller turns two uniforms into two independent normals using a radius and an angle.
  • The polar method does the same without trig functions by rejecting points outside the unit circle.
  • For correlated normals, multiply independent normals by the Cholesky factor of the covariance matrix.
  • In practice call rng.standard_normal; use the from-scratch methods to understand how they work.

Next: Acceptance–Rejection Sampling