生日悖论（Birthday paradox）是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。

生日悖论的理解

理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如在前面所提到的例子，23个人可以产生种不同的搭配，而这每一种搭配都有成功相等的可能。从这样的角度看，在253种搭配中产生一对成功的配对也并不是那样的不可思议。

换一个角度，如果你进入了一个有着22个人的房间，房间里的人中会和你有相同生日的概率便不是50：50了，而是变得非常低。原因是这时候只能产生22种不同的搭配。生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少。

概率估计

假设有n个人在同一房间内，如果要计算有两个人在同一日出生的机率，在不考虑特殊因素的前提下，例如闰年、双胞胎，假设一年365日出生概率是平均分布的（现实生活中，出生机率不是平均分布的）。

计算机率的方法是，首先找出p(n)表示n个人中，每个人的生日日期都不同的概率。假如n > 365，根据鸽巢原理其概率为0，假设n ≤ 365，则概率为:

因为第二个人不能跟第一个人有相同的生日(概率是364/365),第三个人不能跟前两个人生日相同(概率为363/365),依此类推。用阶乘可以写成如下形式:

p(n)表示n个人中至少2人生日相同的概率:

n≤365，根据鸽巢原理， n大于365时概率为1。

当n=23发生的概率大约是0.507。其他数字的概率用上面的算法可以近似的得出来：

np(n)10 12%20 41%30 70%50 97%100 99.99996%200 99.9999999999999999999999999998%300 1 − (7 × 10。

然而Halmos的推导只显示至少需要23人保证平等机会下的生日匹配；因为我们不知道给出的不等式有多清晰，因此n＝22能够正切的可能也无法确定。

泛化和逼近

生日悖论可以推广一下：假设有n 个,每一个人都随机地从1和特定的N个数中选择出来一个数(N可能是365或者其他的大于0的整数)。

p(n)表示有两个人选择了同样的数字，这个概率有多大?

下面的逼近公式可以回答这个问题

N＝365的结果

泛化

下面我们泛化生日问题: 给定从符合离散均匀分布的区间随机取出n个整数, 至少2个数字相同的概率p(n;d) 有多大?

类似的结果可以根据上面的推导得出。

反算问题

反算问题可能是:

对于确定的概率 p ...... 找出最大的 n(p)满足所有的概率p(n)都小于给出的p,或者... 找出最小的n(p) 满足所有的概率p(n)都大于给定的p。

对这个问题有如下逼近公式:

举例

逼近估计N:=365pn 推广 n <N:=365 n↓p(n↓)n↑p(n↑)0.010.14178 √N 2.7086420.0027430.008200.050.32029 √N 6.1191660.0404670.056240.10.45904 √N 8.7700280.0743490.094620.20.66805 √N12.76302120.16702130.194410.30.84460 √N16.13607160.28360170.315010.51.17741 √N22.49439220.47570230.507300.71.55176 √N29.64625290.68097300.706320.81.79412 √N34.27666340.79532350.814380.92.14597 √N40.99862400.89123410.903150.952.44775 √N46.76414460.94825470.954770.993.03485 √N57.98081570.99012580.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-位长度的哈希表可能发生碰撞测试次数不是2次而是只有2N/2次。这一结论被应用到破解密码学散列函数的生日攻击中。

生日问题所隐含的理论已经在（Schnabel 1938）名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。

近似匹配

此问题另外一个范化就是求得要在随机选取多少人中才能找到2个人生日相同，相差1天，2天等的概率大于50％。这是个更难的问题需要用到容斥原理。结果(假设生日依然按照平均分布)正像在标准生日问题中那样令人吃惊:

2人生日相差k天#需要的人数0 231 142 113 94 85 77 6

只需要随机抽取6个人，找到两个人生日相差一周以内的概率就会超过50%。

参考文献

原文：The reasoning is based on important tools that all students of mathematics should have ready access to. The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What calculators do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories

2.Zoe Emily Schnabel: "The estimation of the total fish population of a lake"（某湖中鱼类总量估计）, 美国数学月刊 45 (1938年), 348-352页

3.M. Klamkin，D. Newman: "Extensions of the birthday surprise"（生日惊喜的扩充）, Journal of Combinatorial Theory 3 (1967年),279-282页。

4.D. Blom: "a birthday problem"生日问题, 美国数学月刊 80 (1973年),1141-1142页。{这一论文证明了当生日按照平均分布，两个生日相同的概率最小。)