First analytical coverage bounds of a fully specified nested sampling algorithm

Technical Summary: First Analytical Coverage Bounds of a Fully Specified Nested Sampling Algorithm

Problem Statement
Nested sampling is a Monte Carlo algorithm designed for Bayesian model comparison and posterior estimation. Its core mechanism involves maintaining a population of $K$ "live points" sampled from a prior distribution. At each iteration, the point with the lowest likelihood is discarded and replaced by a new sample drawn from the prior, restricted to exceed the likelihood of the discarded point. The computational bottleneck of this algorithm is the efficient and reliable generation of these likelihood-restricted prior samples (LRPS). While convergence proofs exist for nested sampling assuming an idealized LRPS procedure, practical implementations rely on specific algorithms (such as MCMC or region-based methods) whose analytical properties regarding coverage and bias have remained largely uncharacterized. Specifically, there has been no rigorous analytical bound on the fraction of the likelihood-restricted prior space that a practical, fully specified algorithm might fail to cover.

Methodology
This work focuses on MLFriends, a region-based LRPS algorithm suitable for low-to-moderate dimensional problems. The authors provide a self-contained mathematical formulation of MLFriends and derive heuristic bounds on its performance under specific modeling assumptions:

1. Reparameterization: The prior space is transformed into a unit hypercube with a uniform distribution.
2. Point Process Model: The $K$ live points are modeled as a homogeneous Binomial point process distributed uniformly and independently within the likelihood-restricted prior volume ($\Omega_{r\pi}$).
3. Algorithm Mechanics: MLFriends constructs a proposal region ($\Omega_P$) by aggregating neighborhoods around live points. It employs a bootstrap aggregating (bagging) procedure over $m$ rounds. In each round, a training set of live points is sampled with replacement to define a "safe" radius ($r_{train}$) that covers the left-out validation points. The final proposal radius ($r_{max}$) is the maximum of these radii across $m$ independent rounds.
4. Analytical Approach: The authors derive the expected $d$-th power of the bootstrap radius and subsequently the probability that a point in the likelihood-restricted prior is not covered by the proposal region ($P_{missed}$). They utilize properties of the Beta distribution and Stirling numbers of the second kind to approximate the behavior of the bootstrap sets.

Key Contributions and Results
The paper presents the first analytical characterization of a fully specified, practically implementable nested sampling algorithm without relying on asymptotic or idealized sampling assumptions.

• Derivation of Coverage Bounds: Under the assumption that nearest-neighbor distances from a shared training set to validation points are independent (a heuristic assumption), the authors derive an upper bound on the expected fraction of the likelihood-restricted prior not covered by the proposal region.
  • The bound decays as $( \frac{1}{3}Km )^{-3/2}$.
  • For practical parameter choices (e.g., $K=1000, m=20$), this uncovered fraction is negligibly small (e.g., $\approx 2 \times 10^{-7}$).
• Bias Analysis: The authors analyze the impact of this uncovered region on the marginal likelihood estimate ($\hat{Z}$) and posterior samples.
  • Marginal Likelihood: They show that the fractional bias in $\hat{Z}$ is bounded by $N( \frac{1}{3}Km )^{-3/2}$, where $N$ is the number of iterations. This bias is shown to be negligible compared to the inherent statistical standard deviation of the estimator ($\sqrt{N/K}$) for moderate-to-large $K$ and $m$.
  • Posterior Samples: The omission of the uncovered region results in a loss of posterior mass proportional to the uncovered volume. Under the assumption that the likelihood in the missed region is not systematically higher than the average (Assumption 2), the bias in the posterior approximation is similarly negligible.
• Volume Increments: The analysis clarifies that missing part of the restricted prior does not inflate the estimated prior volume increments ($\Delta V_i$); rather, it leads to a downward bias in the evidence estimate because the likelihood-weighted mass in the missed region is never sampled.

Significance and Claims
The authors claim that these results provide the first analytical characterisation of a fully specified nested sampling algorithm that does not assume an idealized or asymptotic sampling procedure.

• The work bridges the gap between theoretical convergence proofs (which assume perfect LRPS) and practical implementations.
• The derived bounds offer "practically useful reliability estimates" for computer implementations with finite resources.
• The paper explicitly acknowledges the limitations of its approach: the results are labeled "heuristic" because they rely on the assumption of independence between nearest-neighbor distances and the independence of bootstrap rounds. A fully rigorous treatment with explicit error bounds as functions of dimensionality and geometry is identified as an open problem for future work.
• The analysis assumes the likelihood is free of plateaus and that the parameter space can be reparameterized to a uniform prior. It also notes that multi-modal cases are handled heuristically via cluster detection (described in the Appendix) but are not treated analytically in the main derivation.

In summary, the paper establishes that for practical parameter choices, the MLFriends algorithm covers the likelihood-restricted prior with such high probability that the resulting bias in nested sampling estimates is dominated by the algorithm's inherent statistical variance rather than the algorithmic approximation of the proposal region.