Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 38 ยท Variance Reduction

Stratified Sampling and Latin Hypercubes

Split the input range into strata and sample each one to spread points evenly. Compare stratified and Latin hypercube sampling in Python.

Random points clump. Throw 10 darts at a number line segment and you will often leave a big gap in one part and crowd another. Every clump and gap adds noise to a Monte Carlo estimate. Stratified sampling removes the worst of this by splitting the input space into pieces, called strata, and drawing a fixed number of points from each. The points are still random, but they are spread out on purpose.

It is the Monte Carlo version of surveying: a pollster does not phone people at random only, but makes sure each age group and region is represented in the right proportion.

The method in one dimension

To estimate โˆซโ‚€ยน f(u) du, cut [0, 1] into k equal strata [(jโˆ’1)/k, j/k]. Take one draw in each stratum:

Text
U_j = (j โˆ’ 1 + V_j) / k,   V_j ~ Uniform(0, 1),   j = 1, โ€ฆ, k

and average f(U_j). The estimator is unbiased. Its variance is the average of the within-stratum variances divided by k, which is never larger than the plain Monte Carlo variance, because the between-strata part of the variance is removed completely.

Method Where the variance comes from
Plain Monte Carlo whole-function variance
Stratified only variation inside each stratum

For a smooth function, each stratum is almost flat, so the within-stratum variance is tiny. The error then falls faster than the usual 1/โˆšN; for a smooth 1-D integrand with one point per stratum it falls roughly like N^(โˆ’3/2).

Plain vs stratified

We estimate โˆซโ‚€ยน sin(ฯ€u) du = 2/ฯ€ โ‰ˆ 0.63662 using N = 100 points, repeated 2,000 times.

Python Plain vs stratified sampling

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 stratified spread is dramatically smaller. Try changing n to 400 and watch the ratio grow: stratification gains more as the sample size grows, for smooth functions.

Many dimensions and the Latin hypercube

Stratifying each of d dimensions into k pieces needs k^d cells: with d = 10 and k = 10 that is ten billion points, which is hopeless. The Latin hypercube (LHS) is the compromise. To draw N points in d dimensions:

  1. Split every coordinate axis into N equal intervals.
  2. In each dimension, choose a random order of the N intervals.
  3. The i-th point takes interval ฯ€_d(i) in dimension d, with a random position inside it.

Every one-dimensional projection is perfectly stratified (exactly one point per interval), yet you need only N points in total. It works very well when the function is dominated by a few inputs or is nearly additive.

Python Latin hypercube vs random points

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 test function is a product of independent factors with mean 1 plus a sum of sines whose mean is cancelled, so its exact mean is 1. LHS handles the additive part (the sines) almost perfectly, while the product term only improves a little.

Allocation and practical tips

  • Proportional allocation: give each stratum a sample count proportional to its probability. This never does worse than plain Monte Carlo.
  • Optimal (Neyman) allocation: give more points to strata with larger within-stratum standard deviation. It needs those standard deviations, which a pilot run can estimate.
  • Pick strata by what matters. Stratify on the input that most influences the output, or on a cheap predictor of the output.
  • Standard errors: with one point per stratum you cannot estimate the variance from the sample directly. Use two points per stratum, or repeat the whole design independently several times and use the spread of the repeated estimates.

Stratification is the cousin of quasi-Monte Carlo sequences such as Sobol, which spread points even more evenly. They are available in scipy.stats.qmc and are worth trying when your integrand is smooth.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does stratified sampling remove from the variance?

    Each stratum is sampled a fixed number of times, so differences between strata no longer add noise.
  2. 2. Why is full stratification impractical in high dimensions?

    k strata per axis in d dimensions gives k^d cells, which explodes.
  3. 3. In a Latin hypercube sample of N points, each coordinate has:

    Each one-dimensional projection is stratified into N intervals with one point in each.
  4. 4. Which allocation sends more samples to strata with larger spread?

    Neyman allocation is proportional to stratum probability times the within-stratum standard deviation.

Summary

  • Stratified sampling splits the input into strata and draws a fixed number from each, removing between-strata variance.
  • For smooth 1-D integrands the error can fall much faster than 1/โˆšN.
  • Latin hypercube sampling stratifies every coordinate with just N points and scales to many dimensions.
  • Estimate standard errors by repeating the design independently.

Next chapter: Markov Chains for Sampling