[数学]关于Coupon Collector的问题

原题在这里.简单的说,市面上有一种coupon有n个样式.每一个你新收集的coupon以1/n的概率为其中任意一种.如果说你需要收集T个coupon你才能把所有的样式都拿到,那么T的均值是多少呢?

假设我们手里已经有了i-1种不同的coupon.那么在收集了i-1种不同coupon后,出现一个新式的coupon所需要的尝试次数服从参数为pi的几何分布.pi=(n-i+1)/n　也就是出现第i种新coupon的概率.

E[T]=1/p_1+1/p_2+\cdots+1/p_n =  \frac{n}{n}+\frac{n}{n-1}+\cdots+\frac{n}{n} = n H_n\approx n \ln n

该问题的一个变种是:求当我们收集齐了所有n种coupon,其中某个样式(比如印着机器猫的)coupon只拿到了一张的概率.

该珍贵的coupon,可以是第1种收集到的,也可以是第j种收集到的.j服从1,...,n,的均匀分布.如果它是第j种收集到的coupon,则后面不出现该coupon的概率是 1/(n-j+1). 所以全概率是:

\sum_{j=1}^n \frac{1}{n}\frac{1}{n-j+1}= \frac{H_n}{n}\approx \frac{\ln n}{n}