贈券收集問題

機率論問題

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

外部連結