)生日悖论
生日“悖论”是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论， 从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。 大多数人会认为,23人中有2人生日相同的概率应该远远小于50%. 计算与此相关的概率被称为 生日问题， 在这个问题之后的数学理论已被用于设计著名的密码攻击方法:生日攻击。
• 1 对此悖论的解释 • 2 概率估计 • 3 数学论证(非数字方法) • 4 泛化和逼近 o 4.1 N＝365的结果 o 4.2 泛化 • 5 反算问题 o 5.1 举例 • 6 经验性测试 • 7 应用 • 8 不平衡概率 • 9 近似匹配 • 10 参考 • 11 相关条目 • 12 參考文獻 • 13 外部链接
理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如在前面所提到的例子，23个人可以产生23 × 22/2 = 253 种不同的搭配，而这每一种搭配都有成功相等的可能。从这样的角度看，在253种搭配中产生一对成功的配对也并不是那样的不可思议。
换一个角度，如果你进入了一个有着22个人的房间，房间里的人中会和你有相同生日的概率便不是50：50了，而是变得非常低。原因是这时候只能产生22种不同的搭配。生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少。
假設有 n 個人在同一房間內，如果要計算有兩個人在同一日出生的機率，在不考慮特殊因素的前提下，例如閏年、雙胞胎，假設一年365日出生概率是平均分佈的（現實生活中，出生機率不是平均分佈的）。 計算機率的方法是，首先找出p(n)表示 n 個人中，每個人的生日日期都不同的概率。假如n > 365，根據鴿巢原理其概率為0，假设 n ≤ 365，则概率为 该图片显示特定人数对应的2个人生日一样的概率 因为第二个人不能跟第一个人有相同的生日(概率是364/365), 第三个人不能跟前两个人生日相同(概率为363/365),依此类推。用阶乘可以写成如下形式 p(n)表示 n个人中至少2人生日相同的概率 n≤365，根据鸽巢原理， n大于365时概率为1。 当 n=23发生的概率大约是0.507。其他数字的概率用上面的算法可以近似的得出来： n p(n) 10 12% 20 41% 30 70% 50 97% 100 99.99996% 200 99.9999999999999999999999999998% 300 1 − (7 × 10−73) 350 1 − (3 × 10−131) ≥366 100% 比较 p(n) = 任意两个人生日相同概率 q(n) =和某人生日相同的概率 注意所有人都是随机选出的:作为对比,q(n)表示房间中 n个其他人中与特定人（比如你）有相同生日的概率： 当n = 22时概率只有大约0.059,约高于十七分之一。如果n个人中有50％概率存在某人跟你有相同生日， n至少要达到253 。注意这个数字大大高于365/2 = 182.5: 究其原因是因为房间内可能有些人生日相同。
数学论证(非数字方法) 在 Paul Halmos 的自传中，他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此，Paul Halmos给出了一种概念数学方法的解释，下面就是这种方法（尽管这个方法包含一定的误差）。 乘积 }- 等于 1－p(n), 因此我们关注第一个n，使得乘积小于1/2，这样我们得到 }- 由平均数不等式得： }- (我们首先利用已知的1到n－1所有整数和等于 n(n－1)/2, 然后利用不等式不等式 1－x < e−x.) 如果仅当 最后一个表达式的值会小于0.5。 其中"loge"表示自然对数。这个数略微小于506，运气稍微好一点点就可以达到506，等于n2－n，我们就得到n＝23。 在推导中，Halmos写道: 这个推导是基于一些数学系学生必须掌握的重要工具。生日问题曾经是一个绝妙的例子，用来演示纯思维是如何胜过机械计算：一两分钟就可以写出这些不等式，而乘法运算则需要更多时间，并更易出错，无论使用的工具是一只铅笔还是一台老式电脑。计算器不能提供的是理解力，或数学才能，或产生更高级、普适化理论的坚实基础。[1]。 然而Halmos的推导只显示至少需要23人保证平等机会下的生日匹配；因为我们不知道给出的不等式有多清晰，因此n＝22能够正切的可能也无法确定。 [编辑] 泛化和逼近 生日悖论可以推广一下：假设有n 个,每一个人都随机地从1和特定的N个数中选择出来一个数(N可能是365或者其他的大于0的整数)。 p(n)表示有两个人选择了同样的数字，这个概率有多大? 下面的逼近公式可以回答这个问题 [编辑] N＝365的结果 [编辑] 泛化 下面我们泛化生日问题: 给定从符合离散均匀分布的区间[1,d]随机取出n个整数, 至少2个数字相同的概率p(n;d) 有多大? 类似的结果可以根据上面的推导得出。 }- [编辑] 反算问题 反算问题可能是: 对于确定的概率 p ... ... 找出最大的 n(p)满足所有的概率p(n)都小于给出的p,或者 ... 找出最小的n(p) 满足所有的概率p(n)都大于给定的p。 对这个问题有如下逼近公式: [编辑] 举例 逼近 估计N :=365 p n 推广 n <N :=365 n↓ p(n↓) n↑ p(n↑) 0.01 0.14178 √N 2.70864 2 0.00274 3 0.00820 0.05 0.32029 √N 6.11916 6 0.04046 7 0.05624 0.1 0.45904 √N 8.77002 8 0.07434 9 0.09462 0.2 0.66805 √N 12.76302 12 0.16702 13 0.19441 0.3 0.84460 √N 16.13607 16 0.28360 17 0.31501 0.5 1.17741 √N 22.49439 22 0.47570 23 0.50730 0.7 1.55176 √N 29.64625 29 0.68097 30 0.70632 0.8 1.79412 √N 34.27666 34 0.79532 35 0.81438 0.9 2.14597 √N 40.99862 40 0.89123 41 0.90315 0.95 2.44775 √N 46.76414 46 0.94825 47 0.95477 0.99 3.03485 √N 57.98081 57 0.99012 58 0.99166 注意:某些值被着色，说明逼近 不 总是正确。 [编辑] 经验性测试 生日悖论可以用计算机代码经验性模拟 days := 365; numPeople := 1; prob := 0.0; while prob < 0.5 begin numPeople := numPeople 1; prob := 1 - ((1-prob) * (days-(numPeople-1)) / days); print "Number of people: " numPeople; print "Prob. of same birthday: " prob; end; [编辑] 应用 生日悖论普遍的应用于检测哈希函数:N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解密码学散列函数的生日攻击中。 生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。 [编辑] 不平衡概率 就像上面提到的，真实世界的人口出生日期并不是平均分布的。这种非均衡生日概率问题也已经被解决。[Klamkin 1967] [编辑] 近似匹配 此问题另外一个范化就是求得要在随机选取多少人中才能找到2个人生日相同，相差1天，2天等的概率大于50％ 。这是个更难的问题需要用到容斥原理。结果(假设生日依然按照平均分布)正像在标准生日问题中那样令人吃惊: 2人生日相差k天 #需要的人数 0 23 1 14 2 11 3 9 4 8 5 7 7 6 只需要随机抽取6个人，找到两个人生日相差一周以内的概率就会超过50%。
