我正在尝试回答以下问题：“我需要多少（二进制）数据才能让我的学习者至少看到数据集的每个变量一次？” 在我的设置中，我提供了我的算法二进制向量（即所有元素都等于 1 或 0），这些向量具有已知的“密度”（平均数量）——为了回答这个问题——是均匀恒定（好的）或遵循长尾分布（更好）。我曾尝试从组合学的角度来看待它，但这比预期的要难。我想这个问题之前一定有人问过，但到目前为止我还没有找到任何参考资料。

在Valiant的“可学习的理论”中，我读到：

令 L(h,S) 为最小整数，使得$L(h,S)$ 独立的伯努利试验，每个试验至少有概率$h^{-1}$成功的概率小于$S$成功率小于$h^{-1}$. [...] 命题：对于所有整数$S > 1$而且都是真实的$h > 1$.

$$L(h,S) \leq 2 h (S + \ln (h))$$

这可以转化为我的问题的上限，因为假设每个特征都来自独立的伯努利试验，而不是下限。有谁知道其他相关工作可以将我指向下限？