返回题库

集齐 N 种兑奖券

Collecting Lucky coupons

专题
Probability / 概率
难度
L6

题目详情

饮料公司推出活动：集齐 NN 种不同的兑奖券即可领奖。每买一瓶饮料随机获得一张券，且每种券等概率出现。

问：为了集齐所有 NN 种券，期望需要买多少瓶？

提示：分阶段 + 期望线性性。

A soda company is holding a contest where everyone who collects one each of N different coupons wins some prize. You get a coupon with each purchase of a soda, and each coupon is equally likely. What’s the expected number of soda bottles you have to buy in order to collect all the coupons?

Hint

Linearity of expectation

解析

答案是

N⋅HN=N(1+12+⋯+1N).N\cdot H_N = N\left(1+\frac12+\cdots+\frac1N\right).

当已收集到 kk 种时，新券出现概率为 N−kN\frac{N-k}{N}，再获得一张新券的期望等待次数为 NN−k\frac{N}{N-k}。

把 k=0→N−1k=0\to N-1 的期望相加即可得到 NHNN H_N。

Original Explanation

Solution

Divide the whole process in to stages. Each stage ends with collecting a coupon which is new ( different from the coupons we already have )

Let C_i be the random variable which denotes the number of coupons we buy in the stage i.

Let C be the random variable which denotes the number of coupons we buy in order to get all n coupons Now, C= C_1 + C_2 + ... + C_n Note C_1 = 1; In general, while we are during stage i , we already have with us (i-1) different coupons. So, the probability of getting a new coupon is p_i = n-(i-1)/n. Also note that each C_i is a Geometrically distributed random variable with success probability equal to p_i. So, E(C_i) = 1/p_i = n/(n-i+1). By using Linearity of Expectations, E(C) = E(C_1) +E(C_2) + ...+E(C_n) = n(1/n + 1/(n-1)+ ... +1) ~ nlogn.