{ "id": "epxt2sf9q4", "slug": "nested-sampling", "title": "Nested sampling", "updated": "2026-09-30", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.statistics", "label": "Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics" }, { "id": "physical.math.statistics.stats_bayesian", "label": "Bayesian statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics.stats_bayesian" }, { "id": "physical.math.statistics.stats_bayesian.bayes-computation", "label": "Bayesian computation and software", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics.stats_bayesian.bayes-computation" } ], "geo": [ { "id": "geo.nongeo.t2001.physical.math.statistics", "label": "Non-geographic · 2001 to 2020: Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.physical.math.statistics", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.physical" }, { "id": "geo.nongeo.t2001.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.physical.math" }, { "id": "geo.nongeo.t2001.physical.math.statistics", "label": "Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.physical.math.statistics" } ] } ], "excerpt": "Nested sampling is a Monte Carlo algorithm in Bayesian statistics, introduced by John Skilling in 2006, that computes a model's evidence with posterior samples as a by-product.", "snippet": "Nested sampling is a Monte Carlo algorithm in Bayesian statistics, introduced by John Skilling in 2006, that computes a model's evidence with posterior samples as a by-product.", "node": "physical.math.statistics.stats_bayesian.bayes-computation", "markdown": "# Nested sampling\n\nNested sampling is a [Monte Carlo algorithm](https://www.edgepedia.org/monte-carlo-algorithm) in [Bayesian statistics](https://www.edgepedia.org/bayesian-statistics) that computes the evidence (marginal likelihood) \\( Z \\) of a statistical model, with posterior samples as a by-product. It converts a high-dimensional integral over parameter space into a one-dimensional sum by iteratively shrinking the prior volume, and it is popular in cosmology, astrophysics, and particle physics.[1](https://doi.org/10.1214/06-ba127)\n\n| Key fact | Value |\n|---|---|\n| Prime result | Bayesian evidence; posterior samples are an optional by-product[1](https://doi.org/10.1214/06-ba127) |\n| Core transformation | \\( Z = \\int_0^1 L(X)\\,dX \\) over sorted prior mass \\( X(\\lambda) \\)[1](https://doi.org/10.1214/06-ba127) |\n| Shrinkage per iteration | Prior mass ratio distributed as \\( \\mathrm{Beta}(n_{\\mathrm{live}}, 1) \\); mean factor \\( N/(N+1) \\approx e^{-1/N} \\)[2](https://arxiv.org/pdf/2205.15570) |\n| Statistical error | Scales as \\( 1/\\sqrt{n_{\\mathrm{live}}} \\); Skilling's estimate \\( \\sqrt{H/M} \\)[2](https://arxiv.org/pdf/2205.15570) |\n| Typical termination | Stop when \\( Z_{\\mathrm{live}}/Z_i < \\varepsilon \\), e.g. \\( \\varepsilon = 10^{-3} \\)[3](https://ar5iv.labs.arxiv.org/html/2101.09675) |\n| Iterations needed | Roughly \\( n_{\\mathrm{live}} \\cdot H \\), where \\( H \\) is the information gain (KL divergence from prior to posterior)[2](https://arxiv.org/pdf/2205.15570) |\n| Introduced by | John Skilling, \"Nested sampling for general Bayesian computation\", Bayesian Analysis, 2006[1](https://doi.org/10.1214/06-ba127) |\n\n## How it works\n\nThe evidence \\( Z = \\int L\\,dX \\), with \\( dX \\) the element of prior mass, is the normalization a model needs for model comparison, and it is the hard part: standard MCMC yields only normalized posterior samples and fails to give the evidence at all; historically it required thermodynamic integration bridging prior and posterior.[1](https://doi.org/10.1214/06-ba127)\n\nSkilling's reparameterization defines \\( X(\\lambda) = \\int_{L(\\theta)>\\lambda} \\pi(\\theta)\\,d\\theta \\), the cumulant prior mass above likelihood level \\( \\lambda \\), which decreases from 1 to 0 as \\( \\lambda \\) rises. The evidence becomes a one-dimensional integral, whose integrand is positive and nonincreasing in the sorted prior mass (apart from ties or plateaus).[1](https://doi.org/10.1214/06-ba127)\n\nThe shrinkage follows from order statistics. With \\( N \\) live points drawn uniformly from the prior, the fraction of prior mass remaining after deleting the lowest-likelihood point is distributed as \\( X_{i+1}/X_i \\sim \\mathrm{Beta}(N,1) \\).[2](https://arxiv.org/pdf/2205.15570) Its mean is the expectation of the largest of \\( N \\) uniform(0,1) numbers, so \\( X_j \\) is a random product of shrinkage factors with \\( E[X_j] = (N/(N+1))^j \\) after \\( j \\) steps.[4](https://doi.org/10.1086/501068)\n\n## How it is done\n\nA practitioner runs the following loop.[5](https://dynesty.readthedocs.io/en/v2.1.5/overview.html)\n\n1. Draw \\( N \\) live points from the prior and evaluate their likelihoods.\n2. Remove the lowest-likelihood point (a \"dead point\") and replace it with a draw from the prior subject to \\( L \\ge L_{\\min} \\). This likelihood-restricted prior sampling (LRPS) is the key implementation step, and the constrained region can be extremely thin.[3](https://ar5iv.labs.arxiv.org/html/2101.09675)\n3. Accumulate evidence as a weighted sum \\( Z \\approx \\sum_i \\Delta V_i \\times L_i \\), commonly by the trapezium rule with weights \\( (X_{i-1} - X_{i+1})/2 \\).[2](https://arxiv.org/pdf/2205.15570)\n4. Terminate when the remaining live-point evidence \\( Z_{\\mathrm{live}} = L_{\\max} \\cdot X_i \\) is negligible against the accumulated \\( Z_i \\): \\( Z_{\\mathrm{live}}/Z_i < \\varepsilon \\) with \\( \\varepsilon = 10^{-3} \\) typical.[3](https://ar5iv.labs.arxiv.org/html/2101.09675) MultiNest-style runs use \\( \\Delta Z/Z \\le \\mathrm{tol} \\) with the maximum likelihood, PolyChord-style runs the mean likelihood.[2](https://arxiv.org/pdf/2205.15570)\n\nPosterior samples come at no extra cost: the dead points, assigned importance weights \\( \\omega_i \\cdot L_i \\) with \\( \\omega_i = x_{i-1} - x_i \\) and normalized so they sum to one, represent the posterior.[6](https://ar5iv.labs.arxiv.org/html/0801.3887)\n\n## Origin\n\nNested sampling was introduced by John Skilling in \"Nested sampling for general Bayesian computation\", Bayesian Analysis, 2006.[1](https://doi.org/10.1214/06-ba127) • [7](http://www.inference.org.uk/bayesys/box/nested.pdf) Chopin and Robert established that the approximation error vanishes at the standard [Monte Carlo](https://www.edgepedia.org/monte-carlo) rate \\( O(N^{-1/2}) \\) with asymptotically Gaussian error.[3](https://ar5iv.labs.arxiv.org/html/2101.09675)\n\nNested sampling has been well received in astronomy,[6](https://ar5iv.labs.arxiv.org/html/0801.3887) but the first application is disputed. Nested sampling was used in a cosmological application for dark energy model discrimination.[8](https://ar5iv.labs.arxiv.org/html/1308.2675) The Mukherjee, Parkinson, and Liddle paper itself, published in The Astrophysical Journal in 2006, applied nested sampling to cosmological model selection and found a five-parameter Harrison–Zel'dovich model preferred.[4](https://doi.org/10.1086/501068)\n\n## Variants\n\nImplementations separate primarily by how they solve the LRPS problem.\n\n**Rejection samplers** build an explicit region around the live points and sample it. Ellipsoidal sampling of restricted prior regions was introduced in the COSMONEST work of Mukherjee, Parkinson, and Liddle (2006): find the live-point covariance, rotate to principal axes, and draw from an enlarged ellipsoid (enlargement factor 1.5–1.8) subject to the likelihood constraint.[4](https://doi.org/10.1086/501068) Clustered nested sampling, introduced by Shaw, Bridges, and Hobson (2007), forms multiple ellipsoids on identified peaks via recursive [K-means clustering](https://www.edgepedia.org/k-means-clustering) with \\( K = 2 \\).[9](https://export.arxiv.org/pdf/0701867v2.pdf) The MultiNest package uses ellipsoidal rejection sampling, and its importance nested sampling summation can calculate the evidence at up to an order of magnitude higher accuracy than vanilla nested sampling.[10](https://arxiv.org/pdf/1306.2144)\n\n**Step samplers** walk a single point within the constraint. [Slice sampling](https://www.edgepedia.org/slice-sampling), introduced by Radford M. Neal in 2000, is the inner kernel of the PolyChord package, which is tailored for high-dimensional spaces and gains polynomial rather than exponential scaling with dimensionality.[11](https://ar5iv.labs.arxiv.org/html/1506.00171)\n\n**Dynamic and other variants.** Dynamic nested sampling, introduced by Higson, Handley, Hobson, and Lasenby (2018), varies the number of live points during the run to allocate samples where they most reduce uncertainty.[12](https://doi.org/10.1007/s11222-018-9844-0) The dynesty package, introduced by Joshua S. Speagle (2020), is an open-source Python implementation of dynamic nested sampling.[13](https://doi.org/10.1093/mnras/staa278) Diffusive nested sampling was introduced by Brewer, Pártay, and Csányi (2010),[14](https://doi.org/10.1007/s11222-010-9198-8) and superposition enhanced nested sampling by Martiniani, Stevenson, Wales, and Frenkel (2014).[15](https://doi.org/10.17863/cam.15578)\n\n**GPU samplers.** Nested Slice Sampling (NSS), introduced by Yallup, Kroupa, and Handley (2026), is a vectorized formulation using Hit-and-Run Slice Sampling, released in the blackjax library within the JAX ecosystem.[16](https://doi.org/10.48550/arxiv.2601.23252) NS-SwiG, introduced by Yallup (2026), reduces per-replacement cost for hierarchical models from \\( O(J^2) \\) to \\( O(J) \\) via budget constraint decomposition.[17](https://doi.org/10.48550/arxiv.2602.17414) BEST, introduced by Nygaard (2026), combines clustering and slice sampling with batched live-point updates in [TensorFlow](https://www.edgepedia.org/tensorflow), keeping batch size below roughly 10% of the live-point count to control bias.[18](https://doi.org/10.48550/arxiv.2608.28514)\n\n## Applications\n\nNested sampling is popular in cosmology, astrophysics, and particle physics, returning weighted posterior samples and an evidence estimate for model comparison.[19](https://arxiv.org/pdf/2010.13884) MultiNest has been applied to X-ray astronomy, exoplanets, and cosmology including Planck Collaboration analyses.[20](https://arxiv.org/html/2404.16928v2) For Potts model normalizing constants, nested sampling strongly outperforms annealed importance sampling.[6](https://ar5iv.labs.arxiv.org/html/0801.3887) In gravitational-wave astronomy, blackjax NSS achieves a 207-second runtime, a two-orders-of-magnitude speedup over CPU-based bilby, by deleting 1500 live points per iteration, parallelism largely impossible on CPUs.[21](https://arxiv.org/pdf/2509.24949) In cosmology, GPU-accelerated NSS with neural emulators turned a 37/39-dimensional cosmic shear analysis previously reported as taking about 8 months into a task for a single A100 GPU.[22](https://arxiv.org/html/2509.13307v2)\n\n## Limitations and alternatives\n\n**Error.** Statistical uncertainties on \\( \\ln Z \\) scale as \\( 1/\\sqrt{n_{\\mathrm{live}}} \\),[2](https://arxiv.org/pdf/2205.15570) consistent with Skilling's estimate \\( \\sqrt{H/M} \\) from Poisson fluctuations in the number of steps.[23](https://ar5iv.labs.arxiv.org/html/1102.0996) Four bias sources exist: failure to sample the constrained prior, the compression-factor estimator, quadrature error, and truncation error from stopping.[2](https://arxiv.org/pdf/2205.15570)\n\n**Failure modes.** Likelihood plateaus, regions of constant likelihood, cause ordinary nested sampling to underestimate volume contraction and overestimate the evidence; a modification that removes all tied live points without replacement before replenishing addresses this and can be applied retrospectively to PolyChord and MultiNest runs.[19](https://arxiv.org/pdf/2010.13884) In multimodal posteriors, only modes with prior-volume footprint greater than about \\( X/n_{\\mathrm{live}} \\) may be reliably found.[2](https://arxiv.org/pdf/2205.15570) Region samplers become exponentially inefficient above a problem-dependent dimensionality of order 10, while step samplers scale linearly with dimension.[24](https://arxiv.org/html/2409.18464) Sampling from the likelihood-constrained prior can be harder than sampling from the posterior, and the method is impractical with vague priors and completely impractical with improper priors.[25](https://arxiv.org/html/2606.17916) The p_insert diagnostic of Fowlie, Handley, and Su (2020) tests whether new live-point rank indices are uniformly distributed; small values indicate a faulty run.[26](https://doi.org/10.1093/mnras/staa2345) The first analytical coverage bounds for a fully specified nested sampling algorithm show heuristic bounds on uncovered constrained-prior fraction decaying as \\( (3 \\cdot K \\cdot m)^{-3/2} \\), with vanishing evidence bias as \\( K \\to \\infty \\) under those approximations; a fully rigorous convergence proof remains an open problem.[27](https://arxiv.org/pdf/2606.22930.pdf) Cross-method agreement is also unsettled: GPU-NS versus HMC Bayes factors in the cosmological study differed by around \\( 4\\sigma \\), and a discrepancy of 2 in log evidence separates decisive from inconclusive evidence under Jeffreys (1961).[22](https://arxiv.org/html/2509.13307v2)\n\n**Alternatives.** Nested sampling is generally more expensive than well-tuned MCMC for posterior sampling, but MCMC cannot compute the evidence alone because it does not explore the full prior volume in finite time.[8](https://ar5iv.labs.arxiv.org/html/1308.2675) NS-SMC replaces quadrature with importance-sampling weights, avoids truncation error, and can be noticeably less biased than nested sampling at equal cost.[2](https://arxiv.org/pdf/2205.15570)\n\n## References\n\n1. [John Skilling (2006). Nested sampling for general Bayesian computation. Bayesian Analysis.](https://doi.org/10.1214/06-ba127)\n2. [Nested sampling for physical scientists (review, arXiv:2205.15570; Nature Reviews Methods Primer)](https://arxiv.org/pdf/2205.15570)\n3. [Nested Sampling Methods (Buchner, 2021)](https://ar5iv.labs.arxiv.org/html/2101.09675)\n4. [Pia Mukherjee, David Parkinson, Andrew R. Liddle (2006). A Nested Sampling Algorithm for Cosmological Model Selection. The Astrophysical Journal.](https://doi.org/10.1086/501068)\n5. [dynesty documentation, Nested Sampling overview](https://dynesty.readthedocs.io/en/v2.1.5/overview.html)\n6. [Properties of nested sampling (Chopin & Robert, Biometrika 2010; HAL deposit excerpts merged)](https://ar5iv.labs.arxiv.org/html/0801.3887)\n7. [Nested Sampling (MacKay's book chapter, figures by David MacKay)](http://www.inference.org.uk/bayesys/box/nested.pdf)\n8. [Comparison of sampling techniques for Bayesian parameter estimation (Allison & Dunkley 2013)](https://ar5iv.labs.arxiv.org/html/1308.2675)\n9. [Clustered nested sampling (Shaw, Bridges & Hobson, arXiv astro-ph/0701867)](https://export.arxiv.org/pdf/0701867v2.pdf)\n10. [Importance nested sampling and the MultiNest algorithm (Feroz et al., 2013)](https://arxiv.org/pdf/1306.2144)\n11. [PolyChord: next-generation nested sampling (Handley et al., 2015)](https://ar5iv.labs.arxiv.org/html/1506.00171)\n12. [Edward Higson and colleagues (2018). Dynamic nested sampling: an improved algorithm for parameter estimation and evidence calculation. Statistics and Computing.](https://doi.org/10.1007/s11222-018-9844-0)\n13. [Joshua S Speagle (2020). dynesty: a dynamic nested sampling package for estimating Bayesian posteriors and evidences. Monthly Notices of the Royal Astronomical Society.](https://doi.org/10.1093/mnras/staa278)\n14. [Brendon J. Brewer, Livia B. Pártay, Gábor Csányi (2010). Diffusive nested sampling. Statistics and Computing.](https://doi.org/10.1007/s11222-010-9198-8)\n15. [Martiniani, Stefano and colleagues (2014). Superposition Enhanced Nested Sampling. .](https://doi.org/10.17863/cam.15578)\n16. [Yallup, David, Kroupa, Namu, Handley, Will (2026). Nested Slice Sampling: Vectorized Nested Sampling for GPU-Accelerated Inference. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2601.23252)\n17. [Yallup, David (2026). Nested Sampling with Slice-within-Gibbs: Efficient Evidence Calculation for Hierarchical Bayesian Models. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2602.17414)\n18. [Nygaard, Andreas (2026). Fast and efficient nested sampling with BEST. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2608.28514)\n19. [Plateau problems in nested sampling (modified NS algorithm, arXiv:2010.13884)](https://arxiv.org/pdf/2010.13884)\n20. [Notes on the Practical Application of Nested Sampling: MultiNest, (non)convergence, and rectification (2024)](https://arxiv.org/html/2404.16928v2)\n21. [GPU-accelerated nested sampling for gravitational-wave parameter estimation (blackjax NSS)](https://arxiv.org/pdf/2509.24949)\n22. [High-Dimensional Bayesian Model Comparison in Cosmology with GPU-accelerated Nested Sampling and Neural Emulators](https://arxiv.org/html/2509.13307v2)\n23. [On statistical uncertainty in nested sampling (Keeton, 2011)](https://ar5iv.labs.arxiv.org/html/1102.0996)\n24. [A comparison of Bayesian sampling algorithms for high-dimensional particle physics and cosmology applications (2024)](https://arxiv.org/html/2409.18464)\n25. [Nested Sampling: A Critical and Comprehensive Theoretical Guide (2026)](https://arxiv.org/html/2606.17916)\n26. [Andrew Fowlie, Will Handley, Liangliang Su (2020). Nested sampling cross-checks using order statistics. Monthly Notices of the Royal Astronomical Society.](https://doi.org/10.1093/mnras/staa2345)\n27. [First analytical coverage bounds of a fully specified nested sampling algorithm (MLFriends)](https://arxiv.org/pdf/2606.22930.pdf)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Statistics and probability › Bayesian statistics › Bayesian computation and software*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/nested-sampling", "markdown_url": "https://www.edgepedia.org/nested-sampling.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Nested sampling\", Edgepedia (EdgeChat), https://www.edgepedia.org/nested-sampling. Edgepedia Community License 1.0.", "credit_md": "\"[Nested sampling](https://www.edgepedia.org/nested-sampling)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/nested-sampling](https://www.edgepedia.org/nested-sampling). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Nested sampling\", Edgepedia (EdgeChat), https://www.edgepedia.org/nested-sampling. Edgepedia Community License 1.0.", "speakable": "Nested sampling is a Monte Carlo algorithm in Bayesian statistics, introduced by John Skilling in 2006, that computes a model's evidence with posterior samples as a by-product." }