冲突问题

生日问题

如果一个房间里有23个人. 那么有两个人生日相同的概率至少为50%. 这是从以下的theorem得到的: 当你从1到n的范围里面随机抽取m个数(可以视作给m个人各自随机分配一个1-n的号码), 至少有两人号码相同的概率为:

\[ p_{m,n} = 1 - \frac{n!}{(n-m)!\,n^m} \;=\; 1 - \frac{m!}{n^m} \binom{n}{m}. \]

证明: 要算"至少有两人号码相同"的概率, 常用的办法是先算它的对立事件--"所有人都选到了不同的数字"的概率, 然后用p(至少有重复)=1-p(全都不同). 总的分配方式数为\(n^m\), 因为给m个人各选一个数字(从1到n), 总共有\(n^m\)种可能. 如果我们要求m个人所选的数字都不重复, 那么相当于从n个数字中挑选出m个互不相同的数字并分配给m个人, 第一个人可以从n个数字中挑选, 第二个人可以从n-1个数字中挑选..., 第m个人可以从n-m+1个数字中挑选, 因此满足"所有人都不同"的选法总数是\(n\times (n-1)\times (n-2)\times ...\times (n-m+1)\), 也可以用排列数记作\(\frac{n!}{(n-m)!}\). 因为所有\(n^m\)种分配方式是等可能的, 所以这个概率就是:

\[ \frac{n\times (n-1)\times ...\times (n-m+1)}{n^m}=\frac{\frac{n!}{(n-m)!}}{n^m}=\frac{n!}{(n-m)!n^m} \]

那么, "至少有两人号码相同"的概率就是:

\[ p_{m, n}=1-\frac{n!}{(n-m)!n^m} \]

注意到:

\[ \binom{n}{m} = \frac{n!}{m! \, (n-m)!}. \]

将其代入, 即可得证. 该函数的示例图像为:

球碰撞问题

将m个球随机扔到n个箱子, 计算有多少对不同的球落到了同一个箱子里. 设C表示碰撞总数. 每一对不同的球(i, j)(i<j)都可能碰撞(即落到同一个箱子), 每对球碰撞的概率为1/n(因为两球独立, 均匀地选箱子), 共有\(\binom{m}{2}=\frac{m(m-1)}{2}\)对球. 利用期望的线性性, 碰撞总数的期望可以表示为:

\[ E[C]=\sum_{1\leq i<j\leq m>}P(\text{i and j in same box})= \binom{m}{2}\cdot \frac{1}{n}=\frac{m(m-1)}{2n} \]

球碰撞问题是否是独立的

这个问题中, 每对球落在同一个箱子里的事件并不是互相独立的. 举个例子, 如果我们已经知道了球1和球2落在了同一个箱子里, 那么这对球1和球3是否也在同一个箱子里会产生一定的影响. 不过, 尽管它们不是独立事件, 我们依然可以使用期望的线性性计算总碰撞数的期望, 因为线性性不要求事件之间是相互独立的.