贈券收集問題

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

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

計算得出，平均需要 $\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{aligned}\operatorname {E} (T)&=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {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 \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\,=\,n\cdot H_{n}.\end{aligned}}$

其中 $H_{n}$ 是調和數，根據其近似值，可化約為：

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

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

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

　
: $\operatorname {P} (T\geq c\,nH_{n})\leq {\frac {1}{c}}.$

### 變異數

基於 $t_{i}$ 相互獨立的特性，則有：

　
: ${\begin{aligned}\operatorname {Var} (T)&=\operatorname {Var} (t_{1})+\operatorname {Var} (t_{2})+\cdots +\operatorname {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}}}\\&\leq {\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\\&\leq n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots \right)={\frac {\pi ^{2}}{6}}n^{2}\leq 2n^{2},\end{aligned}}$

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

　
: $\operatorname {P} \left(|T-nH_{n}|\geq c\,n\right)\leq {\frac {2}{c^{2}}}.$

### 尾部估算

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

　
: ${\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}$

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

　
: ${\begin{aligned}P\left[T>\beta n\log n\right]\leq P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}]\leq n^{-\beta +1}\end{aligned}}$

### 用生成函數的解法

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

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

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

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

　
: $G(z)=\sum _{m=0}^{\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_ 的期望值是

　
: $\operatorname {E} (T)=\left.{\frac {\mathrm {d} }{\mathrm {d} z}}G(z)\right|_{z=1}$

而某一 _T_ 的機率則是

　
: $\Pr(T=k)=\left.{\frac {1}{k!}}{\frac {\mathrm {d} ^{k}G(z)}{\mathrm {d} z^{k}}}\right|_{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)\left({\frac {n}{z}}+{\frac {1}{n-z}}+{\frac {2}{n-2z}}+{\frac {3}{n-3z}}\cdots +{\frac {n-1}{n-(n-1)z}}\right)$

故此可得出

　
: ${\begin{aligned}\operatorname {E} (T)&=\left.{\frac {\mathrm {d} }{\mathrm {d} z}}G(z)\right|_{z=1}\\&=G(1)\left(n+{\frac {1}{n-1}}+{\frac {2}{n-2}}+{\frac {3}{n-3}}\cdots +{\frac {n-1}{n-(n-1)}}\right)\\&=n+\sum _{k=1}^{n-1}{\frac {k}{n-k}}\end{aligned}}$

其中的連加部分可化簡：

　
: $\sum _{k=1}^{n-1}{\frac {k}{n-k}}=\sum _{k=1}^{n-1}\left({\frac {k}{n-k}}-{\frac {n}{n-k}}\right)+nH_{n-1}=nH_{n-1}-(n-1)$

所以得出： $\operatorname {E} (T)=n+nH_{n-1}-(n-1)=nH_{n-1}+1=nH_{n}$

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

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

其中

　
: ${\begin{aligned}\operatorname {E} (T(T-1))=&\left.{\frac {\mathrm {d} ^{2}}{\mathrm {d} z^{2}}}G(z)\right|_{z=1}\\=&\left[G(z)\left({\frac {n}{z}}+{\frac {1}{n-z}}+{\frac {2}{n-2z}}+{\frac {3}{n-3z}}\cdots +{\frac {n-1}{n-(n-1)z}}\right)^{2}\right.\\&\;\left.\left.+G(z)\left(-{\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}}}\right)\right]\right|_{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)}-2nH_{n-1}+(n-1).\end{aligned}}$

故得出：

　
: ${\begin{aligned}\operatorname {Var} (T)&=\;n^{2}H_{n}^{2}-1+n^{2}H_{n-1}^{(2)}-2nH_{n-1}+nH_{n-1}+1-n^{2}H_{n}^{2}\\&=\;n^{2}H_{n-1}^{(2)}-nH_{n-1}<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}$

## 參考文獻

* 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（頁面存檔備份，存於網際網路檔案館）