机器算法验证 - 关于接近 Gumbel 分布的优惠券收集器问题的直觉 - 吾爱随笔录

假设有种不同类型的优惠券，我们尝试收集所有类型的优惠券。 $n$

我们通过独立随机抽取优惠券来做到这一点，其中每种类型的优惠券都有相同的概率被抽取。 $1/n$

我们需要多少次抽奖收集所有优惠券？ $k$

变量的概率分布是多少？ $K$

的分布遵循分布其中是斯特林数第二种。 $K$
$P (K \leq k) = \frac{k! {\binom{n}{k}}}{k^{n}}$ $P(K \leq k) = \frac{k!{{n}\brace{k}}}{k^n}$ ${{n}\brace{k}}$
该分布也可以看作是独立几何分布变量之和的分布。
$K = \sum_{i = 1}^{n} X_{i} with X_{i} \sim G e o m (p = i / n)$ $K = \sum_{i=1}^{n} X_i \qquad \text{with $X_i \sim Geom(p = i/n)$}$

我们可以用 Gumbel 分布来近似上述结果。

我在 Wikipedia 页面的一部分中发现有几个人发现了限制分布，但没有给出任何资源。 $e^{-e^{-c}}$
在Guy Louchard的“重访第二类斯特林数的渐近”中，第 196 页指出 Erdõs 和 Szekeres 以。但是该资源指向 Sachkov 的书“组合分析中的概率方法”中的第 164 页，我无法找到原始来源（并且有很多要搜索的内容）。 $e^{-e^{-c}}$
Lars Holst的文章“随机优惠券收集器和生日问题的极值分布”正在接近我正在寻找的内容。但它仍然变得相当技术性。

所以，我对这个问题的尝试是证明优惠券收集者的问题接近 Gumbel 分布。潜在地，使其也直观，为什么它是一种极值分布，即极限分布。与极端值有关系吗？或者极端值和这些类型的组合问题是否出于某种原因在极限中具有相似的行为？

我试图操纵几何变量之和的特征函数，但被困在那里。也许我必须更努力地挖掘或尝试其他路线。