Published on Mon Nov 23 2015

### Estimating the number of unseen species: A bird in the hand is worth $\log n$ in the bush

, ,

Estimating the number of unseen species is an important problem in many scientific endeavors. We derive a class of estimators that predict not just for constant , but all the way up to proportional to $n. 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.

0
0
0
###### Abstract

Estimating the number of unseen species is an important problem in many scientific endeavors. Its most popular formulation, introduced by Fisher, uses samples to predict the number of hitherto unseen species that would be observed if new samples were collected. Of considerable interest is the largest ratio between the number of new and existing samples for which can be accurately predicted. In seminal works, Good and Toulmin constructed an intriguing estimator that predicts for all , 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 even for some , but without provable guarantees. We derive a class of estimators that predict not just for constant , but all the way up to proportional to . This shows that the number of species can be estimated for a population times larger than that observed, a factor that grows arbitrarily large as 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 . 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 . The performance guarantees hold uniformly for all distributions, and apply to all four standard sampling models commonly used across various scientific disciplines: multinomial, Poisson, hypergeometric, and Bernoulli product.