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

前一阵子突发奇想,想看看吃饭吃了这么久,是不是把食堂里的盘子都吃过一遍了。提出问题如下: 现存在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年估计是吃不完的。。。