返回题库

集齐 p 种优惠券：期望盒数

Cereal coupon

专题
Probability / 概率
难度
L4

题目详情

Each box of cereal contains a coupon. If there are pp kinds of coupons, how many boxes of cereal have to be bought on average to obtain at least one coupon of each kind?

解析

设已集齐 k−1k-1 种时，再得到一个新种类的概率为 p−(k−1)p\frac{p-(k-1)}{p}，因此等待的新盒数期望为

E[Nk]=1(p−k+1)/p=pp−k+1.\mathbb{E}[N_k]=\frac{1}{(p-k+1)/p}=\frac{p}{p-k+1}.

总期望

E[N]=∑k=1ppp−k+1=p∑j=1p1j=pHp.\mathbb{E}[N]=\sum_{k=1}^{p}\frac{p}{p-k+1}=p\sum_{j=1}^{p}\frac{1}{j}=\boxed{pH_p}.

大 pp 时近似 pln⁡p+γp+12p\ln p+\gamma p+\tfrac12。