我想从整数中采样$\{1, \dots, k\}$有概率$\{ p_i \}_{i=1}^k$，替换，直到我看到$m$不同的元素（称之为$n$次）。

您可以将我要从中采样的分布查看为多项分布，而不是固定样本数$n$， 让$n$是第一个给出确切的数字$m$-稀疏向量。（或者，给出的最大数$m$-稀疏向量也可以。）

使用别名方法，按照上面所写的字面意思实现采样需要$O(n + k)$时间。

所以，这是否有效运行取决于有多大$n$是。如果概率相对一致和/或$k \gg m$，这应该不会太糟糕。但在病理情况下$k = m + 1$和其中的两个$p_i$s 非常小，这需要很长时间。

这是优惠券收集器问题的一个版本，我发现了不统一的变体，但我没有找到你只需要得到的$m < k$优惠券的种类——无论如何，我不知道这种推理是否有助于更有效的抽样算法。

所以：

• 你能找到，或绑定，分布$n$? 特别是在$\max p_i / \min p_i$或类似的？
• 是否有更有效的算法来执行此采样？