我是否吃遍了食堂的盘子?

前一阵子突发奇想,想看看吃饭吃了这么久,是不是把食堂里的盘子都吃过一遍了。提出问题如下: 现存在1,2,3号个盘子,每次吃饭拿一个盘子,用完之后放回去,请问吃了5次饭之后三个盘子都被用过的概率是多少?如果是m个盘子,吃了n次饭所有的盘子都被用过的概率呢?

求概率

虽然我猜出了公式,但是还是不怎么懂。。。讲一下猜的过程:

  1. 3个盘子吃了5次饭的情况。 既然我要算所有盘子都被吃过的情况,那么只要排除掉盘子没吃过的情况就好了。首先考虑只用了2个盘子的情况,总够有\(C^2_3 \cdot 2^5\)种。但是要注意到这里对2个盘子的穷举已经包括了只用了1个盘子的情形而且还冗余了,所以要减掉冗余的3种情况。 所以三个盘子都被用过的概率为:
    \[1-\frac{C^2_3 \cdot 2^5 -3}{3^5}=\frac{150}{243}\]
  2. 4个盘子吃了5次饭的情况。 这里我们首先考虑只用了3个盘子的情况,共有\(C^3_4 \cdot 3^5\)种情况。但是对这3个盘子的情况的列举已经包括了只包含2个盘子的情况,所以要减去\(C^2_4 \cdot 2^5\)种2个盘子的情况,但是要注意的是对这2个盘子的列举又已经包括了1个盘子的情况,所以要加上种只含一个盘子的情况\(C^1_4 \cdot 1^5\)补回来。 所以三个盘子都被用过的概率为:
    \[ 1-\frac{C^3_4 \cdot 3^5-C^2_4 \cdot 2^5+C^1_4 \cdot 1^5}{4^5}=\frac{240}{1024} \]
  3. m个盘子吃了n次饭的情况。 根据上面的减减加加的想法推断(完全是瞎猜好么),就可以得到m个盘子吃了n次饭的概率公式:
    \[ 1-\frac{C^{m-1}_n \cdot (m-1)^n-C^{m-2}_n \cdot (m-2)^n+... \pm C^1_n \cdot 1^n}{m^n} \]
    m个盘子都被用过的概率为: 随便代入一个例子。m=20,n=50得到的概率为:0.16417976964878256。用模拟的方法发现这个数是对的- -。

求期望

虽然我们知道了具体的概率,还是希望有个期望值来告诉我们大概在吃几个盘子的时候你能够舔遍全食堂的盘子。根据《算法导论》5.4.2的说法,我们将吃到以前没吃过的盘子的时候定义为“命中”,然后我们要求为了吃完m个盘子需要吃的次数n。

命中次数可以用来讲n次吃饭划分为多个阶段。第i个阶段包括从第i-1次命中到第i次命中所吃的次数。第1阶段因为所以盘子都没被吃过,所以是必中的。第i阶段的每一次吃饭,都有i-1个盘子被吃过,m-i+1个盘子没被吃过,这样第i次命中的概率就是(m-i+1)/m。

\(n_i\)表示第i阶段的吃饭次数。每个随机变量\(n_i\)都服从概率为(m-i+1)/m的几何分布。根据几何分布的期望可以算得
\[ E[n_i]=\frac{m}{m-i+1}\]
由期望的线性性质,可以得到
\[E[n]=E[\sum^m_{i=1}n_i]=\sum^m_{i=1}E[n_i]=\sum^m_{i=1}\frac{m}{m-i+1}=m \sum \frac{1}{m}=m(\ln m+O(1))\]

最后的式子是调和级数的上界,所以我们希望吃完所有的盘子大概需要\(m\ln m\)次,这个问题也被称作赠卷收集者问题(coupon collector’s problem)。 如果食堂有1000 个盘子,我们大学4年估计是吃不完的。。。

三硬币问题-一个EM算法和Gibbs Sampling的例子

讲一个EM算法和Gibbs 抽样的小例子,用于加深理解(变分推断版本请见变分推断学习笔记(3)——三硬币问题的变分推断解法)。

题目(引用自参考1):假设有3枚硬币,分别记做A,B,C。这些硬币正面出现的概率分别是\(\pi\),\(p\)\(q\)。进行如下掷硬币实验:先掷硬币A,根据其结果选出硬币B或C,正面选B,反面选硬币C;然后投掷选重中的硬币,出现正面记作1,反面记作0;独立地重复\(n\)次(n=10),结果为 \[1111110000\] 我们只能观察投掷硬币的结果,而不知其过程,估计这三个参数\(\pi\),\(p\)\(q\)

EM算法

可以看到投掷硬币时到底选择了B或者C是未知的。我们设隐藏变量Z 来指示来自于哪个硬币,\(Z=\{z_1,z_2,\ldots,z_n \}\),令\(\theta=\{\pi,p,q\}\),观察数据\(X=\{x_1,x_2,\ldots,x_n \}\)

写出生成一个硬币时的概率: \[\begin{split}P(x|\theta) & =\sum_z P(x,z|\theta)=\sum_z P(z|\pi)P(x|z,\theta) \\& =\pi p^x (1-p)^{1-x}+(1-\pi)q^x(1-q)^{1-x} \\\end{split}\] 有了一个硬币的概率,我们就可以写出所有观察数据的log似然函数: \[L(\theta|X)=\log P(X|\theta)=\sum^n_{j=1}\log[\pi p^{x_j} (1-p)^{1-{x_j}}+(1-\pi)q^{x_j}(1-q)^{1-{x_j}}]\] 然后求极大似然 \[\hat{\theta}=\arg \max L(\theta|X)\] 其中\(L(\theta|X)=\log P(X|\theta)=\log \sum_Z P(X,Z|\theta)\)。因为log里面带着加和所以这个极大似然是求不出解析解的。

Read More