贈券收集問題

Template:NoteTA 贈券收集問題(Coupon collector's problem) 是機率論中的著名題目，其目的在解答以下問題：

假設有n種贈券，每種贈券獲取機率相同，而且贈券亦無限供應。若取贈券t張，能集齊n種贈券的機率多少？

計算得出，平均需要$\mathrm{\Theta }(n\ln (n))$次才能集齊n種贈券——这就是赠券收集问题的时间复杂度。例如n = 50時大約要取 $50\ln (50)+50\gamma +1/2\approx 195.6011+28.8608+0.5\approx 224.9619$次才能集齊50種贈券。

問題內容

贈券收集問題的特徵是開始收集時，可以在短時間內收集多種不同的贈券，但最後數種則要花很長時間才能集齊。例如有50種贈券，在集齊49種以後要約多50次收集才能找到最後一張，所以贈券收集問題的答案t的期望值要比50要大得多。

解答

計算期望值

假設T是收集所有n種贈券的次数，$t_i$是在收集了第i-1種贈券以後，到收集到第i種贈券所花的次数，那麼T和$t_i$都是隨機變量。在收集到i-1種贈券後能再找到「新」一種贈券的概率是$p_i=\frac{n-i+1}{n}$，所以$t_i$是一種幾何分佈，並有期望值$\frac{1}{p_i}$。根據期望值的線性性質，

$\begin{array}{cc}\mathrm{E}(T)& =\mathrm{E}(t_1)+\mathrm{E}(t_2)+\cdots +\mathrm{E}(t_n)=\frac{1}{p_1}+\frac{1}{p_2}+\cdots +\frac{1}{p_n}\\ & =\frac{n}{n}+\frac{n}{n-1}+\cdots +\frac{n}{1}=n\cdot (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{n})=n\cdot H_n.\end{array}$

其中$H_n$是調和數，根據其近似值，可化約為：

$\mathrm{E}(T)=n\cdot H_n=n\ln n+\gamma n+\frac{1}{2}+o(1),\text{as}n\to \mathrm{\infty },$

其中$\gamma \approx 0.5772156649$是歐拉-馬歇羅尼常數.

那麼，可用馬爾可夫不等式求取機率的上限：

$\mathrm{P}(T\ge cn{H}_n)\le \frac{1}{c}.$

變異數

基於$t_i$相互獨立的特性，則有：

$\begin{array}{cc}\mathrm{Var}(T)& =\mathrm{Var}(t_1)+\mathrm{Var}(t_2)+\cdots +\mathrm{Var}(t_n)\\ & =\frac{1-p_1}{p_1^2}+\frac{1-p_2}{p_2^2}+\cdots +\frac{1-p_n}{p_n^2}\\ & \le \frac{n^2}{n^2}+\frac{n^2}{(n-1{)}^2}+\cdots +\frac{n^2}{1^2}\\ & \le n^2\cdot (\frac{1}{1^2}+\frac{1}{2^2}+\cdots )=\frac{{\pi }^2}{6}{n}^2\le 2n^2,\end{array}$

最末一行的等式來自黎曼ζ函數的巴塞爾問題。此式繼而可用切比雪夫不等式求取機率上限：

$\mathrm{P}(|T-n{H}_n|\ge cn)\le \frac{2}{c^2}.$

尾部估算

我們亦可用以下方法求另一個的上限：假設$Z_i^r$表示在首r次收集中未有見到第i種贈券，則

$\begin{array}{c}P\left[Z_i^r\right]={(1-\frac{1}{n})}^r\le e^{-r/n}\end{array}$

所以，若$r=\beta n\log n$，則有$P\left[Z_i^r\right]\le e^{(-\beta n\log n)/n}=n^{-\beta }$.

$\begin{array}{c}P[T>\beta n\log n]\le P\left[\bigcup _i{Z}_i^{\beta n\log n}\right]\le n\cdot P[Z_1]\le n^{-\beta +1}\end{array}$

用生成函數的解法

另一種解決贈券收集問題的方法是用生成函數。

觀察得出，贈券收集的過程必然如下：

• 收集第一張贈券，其出現的機率是$n/n=1$
• 收集了若干張第一種贈券
• 收集到一張第二種贈券，其出現的機率是$(n-1)/n$
• 收集了若干張第一種或第二種贈券
• 收集到一張第三種贈券，其出現的機率是$(n-2)/n$
• 收集了若干張第一種、第二種或第三種贈券
• 收集到一張第四種贈券，其出現的機率是$(n-3)/n$
• $\dots$
• 收集到一張最後一種贈券，其出現的機率是$1/n$

若某一刻已若干種贈券，再收集到一張已重覆的贈券的機率是p，那麼，再收集到m張已重覆的贈券的機率就是$p^m$。則就此部分而言，有關m的概率母函数（PGF）是

$G(z)=\sum _{m=0}^{\mathrm{\infty }}{p}^m{z}^m=1+pz+p^2{z}^2+p^3{z}^3+\cdots =\frac{1}{1-pz}$

若將上述收集過程分割為多個階段，則整個收集過程所花的時間的概率母函数為各部分的乘積，亦即

$G(z)=\frac{n}{n}z\cdot \frac{1}{1-\frac{1}{n}z}\cdot \frac{n-1}{n}z\cdot \frac{1}{1-\frac{2}{n}z}\cdot \frac{n-2}{n}z\cdot \frac{1}{1-\frac{3}{n}z}\cdot \frac{n-3}{n}z\cdots \frac{1}{1-\frac{n-1}{n}z}\cdot \frac{n-(n-1)}{n}z.$

那麼，根據機率生成函數的特性，總收集次數T的期望值是

$\mathrm{E}(T)={\frac{\mathrm{d}}{\mathrm{d}z}G(z)|}_{z=1}$

而某一T的機率則是

$\mathrm{Pr}(T=k)={\frac{1}{k!}\frac{{\mathrm{d}}^{k}G(z)}{\mathrm{d}{z}^k}|}_{z=0}$

計算E(T)可先化簡$G(z)$為

$G(z)=z^n\frac{n-1}{n-z}\frac{n-2}{n-2z}\frac{n-3}{n-3z}\cdots \frac{n-(n-1)}{n-(n-1)z}$

因為

$\frac{\mathrm{d}}{\mathrm{d}z}\frac{n-k}{n-kz}=\frac{k(n-k)}{(n-kz{)}^2}$

所以

$\frac{\mathrm{d}}{\mathrm{d}z}G(z)=G(z)(\frac{n}{z}+\frac{1}{n-z}+\frac{2}{n-2z}+\frac{3}{n-3z}\cdots +\frac{n-1}{n-(n-1)z})$

故此可得出

$\begin{array}{cc}\mathrm{E}(T)& ={\frac{\mathrm{d}}{\mathrm{d}z}G(z)|}_{z=1}\\ & =G(1)(n+\frac{1}{n-1}+\frac{2}{n-2}+\frac{3}{n-3}\cdots +\frac{n-1}{n-(n-1)})\\ & =n+\sum _{k=1}^{n-1}\frac{k}{n-k}\end{array}$

其中的連加部分可化簡：

$\sum _{k=1}^{n-1}\frac{k}{n-k}=\sum _{k=1}^{n-1}(\frac{k}{n-k}-\frac{n}{n-k})+n{H}_{n-1}=n{H}_{n-1}-(n-1)$

所以得出： $\mathrm{E}(T)=n+n{H}_{n-1}-(n-1)=n{H}_{n-1}+1=n{H}_n$

用機率生成函數可同時求取變異量。變異量可寫作

$\mathrm{Var}(T)=\mathrm{E}(T(T-1))+\mathrm{E}(T)-\mathrm{E}(T{)}^2$

其中

$\begin{array}{cc}\mathrm{E}(T(T-1))=& {\frac{{\mathrm{d}}^2}{\mathrm{d}{z}^2}G(z)|}_{z=1}\\ =& [G(z){(\frac{n}{z}+\frac{1}{n-z}+\frac{2}{n-2z}+\frac{3}{n-3z}\cdots +\frac{n-1}{n-(n-1)z})}^2\\ & {+G(z)(-\frac{n}{z^2}+\frac{1^2}{(n-z{)}^2}+\frac{2^2}{(n-2z{)}^2}+\frac{3^2}{(n-3z{)}^2}\cdots +\frac{(n-1{)}^2}{(n-(n-1)z{)}^2})]|}_{z=1}\\ =& n^2{H}_n^2-n+\sum _{k=1}^{n-1}\frac{k^2}{(n-k{)}^2}\\ =& n^2{H}_n^2-n+\sum _{k=1}^{n-1}\frac{(n-k{)}^2}{k^2}\\ =& n^2{H}_n^2-n+n^2{H}_{n-1}^{(2)}-2n{H}_{n-1}+(n-1).\end{array}$

故得出：

$\begin{array}{cc}\mathrm{Var}(T)& =n^2{H}_n^2-1+n^2{H}_{n-1}^{(2)}-2n{H}_{n-1}+n{H}_{n-1}+1-n^2{H}_n^2\\ & =n^2{H}_{n-1}^{(2)}-n{H}_{n-1}<\frac{{\pi }^2}{6}{n}^2\end{array}$

參考文獻

• 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. Template:Wayback, Discrete Applied Mathematics, Vol. 39, (1992), pp. 207–229

外部連結

• "Coupon Collector Problem Template:Wayback" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
• Coupon Collector Problem Template:Wayback, Java applet.
• How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect? Template:Wayback, a short note by Doron Zeilberger.
• Template:En getir indirim koduTemplate:Wayback