The Unseen Species Problem Revisited

Given $n$ i.i.d. samples from an unknown discrete distribution over an unknown set, the unseen species problem is to predict how many new outcomes would be observed in $m$ additional samples. For small $m$ we show that the Good--Toulmin estimator is the unique estimator which both respects the symmetries of the problem and has non-trivial rate. We resolve the open problem of constructing principled prediction intervals for it. For intermediate $m$ we propose a new estimator which has vastly improved worst case MSE guarantees compared to competing methods and good empirical performance. For large $m$ we follow previous authors in assuming a power law tail and show that a simple estimator achieves the same rate as, and better empirical performance than, a recent sophisticated method. Moreover, we give pre-asymptotic guarantees and asymptotically calibrated prediction intervals. Many of our results extend to incidence data, without further independence assumptions, provided that the sets are of bounded size. Using Stein's method we obtain concentration inequalities for some natural functionals of sequences of i.i.d. discrete-set-valued random variables which are of independent interest.