跳转到内容

贈券收集問題

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

贈券收集問題(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

外部連結