论文部分内容阅读
我们知道FIFA世界杯有32支参赛球队,每支球队有23名球员。那么同一支球队的两名球員同一天过生日的几率有多大呢?似乎可能性很小,毕竟一年有365天,而一个队只有23名球员,很难有两位生日撞在一起的情况。
实际上这种想法完全错误,一支球队里面找到两位同一天生日球员的几率超过了50%:如果人数再多点,在一个班级里面,假设有50名同学的话,其中两位同学同一天生日的概率甚至高达97%,这是不是违背了大多数人的直觉?要了解为什么我们的直觉判断跟科学认知有那么大的偏差,就要明白一个数学概念——生日悖论。
严格意义上,这并不是一个悖论,称之为悖论是由于跟人们的常识相悖。
假设我们让23名球员依次进入更衣室,第一名球员的生日可以是365天中任意一天;第二名球员这时再进来,如果要与第一名球员生日不同,他可以是剩下的364天中任意一天,即364/365,第三名球员要与前两名球员生日不同,概率是363/365;第四名球员是362/365,第五名是361/365……先进入房间的这些人生日两两不同的概率是很大的,比如说前面5个是1×364/365×363/365×362/365×361/365=97.3%。
而对于最后进入房间的几个人情况就完全不同。最后几个人进入房间并且找不到同生日者的概率是345/365,344/365,343/365。那么全部23人相乘,你会发现1×364/365×363/365×362/365×……345/365×344/365×343/365的结果约等于0.49,也就是这23人生日都不同的概率是49%,还不到一半,反过来即是51%的可能性找到两人生日在同一天。
大多数人之所以会认为23人中有2人生日相同的概率应该远远小于50%,是因为将问题理解为“其他22人与自己的生日相同的概率”,你要在22人当中去找一个与自己在365天内撞到同一天的人,概率当然非常小,但问题本意是“23人之中两两之间存在生日相同”。假设一个靶子上面有365个格子,其中364格为白色,1格为红色(你的生日),给其他22人每人开1枪的机会,命中红色格子的几率也很低。但如果开枪的人不管打中哪一格白色,都会将白色变成红色,那么越到后面,靶上的红色格子就越多,如果最后一人有机会开枪的话,靶上已经有22个红色格子了(对于23人来说可以出现22个不同的生日,只需要其中2人在同一天),命中红色格子的几率就大了很多。
理解了这一点,你就会明白实际概率为什么会比直觉大很多了。现在你可以拿自己班级来测算,当全班有50人时,概率约是97%。当100人在一起时,概率达到99.999997%,当200人在一起时,概率约是99.9999999999999999999999999998%,人越多,越无限接近100%,当人数达到366时,即超过365天,概率达到100%。
当然,以上算法是按常规年份一年365天来举例,排除了2月29日这样的特殊日期。
在计算机领域,这是一个不容忽视的问题。很多网络服务会使用哈希函数,产生一个token,标识用户的身份和权限。在这里我们不用去深入探究哈希函数是什么,简单来说,无论你是在某网站注册一个用户账号,还是自己的私人电脑账户,不需要太多人,可能就会出现另一个账号跟你重合(哈希碰撞),被服务器视为同一个人,这样对方就可以读取和更改你的账户信息,黑客攻击的一种方法,就是设法制造“哈希碰撞”,然后入侵系统,窃取信息。
我们把哈希值看成前面说的生日,如果只有3个字符长度,就像前面365天,那么很容易两个不同用户就撞车了。如果增加到5个字符,就好比在36500天当中找同一天生日的23个人,几率就大大降低了。22个字符的哈希值,就能保证300万亿次计算里面,只有1000亿分之一的概率发生碰撞。而常用的哈希函数产生的是64个字符的哈希值,发生碰撞的概率还要低得多。
举例说说我们生活中的应用,你的网络密码。如果是4位纯数字,那么只有总计1万个不同的密码(0000-9999),几乎别人随便找把钥匙就能把你家大门打开。6位纯数字,总计100万个不同的密码(000000-999999),对于存心要打开你家大门的人来说,也就是分分钟的事。8位以内的小写字母,一般是有意义的拼音或者单词,总计估计不超过1000万个不同的密码,也不算复杂;8位小写字母加数字,就是2.8万亿个不同组合,如果你不是什么特别人物,黑客也没兴趣来破解了。
实际上这种想法完全错误,一支球队里面找到两位同一天生日球员的几率超过了50%:如果人数再多点,在一个班级里面,假设有50名同学的话,其中两位同学同一天生日的概率甚至高达97%,这是不是违背了大多数人的直觉?要了解为什么我们的直觉判断跟科学认知有那么大的偏差,就要明白一个数学概念——生日悖论。
严格意义上,这并不是一个悖论,称之为悖论是由于跟人们的常识相悖。
假设我们让23名球员依次进入更衣室,第一名球员的生日可以是365天中任意一天;第二名球员这时再进来,如果要与第一名球员生日不同,他可以是剩下的364天中任意一天,即364/365,第三名球员要与前两名球员生日不同,概率是363/365;第四名球员是362/365,第五名是361/365……先进入房间的这些人生日两两不同的概率是很大的,比如说前面5个是1×364/365×363/365×362/365×361/365=97.3%。
而对于最后进入房间的几个人情况就完全不同。最后几个人进入房间并且找不到同生日者的概率是345/365,344/365,343/365。那么全部23人相乘,你会发现1×364/365×363/365×362/365×……345/365×344/365×343/365的结果约等于0.49,也就是这23人生日都不同的概率是49%,还不到一半,反过来即是51%的可能性找到两人生日在同一天。
大多数人之所以会认为23人中有2人生日相同的概率应该远远小于50%,是因为将问题理解为“其他22人与自己的生日相同的概率”,你要在22人当中去找一个与自己在365天内撞到同一天的人,概率当然非常小,但问题本意是“23人之中两两之间存在生日相同”。假设一个靶子上面有365个格子,其中364格为白色,1格为红色(你的生日),给其他22人每人开1枪的机会,命中红色格子的几率也很低。但如果开枪的人不管打中哪一格白色,都会将白色变成红色,那么越到后面,靶上的红色格子就越多,如果最后一人有机会开枪的话,靶上已经有22个红色格子了(对于23人来说可以出现22个不同的生日,只需要其中2人在同一天),命中红色格子的几率就大了很多。
理解了这一点,你就会明白实际概率为什么会比直觉大很多了。现在你可以拿自己班级来测算,当全班有50人时,概率约是97%。当100人在一起时,概率达到99.999997%,当200人在一起时,概率约是99.9999999999999999999999999998%,人越多,越无限接近100%,当人数达到366时,即超过365天,概率达到100%。
当然,以上算法是按常规年份一年365天来举例,排除了2月29日这样的特殊日期。
在计算机领域,这是一个不容忽视的问题。很多网络服务会使用哈希函数,产生一个token,标识用户的身份和权限。在这里我们不用去深入探究哈希函数是什么,简单来说,无论你是在某网站注册一个用户账号,还是自己的私人电脑账户,不需要太多人,可能就会出现另一个账号跟你重合(哈希碰撞),被服务器视为同一个人,这样对方就可以读取和更改你的账户信息,黑客攻击的一种方法,就是设法制造“哈希碰撞”,然后入侵系统,窃取信息。
我们把哈希值看成前面说的生日,如果只有3个字符长度,就像前面365天,那么很容易两个不同用户就撞车了。如果增加到5个字符,就好比在36500天当中找同一天生日的23个人,几率就大大降低了。22个字符的哈希值,就能保证300万亿次计算里面,只有1000亿分之一的概率发生碰撞。而常用的哈希函数产生的是64个字符的哈希值,发生碰撞的概率还要低得多。
举例说说我们生活中的应用,你的网络密码。如果是4位纯数字,那么只有总计1万个不同的密码(0000-9999),几乎别人随便找把钥匙就能把你家大门打开。6位纯数字,总计100万个不同的密码(000000-999999),对于存心要打开你家大门的人来说,也就是分分钟的事。8位以内的小写字母,一般是有意义的拼音或者单词,总计估计不超过1000万个不同的密码,也不算复杂;8位小写字母加数字,就是2.8万亿个不同组合,如果你不是什么特别人物,黑客也没兴趣来破解了。