理解生日悖论(Birthday Paradox)

23人. 在一个只有23人的房间里，至少两个人拥有相同生日的概率是50%。在75人的房间里，至少两个人相同的概率是99.9%。

放下计算器和干草叉，我不是在说异端。生日悖论很奇怪、反直觉，而且 完全正确。它只是一个“悖论”，因为我们的大脑无法处理指数级的复合力量。我们期望概率是线性的，并且只考虑我们涉及的情景（顺便说一句，这两个都是错误的假设）。

让我们看看为什么会出现这个悖论以及它是如何工作的。

问题1：指数不是直觉的

我们学习过数学和统计学，但我们不要自欺欺人：这并不自然。

这里有一个例子：抛硬币连续10次得到正面的概率是多少？未经训练的大脑可能会这样想：

“嗯，得到一次正面是50%的概率。得到两次正面难度加倍，所以是25%的概率。得到十次正面可能难度是10倍……所以大概是50%/10即5%的概率。”

然后我们心安理得，得意洋洋。没门儿，老兄。

在苦学统计之后，你知道不是用除法，而是用指数. 抛10次全是正面的概率不是.5/10，而是$.5^10$，大约是.001。

但即使经过训练，我们还是会再次中招。以5%的利率，我们将在14年内使资金翻倍，而不是“预期”的20年。你是否自然地推断出了 72法则在学习利率的时候？可能没有。用我们线性的大脑理解复合指数增长是困难的。

问题2：人类有点自私

看看新闻. 注意有多少负面新闻是不考虑他人行事的结果。我是一个乐观主义者，做对人类抱有希望，但那是另一个讨论的话题:)。

在一个有23人的房间里，你是否会想到那22个比较，即你的你的生日与别人生日进行比较的情况？可能会。

你是否会想到 231 那些不涉及你自己，而是其他人之间相互比较的情况？你是否意识到有那么多？可能不会。

我们忽视 10倍之多 不包含自己的比较，这有助于我们理解为什么这个“悖论”会发生。

好吧，人类确实糟糕：让我看看数学吧！

问题是：在23人的群体中，两个人同一天生日的概率是多少？

当然，我们可以列出所有配对并计算所有可能匹配的方式。但这很困难：可能有1、2、3甚至23种匹配！

这就像问“连续抛23次硬币，至少一次正面的概率是多少？”有太多可能性：第一次抛出正面，或第三次，或最后一次，或第一次和第三次，第二次和第二十一次，等等。

我们如何解决这个硬币问题？反过来思考（懂了吗？懂了吗？）。与其计算所有出现正面的方式， 找出所有反面朝上的概率，即我们的“问题场景”.

如果全是反面的概率是1%（更像是.5^23，但请随我来），那么有99%的概率会 至少一个正面. 我不知道是1个正面，还是2个，或15个或23个：我们得到了正面，这才是重要的。如果我们用1减去问题情景的概率，就得到好的情景的概率。

同样的原理适用于生日问题。与其找出所有匹配的方式， 找出所有人都不同的概率，即“问题场景”. 然后我们取相反的概率，得到匹配的概率。可能是1个匹配，或2个，或20个，但有人匹配了，这才是我们需要找出的。

解释：计算配对（近似公式）

23个人时，我们有253个配对：

$\displaystyle{\frac{23 \cdot 22}{2} = 253}$

（复习组合与排列如果你喜欢的话）。

两个人拥有不同生日的概率是：

$\displaystyle{1 - \frac{1}{365} = \frac{364}{365} = .997260}$

说得通，对吧？当比较两个人的生日时，在365种情况中有364种不会匹配。很好。

但是让 253次比较 并且让他们所有都不同就像连续抛253次正面——你每次都必须避开“反面”。我们通过把生日比较当作抛硬币来得到一个近似解。（精确计算见附录A。）

我们使用指数来求概率：

$\displaystyle{\left(\frac{364}{365}\right)^{253} = .4995}$

单次不匹配的概率很高（99.7260%），但当这种概率重复数百次时，保持这种连续性的几率会下降得非常快。

找到匹配的概率是：1 – 49.95% = 50.05%，也就是刚刚超过一半！如果你想求任意人数n出现匹配的概率，公式是：

$\displaystyle{p(n) = 1 - \left(\frac{364}{365}\right)^{C(n,2)} = 1 - \left(\frac{364}{365}\right)^{n(n-1)/2} }$

