引言

假设我问你一个房间应该有多少人，以便他们两个有生日的可能性为50％。 答案是什么？ 这就是所谓的生日悖论。

矛盾的是：

如果房间里有23个人，则他们有50％的概率是在同一天出生的。

某些版本的悖论做出了更强烈的声明：

如果房间中有70个人，则有99％的可能性是其中两人在同一天出生。

起初，这对我来说似乎是令人惊讶和违反直觉的。 让我们找出为什么这是真的。 为了简化任务，我们进行以下假设：

1. 我们假设房间中的所有人并非in年出生。 我们进行此假设，以便我们不必分析两种不同的情况。
2. 房间里没有双胞胎。 对于一对双胞胎，解决方案将是微不足道的。
3. 我们假设人们出生时是随机且均匀的。 这是什么意思？ 人们有可能在一年中的任何一天出生。 如果将其正式化，则在任何选定的日期出生的概率等于 $$$\ frac {1} {365}$ 。
4. 人们彼此独立地出生。 这意味着任何人的出生日期都不会影响另一个人的出生日期。

值得注意的是，在现实世界中不一定必须遵守这些条件。 特别是在现实世界中，人们并非天生具有统一的随机性。 此链接具有人们出生的日子的统计信息。 尽管我们的模型不能准确反映现实世界，但其简单性使分析问题变得更加容易。

我必须说，如果一个房间中有366个或更多的人，那么可以保证两个人的生日相同。 这是根据狄里克雷原理（“鸽子和盒子的原理”）得出的：如果有366人和365天，那么至少两个人必须有相同的生日。

假设房间中只有一个人，那么他与其他人共同生日的概率为0。 $$$（A_n）$ 将是其中的结果 $$$n$ 人们没有一个生日。 让 $$$\ Pr [A_n]$ -之间的概率 $$$n$ 房间里的每个人都在生日那天过生日。 同样，让 $$$\上线{A_n}$ 将补充 $$$A_n$ ，即 在其中的结果 $$$n$ 人两个人有相同的生日。

$$

$$\ Pr [A_n] + \ Pr [\上线{A_n}] = 1$$

$$

$$\ Pr [A_1] = 1 \文字{因为房间里只有一个人}$$

假设房间中有两个人，A和B。在不失一般性的前提下，想象一下A人于1月1日出生。 为了使B和A具有不同的生日，B必须在1月1日以外的任何一天出生。 B人将有364个生日选项。

$$

$$\ Pr [A_2] = \ Pr [\文本{B与A}不同] = \ frac {364} {365}$$

假设房间中有三个人，A，B和C。假设A人出生于1月1日，那么他们都出生在不同的日子，B人只有364天，如前例所示。 由于A和B需要两天，因此C人只能在365-2 = 363天出生。

$$

