Nested sampling algorithm

The nested sampling algorithm is a computational approach to two problems in Bayesian statistics: comparing competing models and generating samples from posterior distributions. It was developed in 2004 by the physicist John Skilling. Model comparison needs the marginal likelihood of each model, an integral over all of a model's parameters that is usually analytically intractable, so a numerical method is required. Nested sampling approximates that integral by repeatedly discarding the live point of lowest likelihood and replacing it with a new point drawn from the prior restricted to higher likelihood, which in effect turns the integral into a one-dimensional sum over nested shells of prior mass. As a by-product it yields posterior samples, and it offers an alternative to bridge sampling and defensive importance sampling. Skilling's pseudocode leaves open how the replacement point is drawn, so later work supplied several choices, including Markov chain Monte Carlo variants such as slice sampling and constrained Hamiltonian Monte Carlo, and rejection sampling within ellipsoids as in the MultiNest software. Dynamic nested sampling generalises the method by adjusting the number of samples across the parameter space. Applications include astronomy, structural model selection and the study of materials.