交互式示例

我不相信只需要23个人。数学计算没问题，但它是真的吗？

当然。试试下面的例子：选择项目数量（365）、人数（23）并运行几次试验。你会看到理论匹配以及你的实际匹配随着你运行试验。来吧，点击按钮（或者查看完整页面).

当你运行越来越多的试验（继续点击！）时，实际概率应该接近理论概率。

示例与要点

以下是从生日悖论中学到的一些经验：

$\sqrt{n}$ 大致是为了在n个项目中达到50%匹配概率所需的数量。$\sqrt{365}$大约是20。这在密码学中用于生日攻击。
尽管有2¹²⁸ (1e38) GUID秒我们只有2⁶⁴ (1e19)在50%碰撞概率之前可用。而50%是非常非常高的。
只需要13个人从字母表中选字母，就有95%的概率出现匹配。在上面的例子中试试（人数=13，项目=26）。
指数增长会迅速降低选出唯一项的概率（即增加匹配的概率）。记住：指数是非直觉的，而人类是自私的！

在思考了很久之后，我终于理解了生日悖论。但我仍然会查看交互式示例来确认。

附录A：重复乘法解释（精确公式）

还记得我们假设生日是独立的吗？实际上它们并不是独立的。

如果人A和人B匹配，且人B和人C匹配，那么我们知道A和C也一定匹配。A和C匹配的结果依赖于它们与B的结果，因此概率不是独立的。（如果真正独立，A和C匹配的概率是1/365，但我们知道这是100%确定的匹配。）

在计算配对时，我们把生日匹配当作抛硬币，反复乘以相同的概率。这个假设并不严格成立，但对于较小的人数（23人）相对于样本容量（365）来说已经足够好了。多个人的匹配并破坏独立性的情况不太可能发生，所以这是一个很好的近似。

可能性不大，但仍可能发生。让我们计算每个人选择不同数字的真实概率：

第一个人有100%的概率选到唯一数字（当然）
第二个人有（1 – 1/365）的概率（除了365个中的1个数字）
第三个人有（1 – 2/365）的概率（除了2个数字）
第23个人有（1 – 22/365）（除了22个数字）

这个乘法看起来很丑陋：

$\displaystyle{p(\text{different}) = 1 \cdot \left(1-\frac{1}{365}\right) \cdot \left(1-\frac{2}{365}\right) \cdots \left(1-\frac{22}{365}\right)}$

但我们可以走捷径。当 x 接近 0 时，粗略的一阶泰勒近似对于 $e^x$ 是：

$\displaystyle{e^x \approx 1 + x}$

所以

$\displaystyle{ 1 - \frac{1}{365} \approx e^{-1/365}}$

利用我们的便捷捷径，我们可以把大方程重写为：

$\displaystyle{p(\text{different}) \approx 1 \cdot e^{-1/365} \cdot e^{-2/365} \cdots e^{-22/365}}$

$\displaystyle{p(\text{different}) \approx e^{(-1 -2 -3 ... -22)/365}}$

$\displaystyle{p(\text{different}) \approx e^{-(1 + 2 + ... 22)/365}}$

但我们记得对1到n求和 = n(n + 1)/2。不要将其与 n(n-1)/2 混淆，后者是 C(n,2) 或 n 个物品的对数。它们看起来几乎一样！

1 加到 22 是 (22 * 23)/2，所以我们得到：

$\displaystyle{p(\text{different}) \approx e^{-((23 \cdot 22) /(2 \cdot 365))} = .499998}$

呼。这个近似非常接近，在下面输入你自己的数字：

正如他们所说，足够应付政府工作了。如果你稍微简化公式并替换 n 为 23 你会得到：

$\displaystyle{p(\text{different}) \approx e^{-(n^2 / (2 \cdot 365))}}$

和

$\displaystyle{p(\text{match}) = 1 - p(\text{different}) \approx 1 - e^{-(n^2 / (2 \cdot 365))}}$

使用精确公式，366 人保证有碰撞：我们乘以 $1 - 365/365 = 0$，这消除了 $p(\text{different})$ 并使 $p(\text{match}) = 1$。使用近似公式，366 几乎保证，但不完全是 1：$1 - e^{-365^2 / (2 \cdot 365)} \approx 1$ 。