跳转到内容

赠券收集问题

本页使用了标题或全文手工转换
维基百科,自由的百科全书

赠券收集问题(Coupon collector's problem) 是概率论中的著名题目,其目的在解答以下问题:

假设有n赠券,每种赠券获取概率相同,而且赠券亦无限供应。若取赠券t张,能集齐n种赠券的概率多少?

计算得出,平均需要次才能集齐n种赠券——这就是赠券收集问题的时间复杂度。例如n = 50时大约要取 次才能集齐50种赠券。

问题内容

赠券收集问题的特征是开始收集时,可以在短时间内收集多种不同的赠券,但最后数种则要花很长时间才能集齐。例如有50种赠券,在集齐49种以后要约多50次收集才能找到最后一张,所以赠券收集问题的答案t的期望要比50要大得多。

解答

计算期望

假设T是收集所有n种赠券的次数,是在收集了第i-1种赠券以后,到收集到第i种赠券所花的次数,那么T都是随机变量。在收集到i-1种赠券后能再找到“新”一种赠券的概率是,所以是一种几何分布,并有期望。根据期望的线性性质,

其中调和数,根据其近似值,可化约为:

其中欧拉-马歇罗尼常数.

那么,可用马尔可夫不等式求取概率的上限:

方差

基于相互独立的特性,则有:

最末一行的等式来自黎曼ζ函数巴塞尔问题。此式继而可用切比雪夫不等式求取概率上限:

尾部估算

我们亦可用以下方法求另一个的上限:假设表示在首r次收集中未有见到第i种赠券,则

所以,若,则有.

用生成函数的解法

另一种解决赠券收集问题的方法是用生成函数

观察得出,赠券收集的过程必然如下:

  • 收集第一张赠券,其出现的概率是
  • 收集了若干张第一种赠券
  • 收集到一张第二种赠券,其出现的概率是
  • 收集了若干张第一种或第二种赠券
  • 收集到一张第三种赠券,其出现的概率是
  • 收集了若干张第一种、第二种或第三种赠券
  • 收集到一张第四种赠券,其出现的概率是
  • 收集到一张最后一种赠券,其出现的概率是

若某一刻已若干种赠券,再收集到一张已重复的赠券的概率是p,那么,再收集到m张已重复的赠券的概率就是。则就此部分而言,有关m概率母函数(PGF)是

若将上述收集过程分割为多个阶段,则整个收集过程所花的时间的概率母函数为各部分的乘积,亦即

那么,根据概率生成函数的特性,总收集次数T期望

而某一T的概率则是

计算E(T)可先化简

因为

所以

故此可得出

其中的连加部分可化简:

所以得出:

用概率生成函数可同时求取变异量。变异量可写作

其中

故得出:

参考文献

  • Paul Erdős and Alfréd Rényi, On a classical problem of probability theory, Magyar Tud. Akad. Mat. Kutato Int. Kozl, 1961.
  • William Feller, An introduction to Probability Theory and its Applications, 1957.
  • Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005
  • Donald J. Newman and Lawrence Shepp, The Double Dixie Cup Problem, American Mathematical Monthly, Vol. 67, No. 1 (Jan., 1960), pp. 58–61.
  • Philippe Flajolet, Danièle Gardy, Loÿs Thimonier Birthday paradox, coupon collectors, caching algorithms and self-organizing search.页面存档备份,存于互联网档案馆, Discrete Applied Mathematics, Vol. 39, (1992), pp. 207–229

外部链接