返回题库

优惠券收集问题

The Coupon Collector Problem

专题
Probability / 概率
难度
L6

题目详情

某麦片公司促销：每盒麦片里有 1 张优惠券，共有 nn 种不同类型，每盒里出现哪种优惠券等概率且独立。

问：平均需要买多少盒，才能集齐全部 nn 种优惠券？

A cereal company is running a promotion where each box of cereal contains a coupon. There are nn different types of coupons, and each box contains one randomly chosen coupon with equal probability. What is the expected number of boxes you need to buy in order to collect all nn types of coupons?

解析

把“集齐过程”分解为从 k−1k-1 种到 kk 种所需的等待时间。

当已集齐 k−1k-1 种时，下一盒出现“新类型”的概率为 n−(k−1)n=n−k+1n\frac{n-(k-1)}{n}=\frac{n-k+1}{n}，因此期望等待盒数为其倒数 nn−k+1\frac{n}{n-k+1}。

总期望为

∑k=1nnn−k+1=n∑j=1n1j=nHn.\sum_{k=1}^{n}\frac{n}{n-k+1}=n\sum_{j=1}^{n}\frac{1}{j}=nH_n.