Coupon Collector's Problem高级算法设计

1 Geometric Distribution

用X表示n 次投掷coin（独立伯努力分布）中，首次出现正面时，投掷的次数，X可能的取值为1，2，3，。。。N，假设每次正面的概率为1/2（一般化可设为p）

具体参考

2 Coupon Collector’s Problem（CCP）

2.1关注点

CCP关注的是分散，与Balls of Bin 问题不同（其关注的是会不会集中，集中的程度有多少）

2.2 问题定义

设有采票 m张,需要集起n 种不同的类型，当集起n种类型的采票时，可以进行对奖或其它操作
当然可以抽象为Balls of Bin 问题形式，其中所用有的m张采票为m个球，要求集起的n张采票为n个不同的盒子，因此可以问题定义为m个球装在不同的n个盒子里，要求同一个盒子装同一种采票，且每个盒子都必须装满。

2.2.1 具体说

定义问题$Y为$当m 是什么数量级时，使得n种采票$Z_i$收集起：
即$$\begin{gathered} m=? \\ \min Zi>0 \end{gathered}$$

定义问题$Y_K$ 投入多少球(或采票（m的值）),才能使$K$个不同的盒子装（或收集起$n$张不同的采票以对奖）
$$\begin{gathered} m=? \\ \min Z_i>0 \\ (i=0，1，2\dots K) \\ (K\in n) \end{gathered}$$

3 解决$Y_K$的求法

3.1 初始化

令$Y_0$=0,即不收集彩票，自然不需要采票，m=0
而$Y_1$=1

3.2 递推公式

定义$Y_k?Y_{k?1}=Z_k$,先思考如何由$Y_{k?1}$求得$Y_k$?
$Y_{k?1}$表示需要多少个球，才能使得n 个盒子中有$k?1$个盒子被装；
$Y_k$表示需要多少个球，才能使得n 个盒子中有$k$个盒子被装；

如图红色表示需要$Y_{k?1}$个球装在了n个盒子中的$k?1$个，那么计算需要$Y_k$个球，装下n 个盒子中的k个盒子时，只需将第k个球装在剩下的n-k+1个盒子中。
定义$p_k$表示第k个球恰好装入n-k+1（黑色盒子）的概率，$1?p_k$表示进入k-1 个 盒子中的概率，即有如下表达：
$$\begin{gathered} p_k=\frac{n?k+1}{n} \\ 1?p_k=\frac{k?1}{n} \end{gathered}$$

那么上面定义的$Z_k$便有了具体的物理意义，即是第一节提到的几何分布，表示需要新增$Z_k$个球（可以理解为重复$Z_k$次投掷coin ）才能使得有一个球不落入红色部分的盒子中。

