Coupon Collector's Problem

QQ截图20161228095208.png

简单化的问题：

问：一个有理想抱负的女生交男朋友，交到所有12个星座的男朋友的期望是多少（假设每个星座的概率是1/12）？

答：

这里利用Geometric Distribution的性质解答这个问题。

什么是Geometric Distribution以及他的性质？

1.png 2.png

我们可知，直到第X次成功的概率以及其期望。

直到第X成功的概率：

$$
P(X=x|p)=p(1-p)^{x-1}
$$

期望：

$$
\frac{1}{p}
$$
举例：不停地投掷1枚硬币，当正面出现的时候，停止投掷。

投掷1次，就停下来的概率
$$
P(x=1|\frac{1}{2}) =\frac{1}{2} \times(1-\frac{1}{2})^{1-1}
$$
投掷2次，就停下来的概率
$$
P(x=2|\frac{1}{2}) =\frac{1}{2} \times(1-\frac{1}{2})^{2-1}
$$
投掷3次，就停下来的概率
$$
P(x=3|\frac{1}{2}) =\frac{1}{2} \times(1-\frac{1}{2})^{3-1}
$$
。。。。。。。。。。。。。。

不停地投掷1枚硬币，当正面出现的时候，停止投掷。投掷次数的期望是
$$
\frac{1}{\frac{1}{2}}=2
$$
同理，一开始，获得某一个星座的期望是
$$
\frac{1}{\frac{12}{12}}=1
$$
接下来不停地交男朋友，当不同于第一个星座的人出现的时候，停止交男朋友。交男朋友的期望是
$$
\frac{1}{\frac{11}{12}}=\frac{12}{11}
$$
接下来不停地交男朋友，当不同于前两个星座的人出现的时候，停止交男朋友。交男朋友的期望是
$$
\frac{1}{\frac{10}{12}}=\frac{12}{10}
$$
。。。以此类推

最后期望是这些值相加
$$
\frac{12}{12}+\frac{12}{11}+\frac{12}{10}+\frac{12}{9}+...+\frac{12}{1}=
$$

a=0
for(i in 1:12){
  a = 12/i + a
}

R计算可得最后结果是37.23853。也就是这个有理想抱负的女生交到12个不同星座的男朋友大约需要交38个男朋友。

复杂点的问题：

简单的问题中的一个假设，现实是不成立的，就是每个星座的概率不是均分的十二分之一，虽然都很接近十二分之一。

根据每个星座的日期区间，我们可以知道狮子是32天，白羊、金牛、双子、巨蟹、处女是31天，天秤、天蝎、摩羯、水瓶是30天，射手是29天，双鱼比较特殊，闰年是30天，而非闰年是29天。

所以我们可以得到随便抓一个人，他是狮子的概率
$$
\frac{1}{4}\times\frac{32}{366}+\frac{3}{4}\times\frac{32}{365}=\frac{2449}{27953} \approx 0.087611
$$
他是白羊、金牛、双子、巨蟹、处女的概率
$$
\frac{1}{4}\times\frac{31}{366}+\frac{3}{4}\times\frac{31}{365}=\frac{3908}{46045} \approx 0.084873
$$
他是天秤、天蝎、摩羯、水瓶的概率
$$
\frac{1}{4}\times\frac{30}{366}+\frac{3}{4}\times\frac{30}{365}=\frac{1463}{17812} \approx 0.082136
$$
他是射手的概率
$$
\frac{1}{4}\times\frac{29}{366}+\frac{3}{4}\times\frac{29}{365}=\frac{4393}{55329} \approx 0.079398
$$
他是双鱼的概率
$$
\frac{1}{4}\times\frac{30}{366}+\frac{3}{4}\times\frac{29}{365}=\frac{1783}{22265} \approx 0.080081
$$

做到这里我发现，再做下去就是坑了。于是我放弃了。