这是第二类斯特林数吧
by 云浅知处 @ 2024-04-28 17:20:13
@[hxhhxh](/user/429147) @[云浅知处](/user/307453) 这个问题是概率论中的经典问题，叫做赠券收集问题（coupon collector’s problem）。
设 $X$ 为第一次达到所有的数都被生成过的时刻。原帖中的 $P(n)$ 即为 $\Pr(X \le n)$。
有结论：当 $m$ 趋于无穷时，$X$ **依分布收敛**（converge in distribution）于参数为 $(\mu, \beta) = (m \ln m, m)$ 的 Gumbel 分布。
请看图：
此结果应当令人满意。
我们有（当 $m$ 趋于无穷时）$X$ 的
- 众数为 $m \ln m$
- 期望为 $m \ln m + \gamma m$（$\gamma \approx 0.5772$）
- 中位数为 $m \ln m + (-\ln \ln 2) m$（$-\ln \ln 2 \approx 0.3665$）
对于原帖中的问题，由 CDF 为 $\mathrm{e}^{-m \mathrm{e}^{-x / m}}$，解得 $\Pr(X \le n) = p$ 的解为 $n = m (\ln m - \ln(-\ln p))$。如果取 $p = 1/\mathrm{e}$ 则有 $\Pr(X \le m \ln m) = 1/\mathrm{e}$。
（无论是否有帮助，希望您给予反馈并 at 我）
by 小粉兔 @ 2024-04-29 06:57:37
MMA 中的 `F(n, i)` 为当 $m = n$ 时 $X = i$ 的概率的精确结果。
by 小粉兔 @ 2024-04-29 06:58:29
（我本来想根据 $X = \sum_{i=1}^{m} \mathsf{G}(i/m)$，自己用带 Lindeberg 条件的中心极限定理计算，结果发现这玩意不满足 Lindeberg 条件，大概是因为 $\mathsf{G}(1/m)$ 贡献了大部分的方差（大约 $61\%$ 的方差都来自于这一项），导致总方差没法盖住 $\mathsf{G}(1/m)$ 的长尾。而事实上这东西也确实不收敛于一个正态分布，而是这个奇奇怪怪的分布。）
by 小粉兔 @ 2024-04-29 07:04:20
上面的 Gumbel 分布我也不会证明，我给的资料是抄 Wikipedia 的。
对于我还能证明的部分，见下（但它们给不出精确的分布）。
根据 $X = \sum_{i=1}^{m} \mathsf{G}(i/m)$，其中 $\mathsf{G}(p)$ 表示参数为 $p$ 的几何分布（取 $k$ 的概率为 $(1-p)^{k-1}p$），可以得到
- $\operatorname{\mathbb E} X = m H_m$；
- $\operatorname{Var} X = m^2 H^{(2)}_m - m H_m = \frac{\pi^2}{6} \cdot m^2 \cdot (1 + o(1))$。
然后你可以用 Чебышёв 不等式来对它的长尾做一个最简单的估计，即 $\Pr(X > m \ln m + c m) \le \frac{\pi^2}{6} \cdot c^{-2}$。
对于稍紧的估计，考虑 $\Pr(X > m \ln m + c m) \le$ 存在某个数没被生成过的概率 $\le m \cdot {}$一个特定的数没被生成过的概率 $= m \cdot (1 - 1/m)^{m \ln m + c m} < m \cdot (1/\mathrm{e})^{\ln m + c} = \mathrm{e}^{-c}$。[${}^{\textsf{[参考资料]}}$](https://tcs.nju.edu.cn/wiki/index.php?title=%E9%AB%98%E7%BA%A7%E7%AE%97%E6%B3%95_(Fall_2022)/Balls_into_bins#:~:text=the%20probability%20that%20there%20exists%20an%20empty%20bin)
by 小粉兔 @ 2024-04-29 07:34:01
@[小粉兔](/user/10703) 谢谢，受教了
by hxhhxh @ 2024-04-29 08:44:08
@[hxhhxh](/user/429147) 一点不成体统的想法，仅供参考。
首先我们有
$$
\mathbb E(n) = \sum _ {k = 1} ^ m \frac {m} {k}
$$
以及
$$
\mathbb E(n ^ 2) = \left( \sum _ {k = 1} ^ m \frac {m} {k} \right) ^ 2 + \sum _ {k = 1} ^ m \left( \frac {m ^ 2} {k ^ 2} - \frac {m} {k} \right)
$$
这都是可以用常规的计数手段得到的。我使用的方法是直接列出期望 dp 展开计算。
然后有一个 Chebyshevÿ 不等式：
$$
\Pr \left( |x - \mathbb E(x)| \ge a \right) \le \frac {\operatorname{Var}(x)} {a ^ 2}
$$
这里的 $\operatorname{Var}(x)$ 是方差。这个不等式还挺好理解的，就是因为样本空间每一个 $|x - E(x)| \ge a$ 都对 $\operatorname{Var}(x)$ 产生至少 $a ^ 2$ 的贡献，虽然这个理解不太严谨。
然后有 $\operatorname{Var}(x) = \mathbb E(x ^ 2) - \mathbb E ^ 2(x)$，这个也挺经典的。那我们代入上式只需 $\frac{ \operatorname{Var}(n)} {a ^ 2} \le 1 - p$ ，这样 $n = a + \mathbb E(n)$ 即可。而 $\operatorname{Var}(n) = \mathbb E(n ^ 2) - \mathbb E ^ 2(n) = \sum _ {k = 1} ^ m \left( \frac {m ^ 2} {k ^ 2} - \frac {m} {k} \right) = O(m ^ 2)$，于是解得只需 $a$ 到 $O \left( \frac {m} {\sqrt {1 - p}} \right)$，从而最小的 $n$ 是 $O \left(m \left(\ln m + \frac {1} {\sqrt {1 - p}}\right) \right)$ 的。
这个做法比较简单，但是得到的结果相对粗糙，希望对您有所帮助。
by zhouyuhang @ 2024-05-01 23:04:01