# Estimating the size of a set using cascading exclusion

arXiv: https://arxiv.org/abs/2508.05901 · HTML: https://mlsanity.com/paper/2508.05901/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 59 references that are in the map.
- First posted on arXiv 7 Aug 2025.

## Builds on (most cited first, 3 of 3)

- [Theoretical Foundations of Conformal Prediction](https://mlsanity.com/paper/2411.11824/) (2024)
- [Rediscovery of Good-Turing estimators via Bayesian nonparametrics](https://mlsanity.com/paper/1401.0303/) (2014)
- [Application and issues in abstract convexity](https://mlsanity.com/paper/2202.09959/) (2022)

## Abstract (arXiv)

Let S be a finite set, and X1,ldots,Xn an i.i.d. uniform sample from S. To estimate the size |S|, without further structure, one can wait for repeats and use the birthday problem. This requires a sample size of the order |S|^frac12. On the other hand, if S=1,2,ldots,|S|, the maximum of the sample blown up by n/(n-1) gives an efficient estimator based on any growing sample size. This paper gives refinements that interpolate between these extremes. A general non-asymptotic theory is developed. This includes estimating the volume of a compact convex set, the unseen species problem, and a host of testing problems that follow from the question `Is this new observation a typical pick from a large prespecified population?' We also treat regression style predictors. A general theorem gives non-parametric finite n error bounds in all cases.