$$\ Pr [A_3] = \ Pr [\文本{B与A不同，C与B不同，A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

这里发生了一些更有趣的事情：假设房间已经有了 $$$k-1$ 人。 当他进入房间时 $$$k$ 那个人 $$$k$ 人们的生日不同，两个结果必定是正确的

1. 全部 $$$k-1$ 在他之前进入房间的人应该有不同的生日。 这有什么可能性？ $$$\ Pr [A_ {k-1}]$ 。
2. $$$k$ -该人的生日必须与其他所有人不同 $$$k-1$ 房间里的人。 这有什么可能性？ $$$\ frac {365-（k-1）} {365}$ 。

还应注意的是，以上介绍的两个结果是相互独立的，因为根据职位开头的假设（4）， $$$k$ 第二个人独立于其他人而出生。

$$$$显示$$ \开始{等式*} \开始{拆分} \ Pr [A_k]＆= \ Pr [k-1 \ text {房间里的人有不同的生日} \ textbf {AND} \\＆\ \ \ \ \ \ \ \ \文字{人k的生日不同于{k-1 \文字{people}的生日}} \\＆= \ Pr [k-1 \文字{房间中的人生日不同}] \\ ＆\ \ \ \ \ Times \ Pr [\文本{人k的生日不同于} k-1 \文本{people}] \\＆= \ Pr [A_ {k-1}] \ times \ frac { 365-（k-1）} {365} \结束{split} \结束{equation *} $$显示$$

现在我们计算概率：

$$$$显示$$ \开始{等式*} \开始{拆分} \ Pr [A_1]＆= 1 \\ \ Pr [A_2]＆= \ Pr [A_1] \次\ frac {364} {365} = \ frac {364} {365} \约0.997 \\ \ Pr [A_3]＆= \ Pr [A_2] \ times \ frac {363} {365} = \ frac {364} {365} \ times \ frac {363} {365} \约0.991 \\ \ Pr [A_4]＆= \ Pr [A_3] \ times \ frac {362} {365} \约0.983 \\＆\ vdots \\ \ Pr [A_ {22}]＆= \ Pr [A_ {21}] \次\ frac {344} {365} \约0.525 \\ \ Pr [A_ {23}]＆= \ Pr [A_ {22}] \ times \ frac {343} {365 } \约0.493 \\ \结束{拆分} \结束{方程*} $$显示$$

既然我们得到了 $$$\ Pr [A_ {23}] = 0.493 <0.5$ ，这意味着两个人共同生日的概率相等

$$

$$\ Pr [\上线{A_ {23}}] = 1-\ Pr [A_ {23}] = 1-0.493 = 0.507> 0.5$$

随着增加 $$$n$ 概率趋于1并达到它。

更艰巨的任务

假设我们要将这个问题推广到存在 $$$n$ 人们和 $$$m$ 可能的生日。 有 $$$n，m$ ，我们能否确定两个人共同过生日的可能性？

您可以使用相同的系统：我们将取得成果 $$$A_n$ 表示全部 $$$n$ 在不同日子出生的人。 在一个人的情况下，什么都没有改变

$$

$$\ Pr [A_1] = 1$$

在有两个人的情况下，我们将他们指定为A和B。要使人B在另一天出生，人B必须在其中一个生日 $$$m-1$ 其他选择。

$$

$$\ Pr [A_2] = \ frac {m-1} {m}$$

对于三个人，人B的生日必须与A的生日不同。人C的生日必须与A和B的生日不同。

$$

$$\ Pr [A_3] = \ frac {m-1} {m} \ times \ frac {m-2} {m}$$

通常适用于 $$$n$ 我们可以使用与上一节相同的递归公式：

$$

$$\ Pr [A_n] = \ Pr [A_ {n-1}] \次\ frac {m-（n-1）} {m}$$

假设我们要查找封闭形式的表达式 $$$\ Pr [A_n]$ ，然后分解表达式

$$$$显示$$ \开始{等式*} \开始{拆分} \ Pr [A_n]＆= \ Pr [A_ {n-1}] \次\ frac {m-（n-1）} {m} \ \＆= \ Pr [A_ {n-2}] \ times \ frac {m-（n-2）} {m} \ times \ frac {m-（n-1）} {m} \\＆= \ Pr [A_ {n-3}] \ times \ frac {m-（n-3）} {m} \ times \ frac {m-（n-2）} {m} \ times \ frac {m-（n -1）} {m} \\＆\ \ vdots \\＆= \ Pr [A_2] \ times \ frac {m-2} {m} \ times \ frac {m-3} {m} \ times \ cdots \ times \ frac {m-（n-3）} {m} \ times \ frac {m-（n-2）} {m} \ times \ frac {m-（n-1）} {m} \\ ＆= \ prod_ {i = 1} ^ {n-1} \ frac {mi} {m} = \ prod_ {i = 1} ^ {n-1} 1-\ frac {i} {m} \\＆＆ \ rox \ prod_ {i = 1} ^ {n-1} e ^ {\ frac {-i} {m}} \ text {使用身份} 1-x \ rox e ^ {-x} \\＆= e ^ {-\ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\＆= e ^ {\ frac {-n（n-1）} {2m}} \大约e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {equation *} $$显示$$

这个结果的近似值是 $$$\ Pr [A_n] \大约e ^ {\ frac {-n ^ 2} {2m}}$ 。 尽管我们可以找到更多近似边界，但是这给了我们足够的近似。 我们在这种近似中使用的唯一身份：

$$

$$1-x \约e ^ {-x}$$

以其抽象形式，生日悖论在计算机计算中有许多用途。 特别是，它用于散列中，散列本身有很多用途。 此任务中得出的结论是分析将两个元素哈希为一个键的概率的关键。 这个问题可以进一步推广到球和盆的概率问题（球和垃圾箱问题），我们将在另一个职位上讨论。

申请书

生日悖论不仅是人为的任务或有趣的聚会把戏，它还具有许多实际应用。 我个人认为，证据中使用的概率分析对于分析涉及随机化的其他问题很有用。 特别地，这涉及密码散列函数的开发。 我们将看到上面所做的分析如何在创建散列函数以及防止“生日”攻击时非常有用。

首先，让我们定义什么是哈希函数。 哈希函数 $$$h：U \ rightarrow [0，m-1]$ 是从集合执行映射的函数 $$ 在范围内的数量 $$$[0，m-1]$ 。 功能介绍 $$$h$ 定义为 $$$h（x）= x \ mod m$ -来自的示例哈希函数 $$$\ mathbb {N} \ rightarrow [0，m-1]$ 。 哈希函数有很多用途，尤其是与流行的哈希表数据结构结合使用时。 它也用在密码学中，其中使用了一种特殊类型的哈希函数，称为“加密哈希函数”。

密码哈希函数必须具有的许多属性之一是抗冲突性。 很难找到两个这样的 $$$u_1，u_2 \在U $$ 这样它们就形成了碰撞，即 $$$h（u_1）= h（u_2）$ 。

我们将重点放在对碰撞的抵抗上。 首先，我将解释为什么它是理想的属性。 为此，我们将首先考虑数字签名。

过去，人们和组织使用签名和盖章来“签名”文档。 最近，已经过渡到电子或数字签名。 数字签名必须满足三个基本属性。

1. 签署文档时，您需要能够验证谁签署了该文档。
2. 签署文件后，没有人可以伪造文件。
3. 签署文件的人随后不能反驳文件的签署。

数字签名是一种可证明地验证文档或消息真相的方法。 数字签名可确保接收到的消息是由已知发件人创建的，并且不会更改。

假设我们有一个文件 $$$m$ 。 我们如何签名？

每个用户/组织都有唯一的私钥 $$$p_k$ 和公钥 $$$pub_k$ 。 他们使用签名功能通过自己的私钥对文档进行签名。 但是，数字签名只能签署少量文件。 签名功能的范围很小。 解决此问题的一种方法是创建一个较小的文档，该文档代表原始文档，但尺寸要小得多。 最常见的是，将哈希函数应用于该大型文档。 散列函数用于将其从较大的空间映射到较小的空间，这种操作的结果称为“指纹”。 签名使用指纹和私钥创建签名。 该过程可以描述如下：

1. 获取私钥 $$$p_k$ 。
2. 散列文件 $$$m$ 并得到 $$$h（米）$ 。
3. 签收 $$$h（米）$ 使用私钥 $$$p_k$ 。
4. 我们发送 $$$符号（h（m），p_k）$ 和公钥 $$$pub_k$ 任何想要确认文件的人。

任何有 $$$符号（h（m），p_k））$ 和公钥，可以检查文档是否真的 $$$m$ 由合适的人签名。

问题：假设攻击者Eva找到了两个文件 $$$m，m'$ 在哪里 $$$m$ -这是当前合同，并且 $$$m'$ -欺诈性文件，使 $$$h（m）= h（m'）$ 。 假设夏娃事先知道爱丽丝只会签名 $$$m$ 但不是 $$$m'$ 。 签名前，将加密哈希函数应用于文档 $$$h$ 。 夏娃去爱丽丝，要她签名文件 $$$m$ 使用上述顺序。 现在，夏娃可能声称爱丽丝签署了欺诈性文件 $$$m'$ 因为 $$$h（m）= h（m'）$ 。 爱丽丝将无法以任何方式证明她未签名 $$$m'$ 。

在上面的例子中 $$$h$ 事实证明它是一种抗碰撞功能，因此Eve能够找到两个传入的散列相同值的数据集。 夏娃能够声称爱丽丝签了字 $$$m'$ 尽管事实上她只签了名 $$$m$ 。 这强调了抗冲突性的重要性，并说明了如果哈希函数不稳定，为什么数字签名容易受到攻击。

让 $$$h：U \ rightarrow [0，m-1]$ 将是一个哈希函数。 假设输入数据被随机均匀且独立地散列到任何元素中 $$$m$ 。

“生日”攻击的任务是找到最少数量的元素 $$$n$ 可以用 $$$h$ 这样我们可以找到两个元素 $$$x，y \以U$ 在哪 $$$h（x）= h（y）$ 。

攻击“生日”时，攻击者会随机捡起 $$$x \在U $$ 并保持伴侣 $$$（x，h（x））$ 。 攻击者将反复选择并保存这些对，直到找到两个值 $$$x，y$ 在哪 $$$h（x）= h（y）$ 。 我们需要确定攻击者需要多少次才能重复此操作，直到发现冲突为止。

要分析“生日”攻击，您可以使用与生日悖论相同的原理。 在袭击中“生日” $$$m$ 表示一年中的天数，并且 $$ 类似于进入房间的人。 人们在生日那天被散列，这可能是其中的含义之一。 $$$m$ 。 假设我们需要找到发生碰撞的机率为99％。 我们需要知道最小的是什么 $$$n$ ，其中两个值的散列将是一个生日（在散列函数的世界中，这意味着将两个输入数据集散列为相同的值）。

我们以前表明 $$$\ Pr [A_n] \大约e ^ {\ frac {-n ^ 2} {2m}}$

我们想问 $$$\ Pr [\上划线{A} _n] \大约e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ 那就是 $$$\ Pr [A_n] \大约e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ 。

$$$$显示$$ \开始{等式*} \开始{拆分} e ^ {\ frac {-n ^ 2} {2m}}＆= \ frac {1} {100} \\ \ frac {n ^ 2} {2m}＆= \ ln 100 \\ n ^ 2＆= 2 m \ ln 100 \\ n＆= \ sqrt {2 m \ ln 100} \ end {split} \ end {equation *} $$显示$$

上面显示的分析告诉我们，要在具有一定间隔的哈希函数中获得冲突 $$$m$ 攻击者需要均匀且独立地哈希大约 $$$\ sqrt {2 m \ ln 100} = O（\ sqrt {m}）$ 几乎可以完全保证（99％的概率）以相同的值对两个元素进行哈希处理。

假设我们要以50％的概率发生碰撞； 那么我们需要 $$$n = \ sqrt {2 m \ ln 2}$ 。 这里的重要结论是，为了获得概率大于0.5的碰撞，我们必须对顺序进行哈希处理 $$$\ sqrt {m}$ 元素。 这与我们先前对 $$$m = 365$ 因为 $$$\ sqrt {2 \ ln 2 \ cdot 365}$ 大约等于23

其他任务

1. 有 $$$n$ 的人 $$$m$ 天和一定数量 $$$k$ 找到确切的概率 $$$k$ 人们有相同的生日。
2. 让我们稍微改变一下上面的任务。 假设我们有 $$$m$ 天和一定数量 $$$k$ 。 最小值是多少 $$$n$ 不少于 $$$k$ 人们有相同的生日，概率至少为0.5？ 您能否将这项任务推广到任何可能性 $$$p> 0$ ？
3. 假设我们有100个1到100之间的数字，以及一台机器以统一和随机的顺序猜测1到100之间的一个随机数。 我们需要按预期使用机器多少次，以便机器猜测从1到100的所有数字？
4. 您可以将此任务推广到任何 $$$n$ ？
5. 假设我们有一个散列函数，可以在内存区域中随机均匀地显示元素。 让总面积 $$$m$ 。 多少件 $$$n$ 我们是否需要在数据结构中增加数学期望，以便每个区域中至少散列两个元素？