level 7
ゴトゥーザ様
楼主
转自科学松鼠会：http://songshuhui.net/archives/23737.html
原题：生日悖论与生日攻击
作者：苏椰
挺有趣的 算是“反”常识吧 就转过来了
注意开头的“出现这种缘分”是指“出现”同生日而不是有人“和你”同生日
但是数字似乎依然和“实际经验”不符
=======
每个人都有生日，偶尔会遇到与自己同一天过生日的人，但在生活中，这种缘分似乎并不常有。我们猜猜看，在50个人当中，出现这种缘分的概率有多大，是10%，20%，还是50%？
有人告诉我，在文章开头插入公式十分倒胃，所以我就不写计算过程，直接给出结果（除了传统的排列组合方法外，Paul Halmos[1]还给出了一个巧妙的解法）。在50个人中有相同生日的概率，高达97%，这个数字，恐怕高出了绝大多数人的意料。
我们没有算错，是我们的直觉错了，科学与生活，又开了个玩笑。正因为计算结果与日常经验产生了如此明显的矛盾，该问题被称为“生日悖论(BirthdayParadox)”[2]。它体现的，是理性计算与感性认识的矛盾，并不引起逻辑矛盾，所以倒也算不上严格意义上的悖论。它的原始表述是：在23个人当中出现相同生日的概率大于50%[2]。为了让矛盾更突出，我把人数换成了50，如果事先不知道答案，猜测的结果一般远远小于97%。也许有人质疑，我们在计算时，假定人们的生日均匀而随机地分布，但生活中却未必如此——别担心，不平均分布的情形也已解决[3]，而且更进一步的证明是，不平均分布时，概率只会更高[4]。此外，Knuth在TAOCPv3中还计算了，平均在多少人中才能找到一对相同生日，答案是25人[5]，这看起来实在不可思议。
对于为何出现这种矛盾，我没有看到专门的研究。我的想法是，首先，当只有1个人时，概率为0%，当人数大于365时，根据鸽巢原理，概率是100%。于是，在1到365这个区间内，我们直觉地认为，对应的概率是线性地从0％增长到100%，哪怕不线性，也不会陡峭得太离谱，所以对于57人来说，该概率应该在57/365，即七分之一左右。但事实上，这条曲线的增长劲头却是十分可怕：[6]
绿色的曲线，就是在不同的人数时，对应的存在相同生日的概率，它就像坐了直升机一样迅猛窜升，在50人时就已相当接近100%，与我们幻想的线性曲线有天壤之别。那么问题就是：为啥我们会误以为它是线性的？别急，我们把问题稍作改动，就能得到启发。新的问题是，在一群人当中，有人与你同一天生日，这个概率有多大？同样地，我们把概率曲线描出来（即上图蓝色线），可以看到，它是十分平缓的。我认为，就是因为当我们看到“有人生日相同”时，下意识地用“与我生日相同”去推测，以致于把火箭发射当成了平稳增长，造成了生日悖论。
所以生日悖论的本质就是，随着元素增多，出现重复元素的概率会以惊人速度增长，而我们低估了它的速度。（对计算感到头疼的读者，可以选择在此停下脚步。别担心，世界依然美好。）这个问题不容忽视，因为它意味着，在密码学中，我们低估了散列值出现碰撞的概率。这一结论应用于对散列函数的攻击中，称为“生日攻击(Birthday Attack)”[2]。
然后是“讨厌”的一般公式了
因为麻烦所以不转了
想看的肯定愿意猛击……
至于这个问题的计算倒是简单的排列组合（说到这，好像高中做过这题？
1-(A50、365)/365^50=0.97
2009年12月15日 12点12分
1
原题：生日悖论与生日攻击
作者：苏椰
挺有趣的 算是“反”常识吧 就转过来了
注意开头的“出现这种缘分”是指“出现”同生日而不是有人“和你”同生日
但是数字似乎依然和“实际经验”不符
=======
每个人都有生日，偶尔会遇到与自己同一天过生日的人，但在生活中，这种缘分似乎并不常有。我们猜猜看，在50个人当中，出现这种缘分的概率有多大，是10%，20%，还是50%？
有人告诉我，在文章开头插入公式十分倒胃，所以我就不写计算过程，直接给出结果（除了传统的排列组合方法外，Paul Halmos[1]还给出了一个巧妙的解法）。在50个人中有相同生日的概率，高达97%，这个数字，恐怕高出了绝大多数人的意料。
我们没有算错，是我们的直觉错了，科学与生活，又开了个玩笑。正因为计算结果与日常经验产生了如此明显的矛盾，该问题被称为“生日悖论(BirthdayParadox)”[2]。它体现的，是理性计算与感性认识的矛盾，并不引起逻辑矛盾，所以倒也算不上严格意义上的悖论。它的原始表述是：在23个人当中出现相同生日的概率大于50%[2]。为了让矛盾更突出，我把人数换成了50，如果事先不知道答案，猜测的结果一般远远小于97%。也许有人质疑，我们在计算时，假定人们的生日均匀而随机地分布，但生活中却未必如此——别担心，不平均分布的情形也已解决[3]，而且更进一步的证明是，不平均分布时，概率只会更高[4]。此外，Knuth在TAOCPv3中还计算了，平均在多少人中才能找到一对相同生日，答案是25人[5]，这看起来实在不可思议。
对于为何出现这种矛盾，我没有看到专门的研究。我的想法是，首先，当只有1个人时，概率为0%，当人数大于365时，根据鸽巢原理，概率是100%。于是，在1到365这个区间内，我们直觉地认为，对应的概率是线性地从0％增长到100%，哪怕不线性，也不会陡峭得太离谱，所以对于57人来说，该概率应该在57/365，即七分之一左右。但事实上，这条曲线的增长劲头却是十分可怕：[6]
绿色的曲线，就是在不同的人数时，对应的存在相同生日的概率，它就像坐了直升机一样迅猛窜升，在50人时就已相当接近100%，与我们幻想的线性曲线有天壤之别。那么问题就是：为啥我们会误以为它是线性的？别急，我们把问题稍作改动，就能得到启发。新的问题是，在一群人当中，有人与你同一天生日，这个概率有多大？同样地，我们把概率曲线描出来（即上图蓝色线），可以看到，它是十分平缓的。我认为，就是因为当我们看到“有人生日相同”时，下意识地用“与我生日相同”去推测，以致于把火箭发射当成了平稳增长，造成了生日悖论。所以生日悖论的本质就是，随着元素增多，出现重复元素的概率会以惊人速度增长，而我们低估了它的速度。（对计算感到头疼的读者，可以选择在此停下脚步。别担心，世界依然美好。）这个问题不容忽视，因为它意味着，在密码学中，我们低估了散列值出现碰撞的概率。这一结论应用于对散列函数的攻击中，称为“生日攻击(Birthday Attack)”[2]。
然后是“讨厌”的一般公式了
因为麻烦所以不转了
想看的肯定愿意猛击……
至于这个问题的计算倒是简单的排列组合（说到这，好像高中做过这题？
1-(A50、365)/365^50=0.97
![[打酱油]](/static/emoticons/u6253u9171u6cb9.png)
