集卡问题：骰子掷几次六面全出
题
一颗公平骰子反复掷，直到 1 到 6 每个点数都至少出现过一次。平均要掷几次？一般地，\(n\) 种卡片等概率随机抽，集齐一套的期望抽数是多少？
一句话
\(E[T] = n H_n = n\left(1 + \frac12 + \cdots + \frac1n\right)\)，骰子是 \(6 H_6 = 14.7\) 次——难的从来不是前几种，而是最后一种：光等最后一面就要平均 6 次。
关键技巧
按"已集到几种"切段。 手里已有 \(j\) 种时，下一抽是新卡的概率是 \(\frac{n-j}{n}\)，所以这一段的长度 \(G_j\) 服从几何分布，期望 \(\frac{n}{n-j}\)。总时间是 \(n\) 段之和：
\[ T = G_0 + G_1 + \cdots + G_{n-1} \]
期望线性性直接相加，不用管各段的依赖：
\[ E[T] = \sum_{j=0}^{n-1} \frac{n}{n-j} = n \sum_{k=1}^{n} \frac1k = n H_n \]
各段其实还相互独立（无记忆性），所以方差也能直接加：
\[ \mathrm{Var}(T) = \sum_{j=0}^{n-1} \frac{1 - p_j}{p_j^2} = n^2 \sum_{k=1}^n \frac{1}{k^2} - n H_n, \qquad p_j = \frac{n-j}{n} \]
解
\[ E[T] = 6 \left(1 + \tfrac12 + \tfrac13 + \tfrac14 + \tfrac15 + \tfrac16\right) = 6 \cdot \frac{49}{20} = \frac{147}{10} = 14.7 \]
六段依次是 \(1, 1.2, 1.5, 2, 3, 6\)——最后两段占了 9 次，占总数六成。
分布很宽：\(\mathrm{Var}(T) = 38.99\)，标准差约 6.24。中位数是 13（\(P(T \le 12) = 0.438\)，\(P(T \le 13) = 0.514\)），均值被右尾拉到 14.7；20 次内集齐的概率 0.848，30 次内 0.975。6 次就恰好集齐的概率是 \(6!/6^6 = 5/324 \approx 1.5\%\)。
延伸
- \(n \ln n\) 量级：\(nH_n = n\ln n + \gamma n + \tfrac12 + O(1/n)\)。\(n = 100\) 时是 518.7，\(n=1000\) 时 7485.5——比"每种抽一次"多出 \(\ln n\) 倍。
- 集中与 Gumbel 尾：\(T / (n \ln n) \to 1\)，涨落量级是 \(n\) 而不是 \(n \ln n\)。更精确地 \(P(T \le n\ln n + cn) \to e^{-e^{-c}}\)，\(c=0\) 时约 \(0.368\)（\(n=1000\) 精确值 0.367）。和 最长连正 一样，极值问题的极限又是 Gumbel。
- 集齐两套：骰子每面都出现至少两次，期望 \(\frac{390968681}{16200000} \approx 24.13\) 次，远少于 \(2 \times 14.7 = 29.4\)——集第一套时顺手攒下的重复卡已经填了第二套的大半。状态取"一次没出的面数、恰出一次的面数"做两维递推即可。
- 常见错误：把"期望 14.7 次"说成"掷 15 次大概率集齐"——实际 15 次内集齐的概率只有约 64%。期望在右偏分布里偏高于中位数。
- 同构问题：随机哈希填满所有桶、随机测试覆盖所有分支、随机排列的圈数 的 \(H_n\)，都是同一个调和级数在不同地方露头。
数值验证
精确期望、方差、分布、两套的二维递推，加蒙特卡洛：
from fractions import Fraction as F
from functools import lru_cache
import math, random
H = lambda n, s=1: sum(F(1, k ** s) for k in range(1, n + 1))
n = 6
E, V = n * H(n), n * n * H(n, 2) - n * H(n)
print(E, float(V), math.sqrt(V)) # 147/10 38.99 6.244197306299665
def cdf(n, K):
"""P(T <= k)，状态 = 已见过的面数。"""
st = [F(0)] * (n + 1); st[0] = F(1); out = []
for _ in range(K):
new = [F(0)] * (n + 1)
for j, v in enumerate(st):
new[j] += v * F(j, n)
if j < n: new[j + 1] += v * F(n - j, n)
st = new; out.append(st[n])
return out
c = cdf(6, 30)
print(c[5], [round(float(c[k - 1]), 3) for k in (12, 13, 20, 30)])
# 5/324 [0.438, 0.514, 0.848, 0.975]
@lru_cache(None)
def two_sets(a, b):
"""集齐两套：a = 一次没出的面数，b = 恰出一次的面数。"""
if a == b == 0: return F(0)
r = F(1)
if a: r += F(a, n) * two_sets(a - 1, b + 1)
if b: r += F(b, n) * two_sets(a, b - 1)
return r / F(a + b, n)
print(two_sets(6, 0), float(two_sets(6, 0))) # 390968681/16200000 24.133869197530863
for m in (10, 100, 1000):
print(m, round(float(m * H(m)), 3), round(m * math.log(m) + 0.5772156649 * m + 0.5, 3))
# 10 29.29 29.298 / 100 518.738 518.739 / 1000 7485.471 7485.471
random.seed(3)
T, t1, t2 = 200000, 0, 0
for _ in range(T):
cnt, k, one = [0] * 6, 0, None
while min(cnt) < 2:
cnt[random.randrange(6)] += 1; k += 1
if one is None and min(cnt) >= 1: one = k
t1 += one; t2 += k
print(t1 / T, t2 / T) # 14.69647 24.126675