掷一枚均匀的骰子,直到六个面都出现过;投掷次数的期望是 14.7(第一与第二个链接,同一份和分别合着写与逐项写)。道理只有一行:还差 k 个面时,每次投掷有 k/6 的概率是新的,所以等下一个新面是一场期望为 6/k 的几何试验,总期望就是 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6。第三个链接把题目改成五种券,得 11.416666666667。第四个 6⁶ = 46656 是六次投掷的全部可能序列数——对这个问题是用错了工具,但对另一个相关的问题刚好用作分母:头六次就凑齐六个面的概率是 6!/46 656,勉强超过 1.5%。
答案的形状比那个数更要紧:n·H_n 大致按 n ln n 增长,所以价钱几乎全在最后那几张券上。一百种东西要花 100·H₁₀₀ = 518.7 次尝试,其中光是最后一张就占去一百次;第一张只需一次。正是这份不对称让免费领 token 的活动感觉在末尾卡住,让一套收藏卡里最后一个号码最贵,也让那些需要看遍每个取值的随机化算法付同一份调和价钱。散度也朝同一个方向去——归一化后的等待时间分布趋近 Gumbel 律,而它右边拖著一条长尾,所以运气差的收集者会差得又大又可预测。
答案
14.7
口径说明
六乘第六个调和数。第二个链接是同一个和逐项加,第三个把六张券换成五张,第四个是六次投掷的全部序列数。
出处
the coupon collector's problem in Feller, 'An Introduction to Probability Theory and Its Applications', volume 1 (1950), where it is posed as the baseball-card question; the expectation n·H_n and the Gumbel limit of the rescaled waiting time are standard
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。