记得小学的时候特别喜欢吃一种叫做"小浣熊"的干脆面, 并不是说有多么好吃, 主要是为了收集其中附赠的卡片, 吃面倒成了其次. 当时流行的是水浒108将, 那些卡片外观精美, 正面是每一个水浒好汉的生动造型, 背面则是人物介绍, 我最喜欢的是那些关于武器、必杀技、攻击力之类的, 总之很迷恋, 对于那些名词很是敏感. 那时候每一个买这种干脆面的小孩子的最大愿望肯定都是把108张卡片全部集齐, 我几乎是每天一包的买, 下课就会冲向小卖部, 呵呵~ 不过在我集齐之前就厌倦了吃干脆面的日子, 小孩子嘛, 都比较喜新厌旧, 印象比较深的是我有排名考前的几张以及第108张"鼓上蚤——时迁". 现在淘宝上已经有人在卖这个系列的卡片, 都很便宜. 这里也有对于其中部分卡片的精彩点评.
这和伯努利试验 (Bernoulli trial) 又有什么关系? 主要是我今天在看CLRS的时候突然想用概率的知识来算算到底我需要买多少袋干脆面才能集齐108张水浒卡片, 这个应该不算很蛋疼吧, 囧. OK, 闲话少说, 现在我们的目标是收集108张各不相同的卡片, 收集到一张就算成功一次. 那种结果或者成功, 或者失败的试验就叫做伯努利试验, 因此如果我们要集齐的话, 就需要进行n次伯努利试验, 这个n也就是一共需要购买干脆面的期望袋数. 把这n次试验分成108个阶段, 每一个阶段代表上一次收集成功到这一次收集成功间的过程, 比如第108阶段就是在成功收集到107张之后至收集到108张这之间需要经历的过程. 每一个阶段又是一系列小的伯努利试验, 把所有阶段的试验次数加起来也就得到了n的值.
在搞清楚基本原理之后, 来计算一下每一个阶段成功的概率, 也就是我在买了无数袋干脆面之后终于拿到一张不是重复卡片的概率. 假设现在是第i阶段, 证明我已经成功收集了i - 1张卡片, 还剩下108 - i + 1张没有被拿到. 每一张卡片被拿到的概率是1/108, 108 - i + 1张卡片被拿到的概率就是(108 - i + 1)/108, 即是每一个阶段成功的概率. 而第i阶段所进行的一系列伯努利试验的次数ni是服从几何分布的随机变量, 根据几何分布的性质:
上面的期望值就是每一个阶段成功时进行的试验次数, 正如前面所说, 把每一个阶段的试验次数都加起来也就得到了总的试验次数, 也就是我需要买的干脆面袋数, 计算过程如下:
算下来大约需要购买506袋干脆面才能集齐卡片, 也许当时我再坚持那么一下下就可以了, :)
这个问题的变种还有将球投入n个盒子中, 计算需要投多少个球才能让每一个盒子中都至少有一个球.
No comments:
Post a Comment