Optimal prediction of the number of unseen species

Abstract

<p id="d6535592e163">Many scientific applications ranging from ecology to genetics use a small sample to estimate the number of distinct elements, known as ”species,” in a population. Classical results have shown that <i>n</i> samples can be used to estimate the number of species that would be observed if the sample size were doubled to <span class="inline-formula"> <math id="i1" overflow="scroll"> <mrow> <mn>2</mn> <mi>n</mi> </mrow> </math> </span>. We obtain a class of simple algorithms that extend the estimate all the way to <span class="inline-formula"> <math id="i2" overflow="scroll"> <mrow> <mi>n</mi> <mo> </mo> <mi mathvariant="bold">log</mi> <mo> </mo> <mi>n</mi> </mrow> </math> </span> samples, and we show that this is also the largest possible estimation range. Therefore, statistically speaking, the proverbial bird in the hand is worth log <i>n</i> in the bush. The proposed estimators outperform existing ones on several synthetic and real datasets collected in various disciplines. </p><p class="first" id="d6535592e198">Estimating the number of unseen species is an important problem in many scientific endeavors. Its most popular formulation, introduced by Fisher et al. [Fisher RA, Corbet AS, Williams CB (1943) <i>J Animal Ecol</i> 12(1):42−58], uses <i>n</i> samples to predict the number <i>U</i> of hitherto unseen species that would be observed if <span class="inline-formula"> <math id="i4" overflow="scroll"> <mrow> <mi>t</mi> <mo>⋅</mo> <mi>n</mi> </mrow> </math> </span> new samples were collected. Of considerable interest is the largest ratio <i>t</i> between the number of new and existing samples for which <i>U</i> can be accurately predicted. In seminal works, Good and Toulmin [Good I, Toulmin G (1956) <i>Biometrika</i> 43(102):45−63] constructed an intriguing estimator that predicts <i>U</i> for all <span class="inline-formula"> <math id="i5" overflow="scroll"> <mrow> <mi>t</mi> <mo>≤</mo> <mn>1</mn> </mrow> </math> </span>. Subsequently, Efron and Thisted [Efron B, Thisted R (1976) <i>Biometrika</i> 63(3):435−447] proposed a modification that empirically predicts <i>U</i> even for some <span class="inline-formula"> <math id="i6" overflow="scroll"> <mrow> <mi>t</mi> <mo>&gt;</mo> <mn>1</mn> </mrow> </math> </span>, but without provable guarantees. We derive a class of estimators that provably predict <i>U</i> all of the way up to <span class="inline-formula"> <math id="i7" overflow="scroll"> <mrow> <mi>t</mi> <mo>∝</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> </mrow> </math> </span>. We also show that this range is the best possible and that the estimator’s mean-square error is near optimal for any <i>t</i>. Our approach yields a provable guarantee for the Efron−Thisted estimator and, in addition, a variant with stronger theoretical and experimental performance than existing methodologies on a variety of synthetic and real datasets. The estimators are simple, linear, computationally efficient, and scalable to massive datasets. Their 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. </p>