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 为$Y为当m 是什么数量级时，使得n种采票$Z_i$Zi​收集起：
即$m=?\\ \min{Zi} >0$m=?minZi>0

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

3 解决$Y_K$YK​的求法

3.1 初始化

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

3.2 递推公式

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

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

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

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

3.3 求问题Y

由具体的物理意义可知

$Y=Y_n=(Y_1-Y_0)+(Y_2-Y_1)+(Y_3-Y2)+(Y_4-Y_3)+\dots+(Y_n-Y_{n-1})\\ =Z_1+Z_2+Z_3+Z_4+ \dots+Z_n$Y=Yn​=(Y1​−Y0​)+(Y2​−Y1​)+(Y3​−Y2)+(Y4​−Y3​)+⋯+(Yn​−Yn−1​)=Z1​+Z2​+Z3​+Z4​+⋯+Zn​

求Y的均值
$E(Y) =E(Z_1)+E(Z_2)+E(Z_3)+E(Z_4)+ \dots+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}=nH_n(H_n为调和级数Harmonic series，lnn+c)\\=nlnn+cn$E(Y)=E(Z1​)+E(Z2​)+E(Z3​)+E(Z4​)+⋯+E(Zn​)=k=1∑n​pk​1​=k=1∑n​n−k+1n​=nk=1∑n​n−k+11​=nk=1∑n​k1​=nHn​(Hn​为调和级数Harmonicseries，lnn+c)=nlnn+cn
即$Y \sim nlnn \pm\theta(n)$Y∼nlnn±θ(n)
我们如果Y 的访差较小，即可以将Y的界限定在bound E（Y）附近。
$Var(Y)=Var(Z_1+Z_2+Z_3+Z_4+ \dots+Z_n)$Var(Y)=Var(Z1​+Z2​+Z3​+Z4​+⋯+Zn​)
$Z_k$Zk​服从独立分布
$Var(Y)=Var(Z_1+Z_2+Z_3+Z_4+ \dots+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$Var(Y)=Var(Z1​+Z2​+Z3​+Z4​+⋯+Zn​)=k=1∑n​pk2​1−pk​​=k=1∑n​pk2​1​−pk​1​=k=1∑n​((n−k+1)2n2​−n−k+1n​)==k=1∑n​(n−k+1)2n2​−k=1∑n​n−k+1n​==n2k=1∑n​(n−k+1)2​−nk=1∑n​n−k+11​=n2k=1∑n​k21​−nk=1∑n​k1​=6π2​n2−nlnn
$Var(Y)\sim \theta(n^2)$Var(Y)∼θ(n2)