跳至內容

彩券收集問題

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

外部連結

[編輯]