Birthday Problem and Hash Collision

1月份的时候,我们公司的数据部门给我们做了一次统计学的培训。 那天参加培训的大概有30-40人,主讲当时提了这样一个问题,在参加培训的人当中,有两个人是同月同日生的概率是多少? 答案是“大于70%”。这个答案令当场的很多人吃惊。于是现场做了一下实验,确实找到了两个生日相同的人。

这个问题如果从数学角度来分析,可以看成这样:有m个球,和n个桶。依次将这m个球扔入这n个桶中的随机一个。最终,有一个桶内至少有两个球的概率是多少?

解答:

首先,我们拿起一个球,随便扔到一个桶里。然后拿起第二个球,也扔到一个桶里。那么第二个球和第一个球被扔进同一个桶里的概率是\( \frac{1}{n} \),不在同一个桶里的概率是\( 1- \frac{1}{n} \)。假设前两个球不在同一个桶里,那么我们继续,拿起第三个球扔下去,它和前两个球不在同一个桶里的概率是\( 1- \frac{2}{n} \)。即,对于第k个球来说,假如前面k-1个球都在不同的桶里,那么第k个球被扔到一个新桶中的概率就是\( 1- \frac{k-1}{n} \)。于是,最终有一个桶内至少有两个球的概率就是

$$ P =1 - (1- \frac{1}{n})(1- \frac{2}{n})(1- \frac{3}{n}) \dots (1- \frac{m-1}{n}) $$

下面尝试给出一个更简单的近似值:

首先,高等数学课上学过一个很重要的式子:当x远远小于1时,有\(e^x \approx 1 + x \)。于是,当m远远小于n的时候:

$$ (1- \frac{1}{n})(1- \frac{2}{n})(1- \frac{3}{n}) \dots (1- \frac{m-1}{n}) \approx \Pi_{j=1}^{m-1}e^{-\frac{j}{n}} = e^{-\sum_{j=1}^{m-1}{\frac{j}{n}}} = e ^ {-\frac{m(m-1)}{2n}} $$

生日问题其实在计算机算法中经常遇到:假设一个Hash Table有n个桶,需要插入m个元素,那么插入过程中发生hash冲突的概率是多大? \( 1- e ^ {-\frac{m(m-1)}{2n}} \)

另外,假如我希望发生hash冲突的概率小于0.5,那么n至少应该为多大?求解

$$ 1- e ^ {-\frac{m(m-1)}{2n}} \lt \frac{1}{2} $$

可得:

$$ n \gt \frac{m(m-1)}{2\ln{2}} $$

即,为了让发生hash 冲突的概率保持不变,当hash表中的元素数量(m)增长时,桶的数量(n)必须以平方的速度增长。\( n \approx m^2 \)。

对于生日问题,假设一年有365天,那么当人数大于23的时候,有两个人具有相同生日的概率就大于0.5。

很多书上把\( \frac{m}{n} \)定义为hash table的load factor,并且在hash table的实际实现中,在capacity增长的时候会将load factor大致保持在常数。也就是说桶的数量(n)是线性增长的,这么做是因为,在这种策略下,为了查找一个就在其中的元素,它的平均查找时间是一个常数。在这种情况下,就不要再用上面的这些式子计算P,因为前面\(e^{\frac{m}{n}} \approx 1 + \frac{m}{n} \) 的前提是m远远小n。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