Kochenderfer & Wheeler, Chapter 16

Sampling Plans

Where you look matters. Design your evaluation points to maximally cover the design space with minimum waste.

Prerequisites: Chapter 1 (Introduction).

Chapters

Simulations

Quizzes

Chapter 0: Why Sampling Plans?

When each function evaluation is expensive (running a CFD simulation, building a physical prototype), you cannot afford to sample randomly. You need a sampling plan — a strategic arrangement of evaluation points that maximally covers the design space.

The core idea: A good sampling plan fills the design space uniformly, avoids clusters and gaps, and provides maximum information about the function landscape with minimum evaluations. The plan is chosen before any evaluations — it is a design of experiments, not an adaptive strategy.

Sampling plans are needed when:

Function evaluations are expensive and must be planned in advance The function has no local minima Gradients are available

Chapter 1: Full Factorial

The simplest plan: place points on a regular grid. With k levels per variable and n variables, you need kⁿ points. This grows exponentially — the curse of dimensionality.

Think of it this way: A full factorial design is like placing chess pieces on every square of a 3D chessboard. For 2 variables with 10 levels each, you need 100 points — manageable. For 10 variables, you need 10¹⁰ = 10 billion — impossible. We need smarter approaches.

A full factorial design with 5 levels and 4 variables requires:

5⁴ = 625 points 5 × 4 = 20 points 5 + 4 = 9 points

Chapter 2: Random & Stratified

Random sampling: Sample points uniformly at random. Simple but can leave large gaps and create clusters.

Stratified sampling: Divide the space into strata (sub-regions) and sample one point from each. This guarantees coverage while retaining some randomness. Latin hypercube sampling is the most popular form.

Key insight: Pure random sampling is wasteful in low dimensions because of clustering. Stratified sampling enforces a minimum spread. The benefit grows with sample size — for small budgets, the difference between random and stratified can be dramatic.

Stratified sampling improves over pure random by:

Ensuring coverage of each sub-region of the design space Using more sample points Requiring gradient information

Chapter 3: Latin Hypercube

A Latin hypercube sample (LHS) of m points in n dimensions divides each dimension into m equal intervals and ensures exactly one point falls in each interval along every dimension.

This guarantees uniform projection: when projected onto any single axis, the points are evenly spaced. The positions within each interval are randomized.

Why LHS is popular: It scales linearly in the number of dimensions (m points regardless of n), provides excellent one-dimensional coverage, and allows arbitrary m. The remaining degree of freedom — how to arrange the column assignments — can be optimized for space-filling.

A Latin hypercube sample guarantees that when projected onto any single axis:

Exactly one point falls in each of m equal intervals Points cluster near the center Points form a regular grid

Chapter 4: Space-Filling Metrics

How do you measure whether a sampling plan is "good"? Two common metrics:

Metric	Definition	Optimizes For
Maximin distance	Maximize the minimum pairwise distance	No two points too close
Morris-Mitchell Φ_q	Φ_q = (∑d_i^−q)^1/q	Penalizes small distances heavily

The Morris-Mitchell criterion is optimized over multiple values of q, then the worst case is taken. This gives a robust measure of space-filling quality.

Think of it this way: A space-filling metric measures how evenly spread your points are. The maximin criterion is like placing repelling magnets — they spread as far apart as possible.

The maximin distance criterion maximizes:

The minimum distance between any two sample points The maximum distance from the origin The total number of points

Chapter 5: Space-Filling Subsets

Sometimes you have a set of candidate points X and need to select a subset S ⊂ X of size m that best fills X. Two heuristic approaches:

Method	Strategy
Greedy	Start with one point, repeatedly add the point that most reduces the maximum gap
Exchange	Start with a random subset, repeatedly swap pairs to improve the filling metric

Use case: You ran 100 CFD simulations and want to select 10 for wind-tunnel testing. Greedy or exchange selection finds the 10 that best cover the design space of all 100.

Greedy subset selection adds the next point that:

Most reduces the maximum gap between the subset and the full set Has the highest objective function value Is closest to the current subset

Chapter 6: Quasi-Random Sequences

Quasi-random sequences (low-discrepancy sequences) are deterministic sequences that fill space more uniformly than pseudo-random numbers. They achieve O(1/m) error convergence for numerical integration, compared to O(1/√m) for random Monte Carlo.

The simplest method: additive recurrence with step c = (√5−1)/2 (the golden ratio conjugate). Each dimension uses a different irrational step: √2, √3, √5, etc.

Key insight: Quasi-random sequences beat random sampling because they systematically fill gaps. Each new point is placed to maximize distance from all existing points. The golden ratio produces particularly good 1D sequences because it is the "most irrational" number — hardest to approximate with fractions.

Quasi-random sequences achieve better convergence than random sampling because:

They systematically fill gaps, avoiding clustering They use more sample points They require gradient information

Chapter 7: Sobol & Halton

Two widely-used quasi-random sequences:

Sequence	Construction	Character
Halton	Base-b expansion in reverse; different base per dimension	Simple, good up to ~20 dims
Sobol	Binary fractions using direction numbers from primitive polynomials	Better high-dim coverage, more complex

Sobol sequences are generally preferred for high-dimensional problems because they maintain better uniformity as dimensionality increases. Halton sequences can show correlation patterns in high dimensions.

Practical tip: For most engineering sampling plans, start with a Sobol sequence. Scrambled Sobol sequences add randomization while preserving low discrepancy, combining the benefits of quasi-random coverage with statistical error estimation.

Sobol sequences are preferred over Halton for:

High-dimensional problems where Halton shows correlation patterns 1D problems only Problems where only two samples are needed

Chapter 8: Summary

Method	Type	Best For
Full factorial	Grid	Low dimensions only (≤ 3)
Latin hypercube	Stratified	General-purpose, any dimension
Maximin LHS	Optimized stratified	Best coverage with m points
Sobol sequence	Quasi-random	High-dim, numerical integration
Halton sequence	Quasi-random	Simple, moderate dimensions

Looking ahead: Chapter 17 uses sampling plans to build surrogate models — cheap approximations of the expensive objective function that can be optimized quickly.

The curse of dimensionality makes full factorial designs impractical because the number of points grows:

Exponentially with the number of dimensions Linearly with the number of dimensions It does not grow — factorial is always efficient