要抽多少次才能集齐卡片

相信许多人小时候都有过收集某系列东西的经历，譬如我小的时候就曾参与过轰动一时的水浒108将的卡片收集。在一包包的方便面包装袋中，一张薄薄的卡片有时比那香脆的面饼更具吸引力。 我小时候学校门口的小卖部还会有其他的卡片收集活动， 比如数码宝贝，神奇宝贝等。 为了激励学生们购买卡包，商家还会出台奖励政策，比如集满十张赠送一个笔记本；集满50张奖励人民币XX元。 只可惜我运气不够好或者说囊中羞涩，水浒卡抽到的往往都是地煞星，收集兑奖也几乎从来没有集够达到兑奖资格的张数。 只能每每对身边小伙伴们手中满当的卡片集徒生羡慕。

那么为什么我会忽然想起这不堪回首的往事呢？ 事情缘于最近我在帮同学解决邮路算法问题时遇到的一个与收集卡片有异曲同工的问题。 问题如下：

假定邮递员每次送完快递，随机选择下一个目的地进行送递，如果所有目的地都可以反复到达多次。那么邮递员大概要走多少个地方，才能把总计 $m$ 个包裹（每个包裹对应一个不同的目的地）全部送达？

这就非常地像我们小时候收集卡片的情况，假定每张卡片出现的概率是相等的，那么问题便是我们大概需要买多少包卡才能收集齐呢？

开始思考这个问题时以为要解决这个问题思路应该非常简单，不就是计算期望嘛。 我们只需要找出每张卡片都至少出现一次时，购买的卡包数量 $x$ 所服从的概率分布。 但令人遗憾的是，这并不是一个常见的简单分布，我们难以直接根据分布来计算期望，直接通过分布计算期望的方法显然道阻且艰。

不过好在上帝在关上门的时候必然会忘记把窗户也顺带关上。

我们再次审视这个问题，虽然我们不知道所需购买卡包的数量服从什么分布，但是我们可以知道每一张卡片被抽中的次数是服从一个特定分布——几何分布。

在伯努利试验序列中，记每次试验中事件 $A$ 发生的概率为 $P$ ，如果 $X$ 为事件 $A$ 首次出现时的试验次数，则$X$的可能取值为 $1,2,\cdots$ ，称 $X$ 服从几何分布，记为 $X\sim Ge(P)$ ，其分布列为 $P(X=k)=(1-P)^{k-1}P,k=1,2,\cdots$ 。

那么怎么计算问题最后的结果呢？

我们将事件——每张卡片至少被抽中一次所需的卡包数——分开来看。 首先来看一看每次我们所抽中的卡片必定是与之前均不同的情况。

显然，我们第一次抽，所抽上来的卡片必定是与之前不同的，所以是一个必然事件 $P(A_{1})=1$ 。 第二次我们再抽，这时抽到与已抽过卡片不同卡片的概率就会下降为 $P_{2}=P(A_{2})=1-\frac{1}{m}$ （ $m$ 是卡片的种类数）。 那么这是一个伯努利试验，其所需包数 $x$ 服从几何分布 $X\sim Ge(P_{2})$ 。 所以抽到第二张卡所需的包数为:

而抽到第三张卡所需的包数

以此类推，抽到第 $m$ 张卡所需购买的包数期望为：

虽然 $\sum_{n=1}^{\infty}\frac{1}{n}$ 是一个发散级数，但是有限和我们还是可以进行计算的。

然而这里计算的只是我们在理想情况下的期望值。 正如我们平常玩游戏抽卡一样，为了让人们花更多的钱到游戏里去，设计者往往会对不同卡片设置不同的概率，而某些过低的概率必然会导致所需次数的快速上升。

恰如拉普拉斯曾在他的《关于概率的哲学随笔》中提到的 “赌博的维持，只是靠虚假的推理及其激发的贪念，引导人们牺牲他们的生活必须，去追求他们的荒唐的幻想。”