“Estimating the Number of Unseen Species: A Bird in the Hand Is worth Log n in the Bush”, Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu2015-11-23 (mark-and-recapture)⁠:

Estimating the number of unseen species is an important problem in many scientific endeavors. Its most popular formulation, introduced by R. A. Fisher, uses n samples to predict the number U of hitherto unseen species that would be observed if t ⋅ n new samples were collected. Of considerable interest is the largest ratio t between the number of new and existing samples for which U can be accurately predicted.

In seminal works, Good & Toulmin1956 constructed an intriguing estimator that predicts U for all t ≤ 1, thereby showing that the number of species can be estimated for a population twice as large as that observed. Subsequently Efron and Thisted obtained a modified estimator that empirically predicts U even for some t > 1, but without provable guarantees.

We derive a class of estimators that provably predict U not just for constant t > 1, but all the way up to t proportional to log n. This shows that the number of species can be estimated for a population log n times larger than that observed, a factor that grows arbitrarily large as n increases.

We also show that this range is the best possible and that the estimators’ mean-square error is optimal up to constants for any t. Our approach yields the first provable guarantee for the Efron-Thisted estimator and, in addition, a variant which achieves stronger theoretical and experimental performance than existing methodologies on a variety of synthetic and real datasets.

The estimators we derive are simple linear estimators that are computable in time proportional to n. The performance guarantees hold uniformly for all distributions, and apply to all 4 standard sampling models commonly used across various scientific disciplines: multinomial, Poisson, hypergeometric, and Bernoulli product.