标题： 使用级联排除估计集合的大小 显示英文标题

标题： Estimating the size of a set using cascading exclusion

摘要： 设$S$为一个有限集合，$X_1,\ldots,X_n$为从$S$中独立同分布的均匀样本。为了估计大小$|S|$，在没有进一步结构的情况下，可以等待重复并利用生日问题。这需要样本量约为$|S|^\frac{1}{2}$。另一方面，如果$S=\{1,2,\ldots,|S|\}$，通过将样本放大$n/(n-1)$得到的最大值给出了一个基于任何增长样本量的有效估计量。本文给出了在这些极端情况之间的改进方法。发展了一种一般的非渐近理论。这包括估计紧凸集的体积、未被观测到的物种问题，以及从问题“这个新观测是否是从一个大预定义总体中典型的选取？”中得出的一系列检验问题。我们还处理了回归风格的预测器。 一个普遍定理在所有情况下给出了非参数有限$n$误差界。 显示英文摘要

摘要： Let $S$ be a finite set, and $X_1,\ldots,X_n$ 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|^\frac{1}{2}$. 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.