AI Glossary / Statistics and probability / Advanced

Nested sampling algorithm

Definition

Nested sampling is a numerical method for estimating Bayesian evidence and obtaining weighted posterior samples. It explores successively smaller regions of prior probability mass selected by increasing likelihood thresholds. Evidence combines likelihood with prior mass; it is not simply the largest likelihood encountered during a search.

What it means

A narrow region with a high likelihood may contribute less evidence than a broader region with moderately high likelihood. Nested sampling tracks both ingredients. Its nested regions are likelihood-constrained subsets of the prior, rather than nested datasets or a sequence of regression hypotheses. The resulting evidence can support model comparison when models and priors are specified coherently.

How it works

Begin with live points drawn from a proper prior. Repeatedly remove the lowest-likelihood point and replace it with a draw from the prior constrained above that likelihood. Estimate the shrinking prior mass and combine likelihood values with mass differences to approximate the evidence integral. Normalize contribution weights to obtain posterior weights. Reliable exploration of each constrained region is central to accuracy.

Three practical examples

• A scientific team compares two generative models using their marginal likelihoods. It checks prior sensitivity rather than assuming the model with the highest fitted likelihood must have the greatest evidence.
• An engineering team estimates uncertain calibration parameters with several plausible parameter regions. It tests whether the sampler explores all important regions instead of repeatedly visiting only one.
• An AI research team validates a probabilistic simulator on a problem whose evidence is known analytically. Agreement provides a useful implementation check before attempting a harder problem with no closed-form answer.

Think of it this way

Imagine counting the contents of a landscape by moving inward through successive height contours. Height represents likelihood, while each contour encloses some fraction of prior probability. A peak's contribution depends on both its height and the probability mass around it. Looking only for the tallest peak answers a different question.

Worked example

Consider an original one-parameter model. A probability theta lies between zero and one with a uniform prior. We observe one Bernoulli success, so the likelihood is L(theta) = theta. The exact evidence is the integral of theta from zero to one, which equals 1/2. The highest possible likelihood is one, demonstrating immediately that evidence and maximum likelihood are different quantities.

For a likelihood threshold lambda between zero and one, the allowed region is theta greater than lambda. Its prior mass is X(lambda) = 1-lambda. Reversing this relationship gives L(X) = 1-X. Integrating this function over X from zero to one again gives 1/2. This is the prior-mass representation that nested sampling approximates.

For a transparent quadrature illustration, divide the prior mass into four equal shells with boundaries 1, 0.75, 0.50, 0.25, and 0. Use their midpoint likelihoods: 0.125, 0.375, 0.625, and 0.875. Multiplying each by shell mass 0.25 gives contributions 1/32, 3/32, 5/32, and 7/32. Their sum is 16/32 = 1/2. This deterministic midpoint calculation happens to integrate the linear function exactly; it is not a claim that a four-point stochastic run always returns exact evidence.

The normalized shell contributions are 1/16, 3/16, 5/16, and 7/16. They illustrate why retained points should not automatically receive equal posterior weights. The exact posterior density is 2theta, with mean 2/3. Using the four midpoint theta values and those normalized weights gives an approximate mean of 21/32, or 0.65625. Exact evidence in this simple quadrature therefore does not imply that every posterior summary is exact.

Now illustrate the live-point update separately. Suppose four initial live points are 0.10, 0.40, 0.60, and 0.90. Remove 0.10, the smallest likelihood. A valid replacement is uniform on (0.10,1). Using the transformed draw 0.10 + 0.90u with u = 0.80 produces 0.82. The updated live set is 0.40, 0.60, 0.82, and 0.90; the next discarded likelihood is 0.40. Replacing the removed point with an unconstrained prior draw could violate the algorithm.

In this toy problem, the true mass above the first discarded threshold is 0.90. A common typical shrinkage approximation for four live points after one iteration is exp(-1/4), approximately 0.779. These need not coincide in a particular run: prior-mass shrinkage is random, and the approximation is not an exact observed volume.

Finally, change the prior density to 2theta while keeping the same observed success. The evidence becomes the integral of 2theta squared, equal to 2/3. This changes the probabilistic model, not merely the numerical algorithm. It demonstrates why evidence comparisons must disclose priors and cannot be interpreted independently of them.

Illustrative case study

This fictional case concerns Cedar Calibration, an imaginary modeling team. Its first validation compares the sampler's output only with the maximum likelihood, incorrectly expecting a value near one. A reviewer computes the uniform-prior evidence of one-half and also checks the posterior mean of two-thirds.

The team then runs repeated numerical fits, examines differences between runs, and checks whether weighted summaries approach the analytical targets. It separates integration error from deliberate changes in the prior. The case describes a validation workflow; no actual software benchmark or measured commercial benefit is asserted.

Common misconceptions and mistakes

A likelihood constraint alone does not ensure that replacement points correctly represent the constrained prior. Poor exploration can miss important regions and bias results. Practical dependence between generated points also needs attention.

A stopping estimate based on the largest currently observed live-point likelihood is not a universal guarantee that no important unseen peak remains. Likewise, adding more live points can improve resolution without repairing an incorrect likelihood, prior transformation, or implementation.

Business use

Use evidence estimates with numerical uncertainty, convergence checks, and prior-sensitivity analysis. If evidence influences a consequential model choice, compare the competing models' definitions and assumptions as carefully as the reported numerical values. The toy example's change from one-half to two-thirds reflects a changed prior, so it should not be advertised as an algorithmic performance improvement.

People also ask

Does nested sampling only estimate evidence?

No. The contribution weights also support posterior estimation.

Can ordinary uniform sampling over an unlimited parameter range provide the prior?

No proper uniform probability distribution exists over the whole real line. The specified prior must be normalizable and correctly sampled.

Check your understanding

Why do the four shell weights differ despite equal shell masses?

Answer: Their likelihood values differ.

Why is 0.779 not the true first remaining mass in the illustrated live set?

Answer: It is a typical shrinkage approximation, whereas the known threshold leaves mass 0.90 in this particular example.

Related terms

• Likelihood
• Bayes factor
• Bayesian evidence
• marginal likelihood
• prior mass
• posterior weighting
• live points
• numerical quadrature

Learn next

Reproduce the shell calculation and posterior-mean approximation, then distinguish deterministic quadrature error from uncertainty in a stochastic nested-sampling run.

More in Statistics and probability

• Nemenyi test - The Nemenyi test is a rank-based multiple-comparison procedure.
• Nested case - control study - A nested case - control study selects cases and controls from a defined cohort.
• Nested hypothesis - Nested hypotheses form an ordered sequence in which every hypothesis permits only possibilities also permitted by each later hypothesis.
• Net reclassification improvement - Net reclassification improvement, or NRI, compares how two risk-prediction models move observations upward or downward in predicted risk.
• Network sampling - Network sampling is a survey approach in which a target item can be reported through several linked sampling units.
• Networked model - A networked model assigns a local hypothesis space to each node of a network used for federated learning.

Sources

Dynesty developers, Background, nested-sampling algorithm, evidence and posterior weighting, and prior requirements: https://dynesty.readthedocs.io/en/stable/overview.html . The Bernoulli model, shell calculations, live-point example, and Cedar Calibration case are original illustrations.

Previous: Nested Relation Next: Nested sequential Monte Carlo