$$伯努力分布：掷硬币=\{\begin{array}{rlr}{p}_k& & 正面，落入黑色部分\\ 1?p_k& & 反面，即落入红色的部分\end{array}$$
因此重复$Z_k=z$次投掷＂coins＂首次落入黑色的部分可以根据二项分布来计算:$Pr(Z_k=z)=(1?p_k{)}^{z?1}{p}_k$
而首次落入黑色部分平均需要投郑几次,即$E(Z_k)=\frac{1}{p_k}$,其方差$Var(Z_k)=\frac{1?p_k}{p_k^2}$

3.3 求问题Y

由具体的物理意义可知

$$\begin{gathered} Y=Y_n=(Y_1?Y_0)+(Y_2?Y_1)+(Y_3?Y2)+(Y_4?Y_3)+?+(Y_n?Y_{n?1}) \\ =Z_1+Z_2+Z_3+Z_4+?+Z_n \end{gathered}$$

求Y的均值
$$\begin{gathered} E(Y)=E(Z_1)+E(Z_2)+E(Z_3)+E(Z_4)+?+E(Z_n) \\ =\sum _{k=1}^n\frac{1}{p_k} \\ =\sum _{k=1}^n\frac{n}{n?k+1} \\ =n\sum _{k=1}^n\frac{1}{n?k+1} \\ =n\sum _{k=1}^n\frac{1}{k}=n{H}_n(H_n为调和级数Harmonicseries，lnn+c) \\ =nlnn+cn \end{gathered}$$
即$$Y?nlnn\pm \theta (n)withhighprobability$$
$$Y?(n\ln n?cn,n\ln n+cn)withhighprobability$$
我们如果Y 的访差较小，即可以将Y的界限定在bound E（Y）附近。
$$Var(Y)=Var(Z_1+Z_2+Z_3+Z_4+?+Z_n)$$
$Z_k$服从独立分布
$$\begin{gathered} Var(Y)=Var(Z_1+Z_2+Z_3+Z_4+?+Z_n) \\ =\sum _{k=1}^n\frac{1?p_k}{p_k^2}=\sum _{k=1}^n\frac{1}{p_k^2}?\frac{1}{p_k} \\ =\sum _{k=1}^n(\frac{n^2}{(n?k+1{)}^2}?\frac{n}{n?k+1})= \\ =\sum _{k=1}^n\frac{n^2}{(n?k+1{)}^2}?\sum _{k=1}^n\frac{n}{n?k+1}= \\ =n^2\sum _{k=1}^n\frac{}{(n?k+1{)}^2}?n\sum _{k=1}^n\frac{1}{n?k+1}= \\ {n}^2\sum _{k=1}^n\frac{1}{k^2}?n\sum _{k=1}^n\frac{1}{k}= \\ \frac{{\pi }^2}{6}{n}^2?nlnn \end{gathered}$$
$$Var(Y)?\theta (n^2)$$

利用切比雪夫不等式
Pr?{∣X?E(x)∣≥cn}≤Var(Y)c2n2=O(1)\Pr\{|X-E(x)|\ge cn\}\le \frac{Var(Y)}{c^2n^2}=O(1)Pr{ ∣X?E(x)∣≥cn}≤c2n2Var(Y)?=O(1)

进一步思考

• 当$m?\theta (n\ln n)时$，同时可以限定住$\min Z_i$,$\max Z_i$：即$\min Z_i?\theta (\frac{m}{n})=\theta (\ln n)$
• theorem
  当$m>cn\ln n=8n\ln n$时$$\begin{gathered} \min Z_i,\max Z_i?\theta (m/n) \\ withhighprobability \end{gathered}$$
  即证 在m满足上面条件时有$Pr(\frac{1}{2}\frac{m}{n}\le \min Z_i,\max Z_i\le 2\frac{m}{n})=1?O(1)$

证明

要证$$Pr(\max Z_i\le 2\frac{m}{n})=1?O(1)$$即证$$1?Pr(\max Z_i\le 2\frac{m}{n})=O(1)$$
即证
$$Pr(\max Z_i>2\frac{m}{n})=O(1)即它的上界为小O(1)$$
而$$\begin{gathered} Pr(\max Z_i>2\frac{m}{n})= \\ Pr(Z_1>2\frac{m}{n})?Pr(Z_2>2\frac{m}{n})???Pr(Z_n>2\frac{m}{n}) \\ \le \sum _{i=1}^{n}Pr(Z_i>2\frac{m}{n})不访设Z_1对应的概率最大 \\ \le n\mathrm{Pr}(Z_1>2\frac{m}{n})(1) \end{gathered}$$

定义0-1 变量

X={X1,X2,…,Xi,…Xm}X=\{X_1,X_2,\dots,X_i,\dots X_m\}X={ X1?,X2?,…,Xi?,…Xm?}
$$X_i=?\begin{array}{rlr}1& & 第i个球落入第1个盒子中withprobability\frac{1}{n}\\ 0& & 第i个球不落入第1个盒子withprobability1?\frac{1}{n}\end{array}$$
因此$Z_1={\sum }_{i=1}^m{X}_i$
$E(Z_1)={\sum }_{i=1}^{m}E(X_i)=\frac{m}{n}$
利用CherNoff’s Bound

而Pr(max?Zi>2mn)=≤nPr?(Z1>2mn)=nPr?(Z1>(1+1)mn)≤n{e4}mn（当m>8nln?n时即mn=8ln?n）≤n[e4]8ln?n=O(1)Pr(\max Z_i >2\frac{m}{n})= \leq n\Pr(Z_1>2\frac{m}{n}) \\ =n\Pr(Z_1>(1+1)\frac{m}{n}) \leq n\{\frac{e}{4}\}^{\frac{m}{n}}\\ （当m>8n\ln n 时 即\frac{m}{n}=8\ln n） \\ \le n[\frac{e}{4}]^{8\ln n}=O(1) Pr(maxZi?>2nm?)=≤nPr(Z1?>2nm?)=nPr(Z1?>(1+1)nm?)≤n{ 4e?}nm?（当m>8nlnn时即nm?=8lnn）≤n[4e?]8lnn=O(1)

证明$$Pr(\min Z_i\ge \frac{1}{2}\frac{m}{n})=1?O(1)$$即证$$1?Pr(\min Z_i\ge \frac{1}{2}\frac{m}{n})=O(1)$$

即证

$$Pr(\min Z_i<\frac{1}{2}\frac{m}{n})=O(1)即它的上界为小O(1)$$
而$$\begin{gathered} Pr(\max Z_i<\frac{1}{2}\frac{m}{n})= \\ Pr(Z_1<\frac{1}{2}\frac{m}{n})?Pr(Z_2<\frac{1}{2}\frac{m}{n})???Pr(Z_n<\frac{1}{2}\frac{m}{n}) \\ \le \sum _{i=1}^{n}Pr(Z_i<\frac{1}{2}\frac{m}{n})不访设Z_1对应的概率最大 \\ \le n\mathrm{Pr}(Z_1<\frac{1}{2}\frac{m}{n})(1) \end{gathered}$$

$$\begin{gathered} \le n[\frac{e^{?\frac{1}{2}}}{（1/2{）}^{1/2}}{]}^{m/n}=n[2/e{]}^{m/2n}=n[2/e{]}^{4\ln n}=n0.3^{\ln n}=n{e}^{?1.2\ln n} \\ =O(1)(m/n=8\ln n) \end{gathered}$$