查看“贈券收集問題”的源代码

'''贈券收集問題'''是[[機率論]]中的著名題目，其目的在解答以下問題：
:假設有''n''種贈券，每種贈券獲取機率相同，而且贈券亦無限供應。若取贈券''t''張，能集齊''n''種贈券的機率多少？
計算得出，平均来说需要<math>\Theta(n\ln(n))</math>次才能集齊''n''種贈券——这就是赠券收集问题的[[时间复杂度]]。例如''n'' = 50時大約要取 <math>50\ln(50)+50\gamma+1/2 \approx 195.6011+28.8608+0.5\approx 224.9619</math>次才能集齊50種贈券。

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

==解答==

=== 計算期望值 ===
假設''T''是收集所有''n''種贈券的次数，<math>t_i</math>是在收集了第''i-1''種贈券以後，到收集到第''i''種贈券所花的次数，那麼''T''和<math>t_i</math>都是[[隨機變量]]。在收集到''i-1''種贈券後能再找到「新」一種贈券的概率是<math>p_i = \frac{n - i + 1}{n}</math>，所以<math>t_i</math>是一種[[幾何分佈]]，並有[[期望值]]<math>\frac{1}{p_i}</math>。根據期望值的線性性質，
:<math>
\begin{align}
\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{align}
</math>

其中<math>H_n</math>是[[調和數]]，根據其近似值，可化約為：

:<math>
\operatorname{E}(T)  = n \cdot H_n = n \ln n + \gamma n + \frac1{2} + o(1), \ \ 
\text{as}  \ n \to \infty,
</math>
其中<math>\gamma \approx 0.5772156649</math>是[[歐拉-馬歇羅尼常數]]. 

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

:<math>\operatorname{P}(T \geq c \, n H_n) \le \frac1c.</math>

=== 方差 ===
基於<math>t_i</math>互相獨立的特性，則有：

:<math>
\begin{align}
\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 \le 2 n^2,
\end{align}
</math>

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

:<math>\operatorname{P}\left(|T- n H_n| \geq c\, n\right) \le \frac{2}{c^2}.</math>

=== 尾部估算 ===

我們亦可用以下方法求另一個的上限：假設<math>{Z}_i^r</math>表示在首''r''次收集中未有見到第''i''種贈券，則
:<math>
\begin{align}
P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n}
\end{align}
</math>

所以，若<math>r = \beta n \log n</math>，則有<math>P\left [ {Z}_i^r \right ] \le e^{(-\beta n \log n ) / n} = n^{-\beta}</math>. 
:<math>
\begin{align}
P\left [ T > \beta n \log n \right ] \le P \left [ 	\bigcup_i {Z}_i^{\beta n \log n} \right ] \le n \cdot P [ {Z}_1 ] \le n^{-\beta + 1}
\end{align}
</math>

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

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

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

若某一刻已若干種贈券，再收集到一張已重覆的贈券的機率是''p''，那麼，再收集到''m''張已重覆的贈券的機率就是<math>p^m</math>。則就此部分而言，有關''m''的[[概率母函数]]（PGF）是
:<math>G(z)=\sum_{m=0}^\infty p^mz^m = 1 + p z + p^2 z^2 + p^3 z^3 + \cdots = \frac{1}{1 - p z}</math>

若將上述收集過程分割為多個階段，則整個收集過程所花的時間的[[概率母函数]]為各部分的乘積，亦即
:<math> 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.</math>
那麼，根據機率生成函數的特性，總收集次數''T''的[[期望值]]是
:<math>\operatorname{E}(T) = \left. \frac{\mathrm{d}}{\mathrm{d}z} G(z) \right|_{z=1}</math>
而某一''T''的機率則是
:<math>\Pr(T=k) = \left.\frac{1}{k!}\frac{\mathrm{d}^kG(z)}{\mathrm{d}z^k}\right|_{z=0}</math>

計算E(''T'')可先化簡<math>G(z)</math>為
:<math> 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} </math>
因為
:<math> \frac{\mathrm{d}}{\mathrm{d}z} \frac{n-k}{n-kz} = \frac{k(n-k)}{(n-kz)^2}</math>
所以
:<math>\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)
</math>
故此可得出
:<math>\begin{align}
\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{align}</math>
其中的連加部分可化簡：
:<math> \sum_{k=1}^{n-1} \frac{k}{n-k} =
\sum_{k=1}^{n-1} \left( \frac{k}{n-k} - \frac{n}{n-k} \right) + n H_{n-1} =
n H_{n-1} - (n-1)</math>
所以得出：
<math> \operatorname{E}(T) = n + n H_{n-1} - (n-1) = n H_{n-1} + 1 = n H_n</math>

用機率生成函數可同時求取[[變異量]]。變異量可寫作
:<math>\operatorname{Var}(T) = 
\operatorname{E}(T(T-1)) + \operatorname{E}(T) - \operatorname{E}(T)^2</math>
其中
:<math>\begin{align}
\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)} - 2 n H_{n-1} + (n-1).
\end{align}</math>
故得出：
:<math>
\begin{align}
\operatorname{Var}(T) & = \;
n^2 H_n^2 - 1 + n^2 H_{n-1}^{(2)} - 2 n 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{align}</math>

== 參考文獻 ==
* 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 ''[http://algo.inria.fr/flajolet/Publications/alloc2.ps.gz Birthday paradox, coupon collectors, caching algorithms and self-organizing search.]'', ''Discrete Applied Mathematics'', Vol. 39, (1992), pp. 207–229

==外部連結==
* "[http://demonstrations.wolfram.com/CouponCollectorProblem/ Coupon Collector Problem]" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
* [http://www-stat.stanford.edu/~susan/surprise/Collector.html Coupon Collector Problem], Java applet.
* ''[http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/coupon.html How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?]'', a short note by Doron Zeilberger.

[[Category:概率论]]
[[Category:博弈论]]