赠券收集者问题 - 卖程序的小歪 - 博客园

赠券收集者问题 - 卖程序的小歪 - 博客园

赠券收集者问题

赠券收集者问题（coupon collector's problem），就是买东西的时候会又不同的卡片赠送，求集齐这些卡片需要购买的产品的数量的期望值。
见wiki [coupon collector's problem https://en.wikipedia.org/wiki/Coupon_collector%27s_problem]

以一个例子来说明：有种食品每袋都会附赠一张卡片，共有10种卡片，每种卡片出现的概率相等。

首先来求当拥有i种卡片时，再拆开一袋得到不同卡片的概率Pi：

a. 当我们没有任何卡片时，随意拆开就能得到一种不同的卡片，即第一种得到的卡片P0 = 1

b. 当有了一种继续拆，此时得到新的种类的概率为P1 = 9 / 10
...当有了i种，此时得到新种类的概率为Pi = (10 - i) / 10

我们知道了Pi的值，那么对于拆了i包后，拆开发现新卡片的次数期望为E = Pi * Ni，由于只需要然其发生一次即可令E=1反过来求对应的Ni，Ni = 1 / Pi，即拆1 / Pi包时可以发现一种新卡片（相对于已经拥有i种卡片）。

那么发现全部卡片总共需要的包数 = N0 + N1 + N2 ... N9 = 10 / 10 + 10 / 9 + 10 / 8 ... 10 / 1 = 29.289682539682538

即按期望来，买30包可以集齐卡片。

下面给出了卡片等概率出现时，集齐卡片的期望次数：

Read full article from 赠券收集者问题 - 卖程序的小歪 - 博客园