贈券收集問題

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

外部連結
 "Coupon Collector Problem " by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
 Coupon Collector Problem , Java applet.
 How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect? , a short note by Doron Zeilberger.
  getir indirim kodu

Category:概率论
Category:博弈论